改進蟻群算法在果蔬采摘機器人路徑規劃中的應用

李曉靜， 余東滿

(河南工業職業技術學院/河南省柔性制造重點實驗室，河南南陽 473009)

果蔬采摘機器人是一種集機器人技術與自動化技術于一體的新型多功能農業機械設備，因具有解決勞動力不足、改善農業生產環境、提高作業質量和作業效率等優點，故被廣泛應用于現代農業生產中。實際應用中，果蔬采摘機器人如何在復雜多變作業環境中，特別是多丘等特殊地理面貌中，能夠快速選擇最佳路徑實現安全避障完成作業任務，這就涉及到果蔬采摘機器人路徑規劃問題[1]。針對果蔬采摘機器人路徑規劃難題，國內外學者經多年攻關研究，相繼提出了多種有效算法，如果蠅算法[2]、蝙蝠算法[3]、粒子群算法[4]、A*算法[5]、遺傳算法[6]、狼群搜索算法[7]及蟻群算法等。

果蔬采摘機器人路徑規劃問題屬組合優化NP難題，具有問題求解復雜度高、可行解搜索空間大等特點，高效求解該問題仍存在較大挑戰，而蟻群算法(ACO)已被證明具有分布計算、信息正反饋、強魯棒性、強全局尋優能力及易與其他仿生算法融合等特點[8]，且試驗證明該算法在一些優化組合問題求解中能取得較好效果，受其影響，最近幾年學界學者開始嘗試用蟻群算法解決機器人路徑尋優問題，如周凌云等在原蟻群算法基礎上，設計了一種多啟發式信息蟻群優化算法，并用該算法解決了取樣送檢路徑規劃問題[9]；Li等利用改進蟻群算法求解了移動機器人全局路徑規劃問題[10]；游曉明等通過引入一種動態搜索誘導算子改進原蟻群算法，并用改進蟻群算法求解了復雜環境中的移動機器人路徑規劃問題[11]。

傳統蟻群算法會因收斂速度過快及正反饋機制引起的自催化現象而導致算法出現早熟收斂或停滯問題，此外，面對大規模復雜組合優化問題，該算法會存在收斂速度慢、易陷入局部最優及出現早熟收斂等問題，為克服上述缺陷，Yu等通過更改啟發函數因子及構建自適應信息素揮發系數對原蟻群算法進行改進，并將改進算法用于求解移動機器人路徑規劃問題，結果顯示，改進算法的收斂速度及搜索效率得到明顯改善[12]；饒楚鋒等通過自適應調整殘留信息素權重因子、啟發式信息素權重因子，更改信息素更新方式及引入雙向搜索策略對原蟻群算法進行改進，有效提高了算法收斂性能和全局尋優能力[13]。本研究將改進蟻群算法用于求解果蔬采摘機器人路徑規劃問題，為了使路徑搜索更具目的性，設計了新的啟發函數因子，并以此為基礎，修正了狀態轉移規則。同時由于原信息素更新規則易使算法陷入局部最優，為增加路徑選擇多樣性，避免算法出現早熟收斂或停滯問題，通過設計新的精英策略和引入新的信息素更新策略對信息素更新規則進行了改進。

1 建立環境模型

研究果蔬采摘機器人最優避障路徑規劃問題前，需先創建所需環境模型。環境模型建模方法有多種，主要有可視圖法、自由空間法、拓撲法和柵格法，相比于其他3種建模方法，柵格法具有建模復雜性低、建模精度高、障礙環境建模適應能力強及易于實現和存儲等優點型[14]，故選用柵格法創建果蔬采摘機器人工作環境模。建模前，需對果蔬采摘機器人和其工作環境作如下假設：(1)工作環境為二維靜態矩形有限空間，且空間尺寸數據已知；(2)環境模型中僅存在類似小丘陵的靜態障礙物，且障礙物形狀需根據機器人外形尺寸按一定比例進行膨化處理；(3)為簡化問題復雜度，可忽略機器人外形尺寸，用其中心點表示；(4)果蔬采摘機器人工作期間速度恒定，且可在勻速行駛和暫停2種工作模式切換；(5)機器人可由當前位置沿著上、下、左、右、左上、左下、右上和右下8個方向移動，但實際移動方向還需根據相鄰位置是否存在障礙物來決定。

柵格法建立的果蔬采摘機器人工作環境模型，為一個復雜多變且有障礙物的多丘場所，如圖1所示，采用序號法按照從左向右、自上至下的策略對每個柵格進行編碼。坐標系左下角為坐標原點，以原點為起點，水平向右為x軸正方向，豎直向上為y軸正方向，單個柵格尺寸由機器人單位步長及工作區域決定[15]。白色柵格被抽象為可行區域，即果蔬采摘機器人在此區域可自由移動，黑色柵格被抽象為障礙物(可用1個或多個柵格表示，當障礙物所占位置不滿足1個柵格時，需按照1個柵格處理)，表示此區域不可通行，點S和E分別表示機器人的起、止位置。

2 改進蟻群算法設計

2.1 基本蟻群算法

在覓食過程中，螞蟻間信息傳遞和路徑選擇的媒介是其遺留在采摘移動路徑上的信息素，該物質會隨時間推移而逐漸揮發，當后繼螞蟻經過該采摘路徑時，路徑上信息素濃度就會變高。在路徑搜索初期階段，由于路徑上并無殘留信息素，此時螞蟻依據狀態轉移概率大小決定行進方向，后繼螞蟻則可根據前者遺留在路徑上的信息素濃度高低，并綜合狀態轉移概率選擇路徑。當路徑信息素濃度越高時，后繼螞蟻選擇該路徑概率就越大，反過來也會促進該路徑信息素濃度的增加，螞蟻間正是依靠這種物質進行信息交互并最終搜索出蟻巢和食物間的最優路徑。行進中，螞蟻k由網格i轉向網格j的概率可由函數式(1)計算得到[16]：

(1)

式中：allowedk表示螞蟻k下一步待訪問網格集，此集合不包含障礙網格；τij(t)表示螞蟻k在網格(i，j)間路徑上遺留的信息素量，它會隨時間推移而逐漸揮發；ηij表示啟發函數因子，由網格(i，j)間距離決定，表達式為ηij=1/dij，dij表示網格(i，j)間距離；α和β分別表示τij(t)和ηij(t)對螞蟻狀態轉移概率的影響權重因子。

蟻群遺留在路徑上的信息素會隨時間推移而逐漸揮發，后繼螞蟻經過該條路徑又會帶來新的信息素，因此，當種群中所有螞蟻在完成一次循環搜索后，都要利用函數式(2)對路徑上的信息素進行更新[17]：

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

(2)

(3)

(4)

式中：τij(t)和τij(t，t+1)分別表示搜索路徑上信息素更新前后的濃度；Δτij(t，t+1)表示本次迭代所有螞蟻遺留在搜索路徑上的信息素總量；ρ表示信息素揮發系數；Lk表示本次循環螞蟻k搜索到的路徑的長度；Q表示信息素強度。

2.2 改進蟻群算法

實際問題求解中，相比于其他智能仿生算法，蟻群算法雖然能展現出諸多優勢，但面對大規模復雜問題求解時，也存在諸多問題，如收斂速度慢、收斂性能不穩定、搜索效率偏低、易陷入局部最優解，易出現早熟收斂或停滯及達不到特定任務要求等。為了解決上述問題，本研究分別從狀態轉移規則和信息素更新規則入手，對基本蟻群算法作了如下改進。

2.2.1 狀態轉移規則改進 在路徑搜索初期階段，由于可行路徑上無任何殘留信息素，螞蟻對下一節點選擇的隨機性比較強(路徑選擇盲目性比較大)，若因節點選擇的盲目性而引起搜索方向出現較大偏差，則會導致算法出現搜索效率低、易陷入局部最優等問題。針對此類問題，綜合考慮搜索路徑上當前節點、下一節點和目標節點間的幾何關系，設計了新的啟發函數因子，具體如函數式(5)所示。

(5)

式中：節點i、j和g分別表示螞蟻的當前網格、下一網格和目標網格；(xj，yj)和(xg，yg)分別表示網格(j，g)中心點的坐標；djg表示網格(j，g)間距離。

將設計的啟發函數因子(5)代入函數式(1)，可得新的狀態轉移規則，具體如函數式(6)所示。

(6)

2.2.2 信息素更新規則改進 路徑搜索中，螞蟻經過一條路徑后會釋放一定量的信息素，后繼螞蟻會根據信息素濃度強弱自動調整狀態轉移概率，進而選擇路徑。基于這種正反饋機制，為了改善算法收斂性能，提高搜索效率，使螞蟻搜索范圍盡可能快地集中在最優路徑附近，對信息素更新規則作了如下改進：

2.2.2.1 信息素局部更新 為了增加路徑選擇多樣性，避免算法出現早熟收斂問題，故在螞蟻每完成1次網格選擇后，需按照函數式(7)對訪問路段上的信息素進行局部更新：

τij(t+1)=(1-ρ)·τij(t)+ρ·τ0。

(7)

式中：τ0表示初始信息素量。

2.2.2.2 精英策略設計 螞蟻系統中，精英策略思想是找出目前為止所能搜索到的最優解，并通過獎懲機制為其額外增加一定量的信息素，而后誘導后繼螞蟻路徑搜索進程，最終使螞蟻更好、更快地獲取全局最優解[18]。受帶精英策略螞蟻系統影響，為了改善算法收斂性能和增強全局尋優能力，設計了新的精英策略，具體如函數式(8)所示。

(8)

式中：Δτ*表示每次循環最優采摘路徑上信息素的額外增量；υi是變量，表示每次循環選取的精英螞蟻數量，取值與每次循環所獲取的最優采摘路徑的個數一致；Lib表示本次循環所獲取的最優采摘路徑的長度；Q1為常數。

2.2.2.3 信息素全局更新 為了使螞蟻搜索范圍主要集中在當前迭代為止所能搜索到的最優采摘路徑領域內，當本次迭代中所有螞蟻均完成路徑搜索后，需采用函數式(9)對搜索路徑上的信息素作全局更新：

(9)

2.3 算法實現步驟

采用改進蟻群算法求解果蔬采摘機器人路徑規劃問題的具體步驟如下：步驟1：根據模型尺寸規格，采用柵格法建立果蔬采摘機器人工作環境模型；步驟2：初始化算法各參數，包括最大迭代次數Nmax、螞蟻數量m、初始信息素量τ0等，并根據任務要求，為機器人設置路徑規劃的起點和目標點；步驟3：將蟻群中m只螞蟻置于果蔬采摘機器人工作起點位置，算法開始迭代搜索；步驟4：行進中，螞蟻由當前網格i向下一網格j轉移的概率可由函數式(6)計算得到，待網格j確定后，采用函數式(7)對螞蟻剛經過的路段(i，j)上的信息素進行局部更新；步驟5：判斷所有螞蟻是否完成本次循環搜索，若是，則找出本次循環最優采摘路徑所對應的ID編號，并計算出精英螞蟻總量，否則，算法搜索過程轉至步驟3；步驟6：由步驟5所得數據，結合函數式(8)對最優路徑上的信息素進行額外獎勵；步驟7：由步驟6所得數據，結合函數式(3)、(4)和(9)對搜索采摘路徑上的信息素進行全局更新；步驟8：判斷路徑搜索循環次數是否達到預設上限值，若是，則路徑搜索進程終止，輸出結果，否則，轉至步驟3。

3 仿真試驗與分析

選用Matlab軟件作為仿真試驗平臺，以4種不同規格柵格模型作為果蔬采摘機器人工作環境模型，以路徑距離、程序耗時、轉折次數及算法收斂代數作為評價指標，在所設計算法下對果蔬采摘機器人路徑規劃過程作了仿真測試。為了從多個方面論證所設計算法的有效性和優越性，所設計算法分別與4篇文獻中所設計的改進蟻群算法作了對比論證。此外，為了使測試數據充分反映算法實際性能，根據測試要求，對每組試驗數據均作了多次重復測試，測試結果見表1、表2、表3和表4。

表1為本研究IACO與文獻[19]中算法的試驗統計結果，是在還原文獻[19]中環境模型的基礎上，采用本研究IACO與文獻[19]中算法經10次仿真測試得到。對比表1數據，從規劃路徑看，本研究IACO為果蔬采摘機器人搜索的路徑的長度主要集中在28 m附近，且搜索路徑平均長度和路徑所經拐點參數較文獻[19]中TACO和IACO均有不同程度減少，其中，平均路徑長度減少幅度分別為24.43%和 3.74%，平均拐點參數減少幅度分別為81.08%和36.36%，說明本研究IACO路徑尋優能力優于文獻[19]中的2種算法。從迭代次數看，本研究IACO搜索到全局最優路徑的迭代次數多集中在10代以下，較文獻[19]中TACO和IACO有較大幅度改善，且在搜索路徑長度35 m下最佳迭代次數上，較文獻[19]中2種算法分別減少了81.81%和50%，說明本研究IACO收斂速度快，搜索能力強。從程序平均耗時看，本研究IACO較文獻[19]中TACO和IACO分別減少了36.31%和30.14%，說明IACO搜索效率高。

表1 本研究IACO與文獻[19]中算法的試驗統計結果

表2為本研究IACO與文獻[20]中算法的試驗統計結果。分析表2數據，對比路徑規劃結果可以發現，3種算法均能完成路徑規劃目的。30次仿真試驗中，本研究IACO規劃路徑有20次達到最優路徑長度28.627 4 m，規劃路徑的最優長度和平均長度較文獻[20]中常規IACO和新設計IACO均有不同程度減少，其中，最優路徑長度分別減少了10.54%和5.56%，平均路徑長度分別減少了49.81%和43.63%，說明本研究改進策略有效，能大幅度增強算法全局尋優能力。從迭代次數看，本研究IACO搜索到全局最優路徑所需收斂代數≤10的有21次，在最大迭代次數和平均迭代次數上，較文獻[20]中常規IACO和新設計IACO均有大幅度減少，其中，最大迭代次數分別減少了75%和66.67%，平均迭代次數分別減少了82.69%和77.5%，說明本研究IACO收斂速度和搜索能力優于文獻[20]中的算法。在程序耗時上，本研究IACO雖略高于文獻[20]中算法，但因其有較快的收斂速度，搜索到最優路徑的折算耗費時間約為1.35 s，能夠滿足常規路徑規劃要求。

表3為本研究IACO與文獻[21]中算法的試驗統計結果。對比表3數據，與文獻[21]中TACO和IACO相比，本研究IACO的平均路徑長度分別減少了8.34%和0.54%，最大迭代次數分別減少了80.33%和61.29%，平均迭代次數分別減少了81.4%和66.67%。所述數據表明，與文獻[21]中算法相比，本研究IACO的全局尋優能力和收斂速度均為最優。

分析表4數據可知，在平均路徑長度、最大迭代次數和平均迭代次數方面，本研究IACO較文獻[22]中TACO分別減少了1.69%、74.6%和81.4%，較文獻[22]中IACO分別減少了0.84%、64.44%和79.49%。對比結果表明，本研究IACO全局尋優能力和收斂速度優于文獻[22]中算法。

表2 本研究IACO與文獻[20]中算法的試驗統計結果

表3 本研究IACO與文獻[21]中算法的試驗統計結果

表4 本研究IACO與文獻[22]算法的試驗數據對比

為了對果蔬采摘機器人路徑規劃過程分析研究，文中給出了基于4種模型的果蔬采摘機器人路徑規劃結果的其中一組可視化仿真結果，具體見圖2、圖3、圖4和圖5(本研究IACO與文獻[22]中IACO規劃路徑軌跡重合)。

圖2所示為基于模型1的果蔬采摘機器人路徑軌跡迭代圖，圖2-a為路徑軌跡圖，圖中虛線為文獻[19]中IACO搜索路徑軌跡，實線為本研究IACO搜索路徑軌跡；圖2-b為路徑長度迭代圖，實線為本研究IACO最優路徑長度曲線，虛線為本研究IACO平均路徑長度曲線。由圖1至圖4可知，本研究IACO和文獻[19-22]中IACO均能在有效避障前提下，為果蔬采摘機器人規劃出1條從起點至終點的全局最優或次優路徑。分析圖2-b、圖3-b、圖4-b路徑長度曲線變化情況，結合仿真數據統計結果可以看出，本研究IACO在保持較快的收斂速度前提下，能快速搜索到全局最優路徑。另外，在路徑搜索初期階段，平均路徑長度曲線雖有較大波動，但其總體隨時間變化呈下降趨勢，到一定迭代次數后，該曲線會與最優路徑長度曲線重合，說明本研究IACO收斂性能穩定性很強。分析文獻[19]中圖7和圖8、文獻[20]中圖3和圖4及文獻[21]中圖4和圖5可知，在路徑搜索初期階段，文獻[19-21]中算法搜索的最優路徑長度曲線存在較大波動，雖然后期隨時間推移能收斂到全局最優路徑，但所需收斂代數均較大且大于本研究IACO。另外，文獻[20]中圖3和圖4及文獻[21]中圖4和圖5顯示，在整個路徑搜索階段，文獻[20]中2種算法和文獻[21]中TACO的平均路徑長度曲線一直處于波動狀態，文獻[21]中IACO的平均路徑長度曲線雖然能隨時間變化而收斂到與最優路徑長度曲線重合，但此時所需迭代次數已達到120次。綜上分析可知，與文獻[19-22]中算法相比，本研究IACO收斂性能最優，搜索效率最高。

4 結論

通過引入精英策略、設計啟發函數因子、修正狀態轉移規則和更改信息素更新規則對基本蟻群算法進行改進，并基于改進算法求解果蔬采摘機器人路徑規劃問題。為測試改進算法的有效性和優越性，與其他算法作了對比論證，由測試結果可得結論：本研究改進算法能為果蔬采摘機器人規劃出全局最優避障路徑；能有效減少路徑所經拐點個數，可有效提高機器人工作效率；與對比文獻中算法相比，本研究IACO全局尋優能力最強，收斂速度最快，收斂性能最穩定。