擴散強制蟻群算法求解越野機器人路徑規劃

宋阿妮，包賢哲，付 波

（湖北工業大學電氣與電子工程學院，湖北 武漢 430068）

1 引言

隨著人工智能與集成技術的不斷發展，智能機器人開始運用于制造[1?2]、物流[3?4]、服務[5?6]、醫學[7?8]等各行各業中，機器人在工作時需解決的最大問題是如何在復雜環境中找到行進路徑并避開障礙物到達指定地點完成相關任務，提升智能機器人尋找最優路徑的速度將能夠大幅提升機器人工作的效率，為企業生產節省更多時間，具有較高的研究價值。該問題已成為當下人工智能領域研究的熱點，國內外學者對其做過相關研究。

如文獻[9]采用改進的人工蜂群算法提高了結果的收斂精度；文獻[10]構建有重構性的倉庫空間模型并采用改進的A*算法[11]大幅降低機器人行進的路徑長度；文獻[12]結合天牛須搜索算法和A*算法提出一種BACA*全局規劃算法，并通過仿真證明得到的路徑更加平滑，折點數更少；文獻[13]采用圖論遍歷的方法解決此機器人路徑尋優問題；文獻[14]采用非線性策略改進灰狼算法[15]求解該問題，并用實例進行仿真證明了算法穩定性；文獻[16]將人工免疫免疫算法和粒子群算法結合起來強化算法的局部搜索能力并進行了實驗仿真；改進的人工免疫球算法[17]和粒子群算法[18?19]在求解類似路徑問題上有著較好的效果。文獻[20]提出基于障礙物位置和大小的搜索方法，能夠顯著提升收斂速度；文獻[21]針對動態環境下的機器人路徑規劃問題，對柵格進行凹凸化處理防止其陷入U型陷阱，并采用雙層蟻群算法尋優，最終通過仿真驗證其在動態環境下依舊能準確尋找最優路徑；文獻[22]依據RRT算法原理提出一種多優化設計快速擴展隨機樹算法解決了傳統算法收斂慢、路徑平滑效果差等問題，實驗結果顯示其擁有良好的實時性和魯棒性；文獻[23]結合模擬退火思想改進遺傳算法讓規劃的路徑更加安全可靠，實際應用性強；文獻[24]則研究了當工作環境超出機器人的感知范圍的路徑優化問題，但并未考慮到障礙物體積因素，實際應用性不強；文獻[25]結合柵格法、子區域劃分法、模板模型法等策略，運用啟發式搜索算法大幅提高了機器人的工作效率；文獻[26]采用改進智能水滴算法尋找路徑，并用標準測試函數驗證了算法的有效性。很多算法在機器人路徑優化問題上都有著不錯的效果，但是仍然存在最優路徑收斂太慢，不平滑，收斂精度不高的問題。針對這些問題，提出了一種擴散強制蟻群算法（Diffusion Forced Ant Colony Optimization，DFACO），首先算法通過極值策略限制了信息素增長，防止算法陷入停滯，其次通過信息素擴散策略加強了較近螞蟻的協作和關聯，加快了算法的收斂速度，再通過強制刺激策略對陷入停滯的算法進行刺激使其脫離局部最優繼續搜尋最優解，提高算法的搜的范圍和粒子多樣性，最后用DFACO、ACO、GA、FA算法在四個不同實例下求解最優路徑，證明了該算法能夠快速高效的為機器人規劃出一條最短的平滑路徑。

2 問題分析與模型建立

為了模擬野外山地的真實情況，將野外山地分割成大小面積相同的S∈[a×b]的柵格區域，共有a×b個區域方塊，區域方塊坐標由方塊中心點代替。

其中黑色區域部分表示巖石、水坑、山峰、樹木等障礙物，越野運輸機器人以勻速從戰場中任意K點向任意L點搬運物資，區域情況示意圖，如圖1所示。

圖1 工廠模擬柵格示意圖Fig.1 Schematic Diagram of Factory Simulation Grid

運輸機器人在區域S內可以朝著上、下、左、右、左上、左下、右上、右下八個方向移動，若周圍八個方向有黑色方塊區域存在，則不能向此方向移動，其移動示意圖，如圖2所示。如圖2所示，處于第5塊方塊區域內的運輸機器人可以向除了第1塊黑色區域以外的7個方向移動，要求運輸機器人在不觸碰任何黑色區域的情況下以最短的距離到達指定位置。

圖2 運輸機器人移動示意圖Fig.2 Schematic Diagram of Transport Robot Movement

根據上述對問題的描述可知：

3 改進的蟻群算法

3.1 傳統蟻群算法

蟻群算法是由Marco Dorigo于1992年在他的博士論文中提出的一種用來尋找優化路徑的概率型算法，它的原理是模仿螞蟻在尋找食物過程中發現路徑的行為。

蟻群算法常用于旅行商問題，螞蟻依據兩個區域之間的信息素濃度和距離選擇下一個目標區域，第k只螞蟻從區域i前往下一個區域j的概率為：

式中：Q—常數；Lk—螞蟻k走過的路徑總長度；qij—路徑ij；Q—螞蟻k走過的路徑集合。

3.2 改進蟻群算法

3.2.1 大小極值改進策略

當螞蟻在一條道路上走過的次數過多時，會導致該線路信息素含量遠遠超過其他線路，算法會因此進入停滯狀態不再搜索其他線路。為了解決這一問題，給信息素濃度做出限制，信息素濃度的最大值為：

3.2.2 信息素擴散策略

螞蟻釋放信息素時往往可以向附近的同伴傳遞信息，根據這一特征，提出信息素擴散策略來提升距離較近的螞蟻之間的協作能力，提升算法的收斂速率。信息素等類似揮發物質在空間中擴散近似服從正態分布，如圖3所示。

圖3 信息素擴散正態分布圖Fig.3 Normal Distribution of Pheromone Diffusion

圖中：x—距離信號源頭O點的距離；z—信息素濃度水平。

隨著與信息素源O點距離的增加，信息素擴散濃度不斷降低。將這樣一個擴散場域平面模型在空間中展開并簡化后，如圖4所示。

圖4 信息素擴散空間模型圖Fig.4 Pheromone Diffusion Space Model Diagram

按照此改進方式，能夠提高距離較近的不同螞蟻之間的信息交流和協作，顯著提高算法的收斂速度和精度。

3.2.3 強制刺激策略

蟻群算法很容易在迭代中期陷入停滯而無法得到最優解，為了能讓算法能夠在陷入停滯后再次啟動開始搜索，對信息素迭代公式做如下改進。

其中，α1=0.5，α2=0.8。

假設在迭代次數達到T時種群的個體不再發生變化，此時強制刺激即改變α(t)，促使整個蟻群跳出局部最優解。除此之外，為了讓算法能夠區分優質、次優以及其他路徑，改進其信息素變化量公式：

其中，不同迭代次數下的路徑信息素增量不同，且路徑總長度與當前最短路徑Lbest的差越小，其信息素增量越大，越容易被選擇。此改進能夠區分不同路徑的優劣程度，得到更多優質個體加快算法收斂。強制擴散算法的整體流程圖，如圖5所示。

圖5 DFACO算法流程圖Fig.5 DFACO Algorithm Flow Chart

4 實驗驗證與結果分析

假設存在四個不同野外地形需要用到運輸機器人從野外山地某一點（START）到另外一點（GOAL）搬運物資，將四個不同地形空間統一分成S∈[20×20]m2的區域，四個地形中搬運物資的起始和到達位置都不同，需要在不觸碰障礙物的情況下以最快的時間將物資送達目的地保證部隊的正常運作。選取擴散強制蟻群算法（DFACO）、傳統蟻群算法、遺傳算法、螢火蟲算法求解計算，設蟻群數量N=200，最大迭代次數tmax=100，其他參數，如表1所示。

表1 參數數值表Tab.1 Parameter Value Table

根據表1和上述文字中的參數設定，將四個不同地形的情況帶入到四種算法中求解，得到的最終結果，如圖6所示。

圖6 四種野外地形在四種算法下的運輸機器人路徑圖Fig.6 The Path Map of the Transportation Robot Under Four Algorithms in Four Wild Terrains

根據四種不同情況下四種算法計算出的越野運輸機器人的路徑曲線可以看到，DFACO算法得到的線路更短且路徑更為的平滑連貫，相對于改進前的ACO算法，能夠大幅度節省運輸機器人運輸路程中所花費的時間，其他的幾種算法在不同的情況下表現不一。四種算法得到的最終的路徑長度、迭代時間、粒子收斂率登結果，如表2，表3所示。

表2 三種基礎算法的結果對比表Tab.2 Comparison Results of the Three Basic Algorithms

表3 ACO和DFACO改進效果對比表Tab.3 ACO and DFACO Improvement Effect Comparison Table

圖7 情況1下四種算法迭代對比圖Fig.7 Comparison of Four Algorithm Iterations in Case 1

根據表2和表3中的數據，對于四種情況下的越野運輸機器人路徑尋優問題，DFACO算法表現出了更好的性能和適應性，在四種情況下收斂速度和收斂精度以及收斂率相比于傳統ACO算法都有了明顯提升。針對情況1，四種算法的搜索迭代過程，如圖6所示。根據圖6迭代圖中算法迭代情況可知，改進后的DFACO迭代時間更短且能夠得到更優結果，能夠為越野運輸機器人快速提供最佳運輸路徑并滿足特殊情況下的快速機動能力和物資運輸的要求。

5 結語

針對越野運輸機器人運輸工件路徑優化問題，提出了一種擴散強制蟻群算法（DFACO），先用信息素極值策略給出信息素上限防止算法停滯，其次采用信息素擴散策略增加較近螞蟻之間的聯系和協作加快算法收斂，再結合強制刺激策略，通過改變信息素增量公式刺激陷入停滯后的蟻群讓算法擺脫局部最優，提高算法的搜索范圍和粒子多樣性，最后分別用擴散強制蟻群算法、傳統蟻群算法、遺傳算法、螢火蟲算法求解四種不同地形的野外運輸實例，證明了提出算法的有效性，該算法能夠快速準確的為越野運輸機器人提供運輸路徑，降低運輸時間提高工作效率為企業創造更多的收益，對該問題有良好的適應性，下一步將嘗試用其他優化算法與該算法融合進一步提升算法的性能。