黃　玲，胡蔚蔚

( 1.廣東工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，廣州　510520；2.山東女子學(xué)院 信息技術(shù)學(xué)院，濟(jì)南　250300)

?

基于改進(jìn)蟻群算法的果蔬采摘機(jī)器人三維路徑規(guī)劃

黃玲1，胡蔚蔚2

( 1.廣東工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，廣州510520；2.山東女子學(xué)院 信息技術(shù)學(xué)院，濟(jì)南250300)

摘要：近年來(lái)，我國(guó)“農(nóng)民荒”問(wèn)題越演越烈，大量年輕勞動(dòng)力外出務(wù)工，農(nóng)村土地荒置越來(lái)越多。我國(guó)人口高齡化嚴(yán)重，農(nóng)業(yè)人口的減少，勞動(dòng)力缺口過(guò)大，導(dǎo)致對(duì)農(nóng)業(yè)機(jī)器人的需求極為迫切。隨著農(nóng)業(yè)機(jī)械和自動(dòng)化技術(shù)的快速發(fā)展，農(nóng)業(yè)機(jī)器人也在不斷發(fā)展，其可以更好地適應(yīng)生物技術(shù)種植產(chǎn)業(yè)發(fā)展，過(guò)去傳統(tǒng)的采摘方式將會(huì)有很大改變，農(nóng)民種植的側(cè)重點(diǎn)即將改善。為此，基于改進(jìn)蟻群算法，設(shè)計(jì)和規(guī)劃了果蔬采摘機(jī)器人行走的三維路徑，并增加在前進(jìn)過(guò)程中的自適應(yīng)調(diào)整功能。實(shí)驗(yàn)仿真結(jié)果表明：基于改進(jìn)蟻群算法的果蔬采摘移動(dòng)機(jī)器人三維空間路徑規(guī)劃在路徑和轉(zhuǎn)彎個(gè)數(shù)上都做到了最小化，能夠很好地滿足采摘機(jī)器人運(yùn)行需求。

關(guān)鍵詞：改進(jìn)蟻群算法；采摘機(jī)器人；三維空間；路徑規(guī)劃

0引言

隨著信息技術(shù)、微電子技術(shù)與農(nóng)業(yè)機(jī)械化的高速發(fā)展，農(nóng)業(yè)機(jī)器人的研究也獲得了極大突破，開(kāi)始在各個(gè)生產(chǎn)領(lǐng)域中應(yīng)用，不斷推進(jìn)農(nóng)業(yè)生產(chǎn)朝著自動(dòng)化和智能集成化發(fā)展。在果蔬種植過(guò)程中，采摘是最重要的一個(gè)部分，水果蔬菜一般采摘期短、采摘任務(wù)大、采摘要求高，對(duì)采摘人員的體力消耗很大。目前，我國(guó)水果蔬菜的采摘主要以人工為主，導(dǎo)致經(jīng)濟(jì)成本較高，采摘質(zhì)量低下，直接影響果農(nóng)的經(jīng)濟(jì)收入。隨著機(jī)器人技術(shù)的逐漸成熟，我國(guó)現(xiàn)階段已經(jīng)開(kāi)始加大對(duì)農(nóng)業(yè)機(jī)器人研究的投入，以實(shí)現(xiàn)對(duì)采摘過(guò)程的自動(dòng)化，這對(duì)解放農(nóng)村勞動(dòng)力、提高采摘的效率和質(zhì)量有著重要的意義。路徑規(guī)劃是采摘機(jī)器人作業(yè)過(guò)程中最重要的部分，采摘機(jī)器人的智能自動(dòng)化主要體現(xiàn)在對(duì)運(yùn)動(dòng)范圍、作業(yè)空間的規(guī)劃上。果林中環(huán)境地勢(shì)一般較為復(fù)雜，采摘機(jī)器人在其中前行作業(yè)需要對(duì)運(yùn)動(dòng)路徑具有很好的規(guī)劃技術(shù)，這樣可以節(jié)省一定的采摘時(shí)間、減少采摘機(jī)器人行進(jìn)過(guò)程的三維路徑計(jì)算優(yōu)化，并采用環(huán)境模型來(lái)仿真預(yù)測(cè)采摘機(jī)器人在作業(yè)中可能發(fā)生的某些碰撞以成功避開(kāi)障礙物，實(shí)現(xiàn)果蔬采摘機(jī)器人作業(yè)運(yùn)動(dòng)路徑最優(yōu)。

1改進(jìn)型蟻群算法

20世紀(jì)90年代，意大利研究者Dorigo受到螞蟻找食物的啟示，提出了一種仿生的蟻群算法。研究者發(fā)現(xiàn)：螞蟻在覓食過(guò)程中會(huì)留下作為信息素的分泌物，且在某條路線走過(guò)螞蟻越多，則后面螞蟻選擇該路徑的機(jī)會(huì)就越大，產(chǎn)生這一奇特的正反饋現(xiàn)象就是蟻群算法的由來(lái)。簡(jiǎn)化的螞蟻尋找食物過(guò)程如圖1所示。

圖1　螞蟻尋找食物示意圖

圖1中：(a)是表示螞蟻尋找食物路線的距離；(b)是t=0時(shí)兩條尋找食物路線上螞蟻的數(shù)量，最開(kāi)始兩條路線信息素是一樣的，螞蟻選擇兩條路線的概率相同；(c)是t=1時(shí)兩道尋找食物路線上的螞蟻數(shù)量，路線短的螞蟻更多。螞蟻從起點(diǎn)A到終點(diǎn)F，有ABCEF和ABDEF兩條距離不同的線路，因?yàn)锳BCEF的路徑短，時(shí)間越長(zhǎng)該線路走過(guò)的螞蟻越多，路上的分泌物也越多，則后面螞蟻選擇ABCEF短線路的機(jī)會(huì)就會(huì)越大。

假設(shè)短路線為S，長(zhǎng)路線為L(zhǎng)，KS和KL分別為經(jīng)過(guò)S和L的螞蟻數(shù)目，則

K=KS+KL

(1)

當(dāng)K只螞蟻?zhàn)哌^(guò)兩條路徑以后，第K+1只螞蟻?zhàn)逽路徑的概率為

(2)

PL(K)=1-PS(K)

(3)

其中，m和h是具體的參數(shù)。在第K+1只螞蟻選擇前，計(jì)算出PS(K)，然后再求到一個(gè)在[0,1]的隨機(jī)概率φ，若φ≤PS(K)，則選擇路線S，否則選擇路線L。

2三維空間路徑規(guī)劃

三維空間路徑規(guī)劃是機(jī)器人人工智能的核心問(wèn)題，機(jī)器人可以根據(jù)三維空間路徑規(guī)劃在三維空間中自主識(shí)別一條從起始點(diǎn)到目標(biāo)點(diǎn)距離最優(yōu)、障礙最少的路徑。與二維相比，三維空間路徑規(guī)劃的算法復(fù)雜度更高，限制性條件和外在因素更多，其效果一般很難達(dá)到設(shè)計(jì)者的預(yù)期。改進(jìn)蟻群算法具有智能群體和廣泛分布的優(yōu)勢(shì)，在三維空間路徑規(guī)劃算法上有很大的優(yōu)越性。山林地形三維空間立體結(jié)構(gòu)如圖2所示。

圖2　山林三維空間立體結(jié)構(gòu)圖

對(duì)三維路徑的規(guī)劃需要建立三維模型，即從復(fù)雜的果林地形中得到抽象的三維空間模型，具體的方法為：先取一點(diǎn)作為三維空間的原點(diǎn)O，并且在原點(diǎn)O建立直角坐標(biāo)系，X軸與Y軸形成的平面XOY平行于海平面，Z軸則垂直于海平面。三維模型如圖3所示。

圖3中，從起點(diǎn)B到目的地F有無(wú)數(shù)條路徑可走，這樣就需要利用蟻群算法求解最優(yōu)路線。首先建立三維空間模型，然后用柵格法將三維空間等分為體積大小相同的柵格，即獲得整個(gè)三維點(diǎn)的集合，且各類柵格表示一定的環(huán)境，每個(gè)柵格都代表一個(gè)節(jié)點(diǎn)值，計(jì)算出三維空間所有可能的路線，并通過(guò)搜索每一個(gè)可能的路徑求出最優(yōu)者。用以上算法可以求出從B到F的最優(yōu)路徑是BHF，而B(niǎo)AEF和BCGF相對(duì)來(lái)說(shuō)距離比較遠(yuǎn)。改進(jìn)蟻群算法在這些三維集合點(diǎn)上比較計(jì)算，求出起點(diǎn)到終點(diǎn)滿足距離最優(yōu)的路線。該方法簡(jiǎn)單實(shí)用，為路徑規(guī)劃的最優(yōu)性提供了很多方便。

圖3　三維空間模型圖

3改性蟻群算法的三維地形路徑規(guī)劃

首先將三維地形模型分為N個(gè)節(jié)點(diǎn)，然后將M個(gè)螞蟻任意的分配給N個(gè)節(jié)點(diǎn)，則節(jié)點(diǎn)i的第K只螞蟻去節(jié)點(diǎn)j的概率為

(4)

其中，λ(i,j)是邊(i,j)區(qū)間上的信息素，μ(i,j)=1/d(i,j) ；t是該螞蟻已經(jīng)到達(dá)過(guò)的列表信息。

在果林中選擇一片100m×100m×100m的山地，采用蟻群算法在其間進(jìn)行果實(shí)采摘作業(yè)，并求出從起點(diǎn)到目的地的最優(yōu)路徑，并在采摘作業(yè)中成功避開(kāi)果林中的障礙物。如圖4所示，設(shè)定A(18,20,22)為起點(diǎn)，D(98,60,86)為終點(diǎn)。蟻群算法的搜索范圍為圖4中整片山地。

圖4　山地環(huán)境規(guī)劃

在求最優(yōu)采摘路徑的過(guò)程中，改進(jìn)蟻群算法解決問(wèn)題的程序流程如圖5所示。

圖5　改進(jìn)蟻群算法程序流程圖

具體的算法流程如下：

1)建立規(guī)劃環(huán)境模型，設(shè)定采摘起點(diǎn)和終點(diǎn)，并準(zhǔn)確確定其在規(guī)劃環(huán)境模型的三維坐標(biāo)。

2)初始化蟻群算法參數(shù)，格式化所有信息素，清空迭代次數(shù)儲(chǔ)存信息，清空禁忌表。

3)初始化螞蟻，將螞蟻全部置于A。

4)螞蟻按照概率在節(jié)點(diǎn)間移動(dòng)，并將移動(dòng)的次數(shù)計(jì)數(shù)。

5)對(duì)于移動(dòng)次數(shù)小于軟件設(shè)置最大次數(shù)，且螞蟻沒(méi)有成功到達(dá)終點(diǎn)D時(shí)，回到第4步重新開(kāi)始，對(duì)于移動(dòng)次數(shù)大于等于軟件設(shè)置最大次數(shù)，且螞蟻沒(méi)有成功到達(dá)終點(diǎn)D時(shí)，初始化螞蟻所有數(shù)據(jù)，重新放回起點(diǎn)A；否則，判定該螞蟻數(shù)據(jù)信息無(wú)效。

6)統(tǒng)計(jì)成功到達(dá)D的螞蟻行走路徑P。

7)比較所有成功到達(dá)D的螞蟻行走路徑P，并求出最優(yōu)值。

8)輸出最優(yōu)路徑。

4三維地形路徑規(guī)劃軟件仿真設(shè)計(jì)

MatLab是矩陣實(shí)驗(yàn)室，是面對(duì)科學(xué)計(jì)算和可視化的高科技計(jì)算環(huán)境，為工程設(shè)計(jì)的數(shù)值計(jì)算提供了極大地方便。用MatLab對(duì)三維地形路徑規(guī)劃進(jìn)行仿真求優(yōu)，采用蟻群動(dòng)態(tài)尋路算法。蟻群算法在采摘機(jī)器人進(jìn)行路徑最短規(guī)劃的主程序如下：

1)狀態(tài)初始化。

W=S;Path=S;爬行路線初始化

PLkm=0;爬行路線長(zhǎng)度初始化

TABUkm=ones(1,N);禁忌表初始化

TABUkm(S)=0;已經(jīng)在初始點(diǎn)了，因此要排除

DD=D;鄰接矩陣初始化

2)下一步可以前往的節(jié)點(diǎn)。

DW=DD(W,:);

DW1=find(DW

for j=1:length(DW1)

if TABUkm(DW1(j))==0

DW(j)=inf;

LJD=find(DW

Len_LJD=length(LJD);可選節(jié)點(diǎn)的個(gè)數(shù)

3)轉(zhuǎn)輪賭法選擇下一步怎么走。

PP=zeros(1,Len_LJD);

For i=1:Len_LJD

PP(i)=(Tau(W,LJD(i))^Alpha)*(Eta(LJD(i))^Beta);

PP=PP/(sum(PP));建立概率分布

4)狀態(tài)更新和記錄。

Path=[Path,to_visit];路徑增加

PLkm=PLkm+DD(W,to_visit);路徑長(zhǎng)度增加

W=to_visit;螞蟻移到下一個(gè)節(jié)點(diǎn)

for kk=1:N

if TABUkm(kk)==0

5)記下所有螞蟻覓食路線和路線長(zhǎng)度。

ROUTES{k,m}=Path;

PL(k,m)=PLkm;

6)更新信息素。

Delta_Tau=zeros(N,N);更新量初始化

TS=length(ROUT)-1;跳數(shù)

PL_km=PL(k,m);

Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;

Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;

5仿真與結(jié)果分析

為了驗(yàn)證基于改進(jìn)蟻群算法的果蔬采摘機(jī)器人三維路徑規(guī)劃的可行性，運(yùn)用MatLab進(jìn)行仿真實(shí)驗(yàn)。該機(jī)器人在山林中停止進(jìn)行采摘作業(yè)的次數(shù)很多，選擇最優(yōu)路線進(jìn)行作業(yè)可以節(jié)約時(shí)間，減少資源浪費(fèi)，本文中選取300個(gè)路徑節(jié)點(diǎn)為機(jī)器人必須經(jīng)過(guò)的地點(diǎn)。假設(shè)整個(gè)規(guī)模為500次，軟件設(shè)定最大移動(dòng)次數(shù)為10 000，交互概率為0.75。運(yùn)用MatLab計(jì)算10次，在第4次得到最優(yōu)解7 456.353，所求最優(yōu)路徑如圖6所示。最優(yōu)路徑迭次曲線如圖7所示。

圖6　三維空間最優(yōu)路徑

圖7　最優(yōu)路徑迭次曲線

如圖7所示，基于改進(jìn)蟻群算法規(guī)劃了成功避開(kāi)障礙物且為長(zhǎng)度最短最優(yōu)的路徑。隨著迭代次數(shù)的增加，算法更加趨近最優(yōu)路徑，大大地提高了路徑質(zhì)量，而且波動(dòng)非常小，說(shuō)明改進(jìn)蟻群算法穩(wěn)定性強(qiáng)，可靠性高。

6結(jié)束語(yǔ)

針對(duì)采摘機(jī)器人在采摘作業(yè)過(guò)程中行走路徑過(guò)長(zhǎng)及效率低的問(wèn)題，設(shè)計(jì)了以改進(jìn)蟻群算法為核心的果蔬采摘機(jī)器人三維最優(yōu)路徑規(guī)劃，采用柵格法建立了環(huán)境模型，并實(shí)時(shí)根據(jù)實(shí)際出現(xiàn)的問(wèn)題再次進(jìn)行局部規(guī)劃調(diào)整，結(jié)合機(jī)器人轉(zhuǎn)彎次數(shù)制定最優(yōu)路徑。研究過(guò)程中運(yùn)用MatLab進(jìn)行仿真實(shí)驗(yàn)分析，并提出改進(jìn)方案，使機(jī)器人運(yùn)行效率有較大的提高；同時(shí)加強(qiáng)了運(yùn)行過(guò)程中的穩(wěn)定性，為果農(nóng)節(jié)省了大量時(shí)間和成本，證實(shí)了路徑規(guī)劃方案的可靠性。

參考文獻(xiàn)：

[1]馬強(qiáng).蘋果采摘機(jī)器人關(guān)鍵技術(shù)研究[D].北京：中國(guó)農(nóng)業(yè)機(jī)械化科學(xué)研究院,2012.

[2]柳軍.爬壁機(jī)器人的電機(jī)控制與路徑規(guī)劃[D].沈陽(yáng)：東北大學(xué),2010.

[3]周婷.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃及實(shí)現(xiàn)[D].長(zhǎng)沙：中南大學(xué),2010.

[4]劉亮.基于勢(shì)場(chǎng)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[D].南昌：南昌大學(xué),2013.

[5]范志超.基于PSO和彈性繩算法的水下潛器三維空間路徑規(guī)劃方法研究[D].哈爾濱：哈爾濱工程大學(xué),2013.

[6]范路橋,段班祥,周文瓊.應(yīng)用于機(jī)器人路徑規(guī)劃中的蟻群算法的改進(jìn)策略研究[J].現(xiàn)代計(jì)算機(jī),2013(5):3-8.

[7]賈祥素,吳菁.基于改進(jìn)蟻群算法服裝運(yùn)輸車輛路徑優(yōu)化研究[J]. 浙江紡織服裝職業(yè)技術(shù)學(xué)院學(xué)報(bào),2013(3):68-72.

[8]潘攀.足球機(jī)器人路徑規(guī)劃算法的研究及其仿真[J].計(jì)算機(jī)仿真,2012(4):181-184.

[9]馬軍煜,成旭華,葉學(xué)義.基于蟻群算法的可信網(wǎng)絡(luò)路由[J].電子技術(shù)應(yīng)用,2010(1):91-94.

[10]盧冰,王夢(mèng)蘭.一種改進(jìn)螞蟻算法在TSP問(wèn)題中的應(yīng)用[J].科技創(chuàng)業(yè)月刊,2010(6):128-129.

[11]苑嚴(yán)偉,張小超,胡小安.蘋果采摘路徑規(guī)劃最優(yōu)化算法與仿真實(shí)現(xiàn)[J].農(nóng)業(yè)工程學(xué)報(bào),2009(4): 141-144.

[12]成旭華,趙知?jiǎng)?葉學(xué)義.基于改進(jìn)蟻群算法的網(wǎng)絡(luò)路由重組[J]. 計(jì)算機(jī)工程,2009(13):90-92.

[13]王俊峰.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃[D].南京：南京師范大學(xué),2005.

[14]黎田.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[D].西安：西安科技大學(xué),2011.

[15]侯文靜.混合蟻群算法及其應(yīng)用研究[D].西安：西北師范大學(xué),2011.

[16]黃佰川.改進(jìn)蟻群算法在船舶鍋爐蒸汽壓力控制系統(tǒng)中的應(yīng)用研究[D].哈爾濱：哈爾濱工程大學(xué),2011.

[17]孫宇.基于蟻群算法的通信線路最佳搶修路徑問(wèn)題的研究[J].電腦知識(shí)與技術(shù),2011(7):1619- 1621.

[18]柳長(zhǎng)安,鄢小虎,劉春陽(yáng),等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J].電子學(xué)報(bào),2011(5):1220-1224.

[19]傅奧.多目標(biāo)資源受限項(xiàng)目調(diào)度問(wèn)題蟻群算法研究[D].杭州：浙江大學(xué),2008.

[20]毛琳波,劉士榮,俞金壽.移動(dòng)機(jī)器人路徑規(guī)劃的一種改進(jìn)蟻群算法[J].華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版,2006(8):997-1001.

[21]王崇寶.蟻群算法熵收斂性分析與應(yīng)用[D].成都：四川師范大學(xué),2009.

[22]尹向東.基于螞蟻優(yōu)化的QoS約束分布式多播路由算法研究與實(shí)現(xiàn)[D].長(zhǎng)沙：中南大學(xué),2008.

[23]陳杰.基于蟻群算法的機(jī)器人路徑規(guī)劃研究[D].南京：南京理工大學(xué),2009.

[24]任春明,張建勛.基于優(yōu)化蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程,2008(15):1-3,35.

[25]龔雨兵,李泉永.螞蟻算法在工件排序問(wèn)題中的應(yīng)用[J].桂林電子工業(yè)學(xué)院學(xué)報(bào),2004(2):68-71.

[26]胡小兵,袁銳,黃席樾,等.蟻群算法原理的仿真研究[J].計(jì)算機(jī)仿真,2004(8):125-128.

[27]廖興新.螞蟻算法在TSP問(wèn)題中的應(yīng)用與研究[D].成都：四川大學(xué),2006.

[28]朱國(guó)璽.嵌入式計(jì)算機(jī)系統(tǒng)熱分析及熱優(yōu)化研究[D].西安：西安電子科技大學(xué),2007.

[29]胡小兵,黃席樾.蟻群算法在迷宮最優(yōu)路徑問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)仿真,2005(4):114-116,161.

Three Dimensional Path Planning of Fruit and Vegetable Picking Robot Based on Improved Ant Colony Algorithm

Huang Ling1, Hu Weiwei2

(1.School of Information Engineering,Guangdong Polytechnic College,Guangzhou 510520, China； 2.School of Information Technology,Shandong Women College,Jinan 250300, China)

Abstract：In recent years, the"shortage of farmer" problem plays more more strong in our country,and a large number of young workers migrant workers, rural land fallow more and more. China's population aging is serious, the agricultural population is reduced, the labor gap is too large, which leads to the demand of agricultural robot very urgent. With the rapid development of agricultural machinery and automation technology, agricultural robots are constantly developing, which can better adapt to the development of biotechnology, the past the traditional picking methods will be greatly changed, the focus of farmers planting is about to improve. Based on the improved ant colony algorithm, this paper designs and plans the 3D path of fruit picking robot walking, and increases the adaptive adjustment function in the process of advancing. Experimental simulation results show that the improved ant colony algorithm based 3D space path planning of fruit and vegetable picking robot is the best way to meet the requirements of the picking robot.

Key words：improved ant colony algorithm; picking robot; 3D space; path planning

中圖分類號(hào)：S225.93；TP242

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1003-188X(2016)09-0038-05

作者簡(jiǎn)介：黃玲(1979-)，女，廣西桂林人，講師，碩士。通訊作者：胡蔚蔚(1980-)，女，濟(jì)南人，副教授，碩士，(E-mail)huangling1979@sina.com。

基金項(xiàng)目：山東省科技廳科技發(fā)展計(jì)劃項(xiàng)目(2013YD010334)

收稿日期：2015-08-16