基于改進蟻群算法的農業機器人路徑規劃研究

朱鐵欣，董桂菊，顏丙學，郭凱敏，謝學剛，郭志強

(東北農業大學，哈爾濱　150030)

?

基于改進蟻群算法的農業機器人路徑規劃研究

朱鐵欣，董桂菊，顏丙學，郭凱敏，謝學剛，郭志強

(東北農業大學，哈爾濱150030)

摘要：針對農業機器人路徑規劃實時性和穩定性差的問題，采用人工勢場法，并結合Memetic算法與精英排序法優化基本蟻群算法。該算法用勢場法獲得路徑初始化種群，對每代路徑進行Memetic算法中的交叉組合操作，將每代螞蟻產生的路徑分別進行優化排序，根據螞蟻路徑的優劣程度，對信息素進行更新；同時，加入精英小組螞蟻產生的信息素，從而加快了算法的收斂速度，提高了算法的穩定性。實驗表明：改進后算法的平均最優路徑長度提高了12.56%，收斂代數提高55.86%，算法用時提高了65.3%，最優解百分比增加了40%。本算法能夠快速有效地規劃出最優路徑，提高了農業機器人的工作效率。

關鍵詞：農業機器人；Memetic算法；路徑規劃；蟻群算法；精英排序；人工勢場

0引言

隨著科技的發展，智能機器人在農業領域的應用日益廣泛，而路徑規劃是農業機器人研究領域的重要內容之一，是實現機器人智能作業的必要基礎。路徑規劃一般分為環境地圖完全已知的靜態路徑規劃和環境地圖部分已知或全部未知的動態路徑規劃，本文主要對前者進行研究分析。對于這個問題，已經有大量學者進行研究和探索，并提出了很多解決方法。其中，蟻群算法的應用最為突出，該算法具有分布式計算、信息正反饋和啟發式搜索的特征，非常適合求解移動機器人的路徑規劃問題。但基本蟻群算法的執行過程依賴于大量的迭代和循環，缺乏實時性；運行過程中信息素不斷地累積，優質路徑不突出，對于最優解的求取有著很大的影響。針對這些問題，文獻[1]在算法停滯階段，引入交叉操作，并調整α、β和ρ的值，改善了算法的搜索效率；文獻[2]采用遺傳算法對蟻群算法的基本參數進行優化和配置，增強了算法的穩定性；文獻[3]采用人工勢場法融合蟻群算法，構建并加入了權重可調的引力概率函數作為啟發式因子，提高了算法的運行速度。為了減少算法運行時間，提高算法收斂速度和穩定性，本文融合了人工勢場、Memetic算法、精英小組和優化排序法以得到問題的更優解。

1基本蟻群算法

蟻群算法(Ant colony optimization,ACO)是意大利學者Dorigo等人，從螞蟻群體的覓食過程中受到啟發，于1991年提出的一種模擬自然界中蟻群行為的模擬進化算法[4]。以下為基本蟻群算法的主要過程。

(1)

螞蟻完成一次循環，各生成路徑上的信息素按下式進行調整，有

τij(t+1)=ρ·τij(t)+Δτij(t,t+1)

(2)

(3)

按照信息素增量表達方式的區別，基本蟻群算法可以分為蟻周系統、蟻量系統和蟻密系統。本文選用使用全局信息素更新策略的蟻周系統。軌跡信息素增量為

(4)

其中，Q為螞蟻k經過路徑(i,j)后，每單位長度釋放的信息素量；Lk為螞蟻k在本次循環所經過的路徑長度。螞蟻按照這一規則，循環往復進行，最終得到從起始點到目標點的最優路徑。

2改進算法設計

2.1　種群初始化

人工勢場法是由Khatib提出的一種虛擬力法。該算法應用在路徑規劃問題中時，將工作環境抽象為力場，目標點對移動機器人產生“引力”，障礙物對移動機器人產生“斥力”，機器人距離目標位置越近，所受“引力”的影響越大，反之越小。

設Xd為小車當前位置點，Xe為目標點，Xz為障礙物，共n個障礙物，車與障礙物的夾角為

(5)

其中，i=1,2,…,n；dzd為各障礙物與小車當前位置間距離。

目標對車的引力為

(6)

其中，y為引力增益系數；dde為當前位置與目標位置的距離；θe為當前位置與目標位置的夾角。

當路徑點與障礙物間距離大于預先設置的障礙物影響距離P0時，該障礙物對小車的斥力為0；否則，障礙物對車的斥力為

(7)

其中，c為斥力增益系數。

將位引力與斥力對應求和，則機器人在該合力的指引下尋找下一路徑點。

2.2　路徑更新

為了擴大路徑點的選擇范圍，減少鎖死和早熟現象的發生，在路徑更新的過程中融入Memetic算法。Memetic算法(也有文獻將其稱為文化基因算法)的概念在1989年由Moscato首次提出，并將其歸為一種基于群體的混合全局啟發式搜索算法[6]。Memetic算法采用的框架和操作流程與遺傳算法相似，應用在路徑規劃時，結合了遺傳算法和局部搜索算法的優點，全局尋優能力強，收斂性較高，能夠獲得高質量解。本文主要應用Memetic算法中的交叉操作。

在螞蟻完成一次迭代之后，隨機打亂一代中全部m只螞蟻的路徑順序，然后取第i條路徑和第m-i條路徑作為父代，將兩父代中所有路徑點合并，取出不重復的路徑點，且各路徑點首次出現的位置不變，作為子代新生路徑。下面進行舉例說明。

設路徑s1為(1 9 15 18 24 65)，路徑s2為(4 9 18 20 35 43)，合并路徑s1和s2，得到路徑s3為(1 9 15 18 24 65 4 9 18 20 35 43)，剔除重復路徑點并保持各點相對位置不變，得到子代路徑sz為(1 9 15 18 24 65 4 20 35 43)。

2.3　信息素更新

2.3.1優化排序

在完成算法一次迭代后，將本次循環中所有螞蟻形成的有效路徑，按照從大到小(L1≥L2≥L3≥…≥Lm)的順序進行排列，路徑長度越長，排名越靠前，則對該路徑上的信息素增加較小；反之，較短路徑會對信息素的更新做出較大貢獻。

本設計采用冒泡排序(Bubble Sort)法[7]，是一種穩定的排序算法。它重復地走訪要排序的數列，一次比較兩個元素，若順序與設置不同，則交換兩個元素，直到完成最后兩個元素的比較，排序完成。同時，在排序過程中加入swap變量，它的作用是如果某次比較路徑長度Ln=Ln+1，不用將其交換，即可視為排序已完成，就會直接做結束處理。如此，便得到從大到小的路徑排序，將此排序翻轉，則得到算法所需順序，即從小到大。排序過程流程圖如圖1所示。其中，lengh(Lm)為可行路徑數量。

2.3.2精英小組

在信息素更新時，在對所有可行路徑增加信息素的基礎上，加入精英蟻群小組。精英蟻群小組指在算法執行過程中，得到最短路徑的螞蟻小組。使用精英螞蟻小組可以更快、更好地找出最優解。然而，如果精英螞蟻的選擇太多，搜索將迅速地集中在其周圍的最佳值附近，這樣將會導致過早收斂；選用精英螞蟻過少，對算法的優化則難以達到預期的效果。經大量實驗分析，精英數量小組數量jj取3~6時效果較好。部分實驗數據如表1所示。

圖1　冒泡路徑排序流程圖

樣本號mkjj18035425010063403544505046503537508048406039454031035453

3算法的實現

應用人工勢場、Memetic算法和精英排序改進蟻群算法的算法流程圖如圖2所示。

算法步驟為以下8步。

Step1：算法基本參數設置。

Step2：初始化禁忌表、信息素等，人工勢場法初始化螞蟻爬行路經。

Step3：設置評價函數，本文以起始位置到目標位置間直線距離的倒數作為啟發式因素。

Step4：按輪賭法尋找螞蟻運行路徑點。

Step5 ：Memetic算法更新所得路徑，將所得路徑進行交叉組合操作。

Step6：優化排序和精英小組信息素更新。

Step7：全局信息素更新。

Step8：判斷是否滿足終止條件，即是否獲得最優路徑，或達到最大迭代次數，滿足則運行結束，不滿足則返回Step4。

圖2　改進蟻群算法流程圖

4實驗研究

4.1　仿真環境

W.H.Howden提出的柵格法[8]在處理路徑規劃問題時，可視地圖簡單、清晰。并且，柵格法易于實現計算機的建模、存儲、處理、更新與分析。實驗中將圖片進行柵格化處理，障礙區域用1表示，可行區域用0表示，并將柵格按照從左到右、從上到下的順序進行編碼，格柵個序號與坐標的關系為

S=(j-1)×20+i

(10)

其中，i，j分別為柵格的橫縱坐標。

本實驗采用20×20的障礙柵格模擬實際農田環境，分別采用復雜障礙、中等復雜障礙、簡單障礙環境，每種環境進行20次仿真。此仿真過程中，將障礙物尺寸增加機器人半徑長度，即視機器人為質點；障礙物不滿一柵格，按一柵格處理。

4.2　仿真結果分析

取基本蟻群算法參數迭代次數K=100，蟻群數量M=50，信息素激勵因子α=1.5，啟發式激勵因子β=9，信息素強度Q=1，信息素揮發系數ρ=0.31；改進算法中取K=35，引力增益系數y=8，斥力增益系數c=4，障礙影響距離P0=1.8，勢場步長b=2.1，并加入精英小組jj=3。表2為各障礙環境下的仿真數據結果。圖3為算法改進前后各數據結果柱狀圖。

表2　算法改進后仿真數據結果

圖3　算法改進前后結果對比圖

圖3中，改進前后最優路徑長度、收斂代數、算法用時皆為3種環境規模平均值，改進前分別為32.64、48.33、19.54，最優解百分比為48%；改進后為28.54、21.33、6.78，最優解百分比為88%，這4個評價參數分別提高了12.56%、55.86%、65.3%、40%，在收斂速度和算法用時上最為顯著，達到了本文的目的。圖4為算法改進后不同障礙環境路徑結果圖。從圖4中可以直觀地看到，對于不同的環境模型，該改進算法都可以找到最優路徑。

復雜障礙 　　　　　　　　　　　　　　 中等復雜障礙 　　　　　　　　　　　　　　 簡單障礙

5結論

由于基本蟻群算法迭代次數多、運行速度慢，容易產生鎖死現象，本文采用一種基于人工勢場、冒泡排序和精英小組的改進蟻群算法，并融入Memetic算法。該算法在初始時刻產生優質初始值，路徑更新過程加入交叉操作，信息素更新時，突出優質螞蟻對算法規劃的影響，增加優質路徑搜索范圍，從而使后來螞蟻能夠更快地找到優質路徑，加快了算法的收斂速度，進而可以減少迭代次數，提高算法效率。

仿真結果表明：與基本蟻群算法相比，改進算法在運行用時和收斂速度上皆有大幅度的提高，具有更高的穩定性和有效性，說明本文中的算法改進是有效可行的，提高了農業機器人運動過程中的穩定性和實時性。基于此改進效果，該算法可以應用于自主移動農業機器人，為其智能移動進行采摘、噴藥等工作的實施提供了理論依據。

參考文獻：

[1]張琦,馬家辰,謝瑋，等.基于改進蟻群算法的移動機器人路徑規劃研究[J].東北大學學報：自然科學版,2013,34(11):1521.

[2]Wang Zhangqi, Zhu Xiaoguang, Han Qingyao.Mobile robot path planning based on parameter optimization ant colony algorithm[J].Procedia Engineering, 2011,15(8):2738-2741.

[3]孫純哲,桂貴生,韓東，等.基于蟻群算法的移動機器人路徑規劃研究與應用[J].合肥工業大學學報：自然科學版,2006,29(10):1208

[4]李世勇.蟻群算法及其應用[M].哈爾濱：哈爾濱工業大學出版社,2004:29-31.

[5]段海濱.蟻群算法原理及其應用[M].北京：北京科學出版社,2005:36-48.

[6]陳穎頻,王靈芝,吳金峰，等.基于選擇思想和反序標識的改進冒泡排序算法[J].泉州師范學院學報,2014,32(6):89.

[7]段海濱,張祥銀,徐春芳.仿生智能計算[M].北京：科學出版社,2011:130-143.

[8]吳登峰,梅志千,尹立偉，等.一種未知環境下移動機器人路徑規劃新算法[J].機電工程,2015,32(3):390.

Research for the Path Planning of the Agricultural Robot Based on the Improved Ant Colony Algorithm

Zhu Tiexin， Dong Guiju，Yan Bingxue， Guo Kaimin， Xie Xuegang， Guo Zhiqiang

(Northeast Agricultural University, Harbin 150030, China)

Abstract：In response to the problems of agricultural robot path planning bad real-time and stability,artificial potential field, elite sorting method combined with Memetic algorithm is adopted. This algorithm initialize the path population with potential field method,optimizes the sorting of each generation ants path. And also updates the pheromone according to the superiority of the ants path. At the same time, with the help of the pheromone of the elite ants, and using crossover and mutation operation of the memetic algorithm on each generation path,so as accelerate the convergence speed of the algorithm, improves the stability of it.The simulation results show that the improved algorithm of the optimal path length on average increased by 12.56%,the convergence generation increased by 55.86%, the algorithm time increased by 65.3%,and the optimal solution percentage increased by 40%,this shows that the mentioned algorithm can plan the optimal path in a quick and efficient way, improving the efficiency of agricultural robot.

Key words：agricultural robot; memetic algorithm; path planning; ant colony algorithm; elite sorting; artificial potential field

中圖分類號：S24

文獻標識碼：A

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

作者簡介：朱鐵欣(1990-)，女，黑龍江五營人，碩士研究生，(E-mail)1254904178@qq.com。通訊作者：董桂菊(1967-)，女，哈爾濱人，副教授，碩士生導師。

基金項目：國家“863計劃”項目(810028)

收稿日期：2015-08-26