黃　玲，胡蔚蔚

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

?

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

黃玲1，胡蔚蔚2

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

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

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

0引言

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

1改進型蟻群算法

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

圖1　螞蟻尋找食物示意圖

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

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

K=KS+KL

(1)

當K只螞蟻走過兩條路徑以后，第K+1只螞蟻走S路徑的概率為

(2)

PL(K)=1-PS(K)

(3)

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

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

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

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

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

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

圖3　三維空間模型圖

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

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

(4)

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

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

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

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

圖5　改進蟻群算法程序流程圖

具體的算法流程如下：

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

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

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

4)螞蟻按照概率在節(jié)點間移動，并將移動的次數(shù)計數(shù)。

5)對于移動次數(shù)小于軟件設(shè)置最大次數(shù)，且螞蟻沒有成功到達終點D時，回到第4步重新開始，對于移動次數(shù)大于等于軟件設(shè)置最大次數(shù)，且螞蟻沒有成功到達終點D時，初始化螞蟻所有數(shù)據(jù)，重新放回起點A；否則，判定該螞蟻數(shù)據(jù)信息無效。

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

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

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

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

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

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

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

PLkm=0;爬行路線長度初始化

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

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

DD=D;鄰接矩陣初始化

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

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é)點的個數(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);路徑長度增加

W=to_visit;螞蟻移到下一個節(jié)點

for kk=1:N

if TABUkm(kk)==0

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

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é)果分析

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

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

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

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

6結(jié)束語

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

參考文獻：

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

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

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

[4]劉亮.基于勢場蟻群算法的移動機器人路徑規(guī)劃研究[D].南昌：南昌大學,2013.

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

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

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

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

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

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

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

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

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

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

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

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

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

[18]柳長安,鄢小虎,劉春陽,等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學報,2011(5):1220-1224.

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

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

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

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

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

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

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

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

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

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

[29]胡小兵,黃席樾.蟻群算法在迷宮最優(yōu)路徑問題中的應(yīng)用[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

中圖分類號：S225.93；TP242

文獻標識碼：A

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

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

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

收稿日期：2015-08-16