基于方向指引的蟻群算法機器人路徑規劃

摘 要：針對蟻群算法收斂速度慢、折點多、路徑長等問題，提出了一種基于方向指引的蟻群算法。該算法通過引入向量夾角，重新構造了螞蟻轉移概率，提高了算法的收斂速度且路徑長度更短；算法同時融合了插點策略，進一步對生成的路徑進行優化，縮短了路徑長度，減少路徑折點數，使路徑更加平滑。最后，經實驗驗證，提出的算法在收斂次數和路徑折點數方面有明顯優化效果。在仿真柵格地圖中，平均收斂次數減少了68%，路徑平均折點數減少了42%，平均路徑長度減少了8%。

關鍵詞：路徑規劃； 機器人； 蟻群算法； 轉移概率； 插點策略

中圖分類號：TP393.04 文獻標志碼：A

文章編號：1001-3695（2023）03-022-0786-03

doi： 10.19734/j.issn.1001-3695.2022.07.0397

Ant colony algorithm for robot path planning based on direction guidance

Zhao Zengxu， Liu Xiangyang， Ren Bin

（College of Mechanical Engineering， Shijiazhuang Tiedao University， Shijiazhuang 050043， China）

Abstract：This paper proposed an ant colony algorithm based on directional guidance to address the problems of slow convergence， many folding points， and long paths. The algorithm also incorporated the interpolation strategy to further optimize the generated paths， shortened the path length， reduced the number of path folds， and made the path smoother. Finally， the experimental verification shows that the algorithm has obvious optimization effect in terms of convergence times and path folding points. In the simulated raster map， the average number of convergence are reduced by 68%， the average number of path folding points are reduced by 42%， and the average path length is reduced by 8%.

Key words：path planning; robot; ant colony algorithm; transition probability; insertion strategy

路徑規劃是機器人移動技術中的重要組成部分，是指在一定環境條件和性能指標下，為機器人尋找一條從起始點到目標點的最優或次優的安全無碰撞路徑［1］。國內外學者對路徑規劃問題做了大量研究，常用的路徑規劃算法有A算法［2］、RRT算法［3］、蟻群算法［4］、Dijkstra算法［5］、遺傳算法［6］等。蟻群算法（ant colony optimization，ACO）是由意大利學者Dorigo、Maniezzo和Colorni等人于20世紀90年代初期提出的一種啟發式隨機搜索算法［7］。蟻群算法具有魯棒性強和適應強等優點，但也存在收斂速度慢和易出現局部最優解等問題。針對這些問題，文獻［8］提出了勢場跳點蟻群算法，將蟻群算法與跳點策略進行融合，引入勢場力的思想，使規劃的路徑更加平滑，提高了算法的搜索效率；文獻［9］提出一種改進的蟻群算法，通過擴大螞蟻的視野范圍，改進概率函數，提高了蟻群算法的路徑尋優效果和搜索效率；文獻［10］將柵格地圖劃分為三個不同區域并分配不同的初始信息素值，改進了螞蟻轉移概率，加快了算法的收斂速度，提高了路徑的平滑性和導向性；文獻［11］通過引入迭代閾值，提高了算法的搜索能力，避免出現停滯現象。

本文針對蟻群算法收斂速度慢、規劃的路徑折點多、路徑長等問題，提出了一種基于方向指引的蟻群算法（ant colony algorithm for direction guidance，DG-ACO），算法中引入向量夾角，重新構造螞蟻的轉移概率，使螞蟻在做路徑選擇時更傾向于目標點的節點，以此提高蟻群算法的收斂速度，優化路徑長度。在此基礎上融合插點策略［12］對路徑作進一步優化，對于不存在障礙物的兩個或多個節點之間可直接生成路徑，以此減少折點數，縮短路徑長度。最后，通過仿真實驗對本文算法的有效性和可行性進行驗證。

1 傳統蟻群算法

蟻群算法是一種源于自然界的仿生進化算法，其主要思想是螞蟻在尋找食物過程中會在行走的路徑上留下信息素，后來的螞蟻會根據路徑上信息素的強度來選擇下一步所要移動到的路徑［13］，選擇該路徑的概率與信息素的強度成正比，選擇該路徑的螞蟻越多，此路徑上的信息素強度越高，從而形成正反饋機制，最終可以找到最短路徑。

傳統蟻群算法轉移概率［14］如下：

其中：τij（t）為路徑（i，j）上的信息素強度；ηij（t）為啟發信息值；α為信息啟發因子；β為期望啟發因子；Jk（i）為螞蟻k下一步允許選擇的節點。

信息素更新［15］公式如下：

其中：ρ為信息素的蒸發系數；Δτij為路徑（i，j）上的信息素增量；Q為信息素增強系數；Lk為第k只螞蟻本次尋路的路徑長度。

2 改進蟻群算法

2.1 改進螞蟻轉移概率

在傳統的蟻群算法中，采用當前節點到下一節點距離的倒數作為啟發信息［16］，即ηij=1dij。本文根據向量夾角構造了一種指引函數，提出一種新的啟發信息計算方法。

下式為新的啟發信息計算方法：

其中：θ為當前節點與目標節點和下一步可選擇節點構成的夾角；（xi，yi）為當前節點坐標；（xk，yk）為鄰域節點坐標；（xG，yG）為目標節點坐標;ecos θ為指引函數，θ∈［0，π］。指引函數與向量夾角的函數關系如圖1所示（圖中橫軸為角度，縱軸為指引函數值）。由圖可知，指引函數值隨向量夾角的增加而減小，即螞蟻在做路徑選擇時更傾向于選擇偏向于目標點的路徑。

改進后的蟻群算法轉移概率如下：

螞蟻移動至下一節點的路徑選擇如圖2所示。

假設螞蟻位于A節點，B和C節點為螞蟻可選擇移動的兩個鄰域節點。∠GAC為θ1，∠GAB為θ2，θ2＞θ1。根據改進后的轉移概率，螞蟻選擇節點C時的啟發信息值大于節點B的啟發信息值，即ηC＞ηB，所以螞蟻在做路徑選擇時，螞蟻選擇節點C的概率大于節點B的概率。改進后的啟發信息計算方法使螞蟻做路徑選擇時更具目的性，更傾向于選擇向量夾角較小的節點。

2.2 插點策略進行路徑平滑優化

插點策略可以優化任意兩點之間最短路徑的問題［17］，其原理如圖3所示。A→B→C→D為原路徑長度，以A點為起點，沿路徑A→B→C→D每次移動一個步長u，若在此路徑上尋找到一個節點C，連接A、C生成路徑A→C，可替換路徑A→B→C生成新路徑。若尋找到節點D時，假設AD之間存在障礙物，則AD不能直接生成路徑，所以路徑A→C→D為新生成的路徑，路徑長度比路徑A→B→C→D更優。

本文對改進蟻群算法生成的路徑通過插點策略進行路徑平滑優化，刪除冗余節點［18］，縮短路徑長度。路徑平滑優化步驟如圖4所示。其中虛線為優化前生成的路徑，實線為優化后的路徑。

a）記錄路徑中的起點、終點、拐點。如圖所示，原路徑為S→a1→a2→a3→a4→a5→a6→G。

b）在路徑S→a1→a2→a3→a4→a5→a6→G上，以S點為起點，以一個節點為步長，進行插點策略。每進行一次插點，判斷兩節點連線之間是否有障礙物：（a）若有障礙物，以此節點為一次插點的結束點，生成一段新的路徑，并以此節點為起點進行下一次插點策略；（b）若無障礙物，繼續遍歷路徑，直至遍歷整條路徑，完成路徑平滑優化。

c）當插點策略遍歷路徑所有節點時，算法結束，生成新的路徑。新生成的路徑為S→a1→a6→G。

2.3 算法步驟

DG-ACO算法步驟如圖5所示。

a）將參數進行初始化。

b）螞蟻從起始點出發，按照改進后的轉移概率選擇路徑。

c）對移動到的節點進行局部信息素更新，并更新禁忌表。

d）判斷螞蟻是否到達目標點：若螞蟻未到達目標點，執行步驟b），繼續進行下一節點的選擇；若螞蟻到達目標點，則執行步驟e）。

e）記錄本次循環中的最優路徑，并進行全局信息素更新。

f）判斷是否達到最大迭代次數：若未達到最大迭代次數，執行步驟b）；若達到最大迭代次數，執行步驟g）。

g）對輸出的路徑使用插點策略進行優化，并輸出優化后的路徑。

3 仿真與實驗結果分析

為了驗證本文所提出的DG-ACO算法的有效性，在MATLAB 2019b平臺上對ACO算法、GACO算法［16］和本文DG-ACO算法，在20×20和30×30的柵格地圖中進行了仿真實驗，并對三種算法的仿真結果進行了對比分析。

圖6分別為ACO、GACO和本文算法在20×20的柵格地圖中的尋路結果。圖7分別為ACO、GACO和本文算法在30×30的柵格地圖中的尋路結果。機器人起點位置位于左下角，終點位置位于右上角；黑色柵格表示障礙物，白色柵格表示可移動區域。算法參數如表1所示。

對表2和3的仿真數據分析可知：

a）在20×20的柵格地圖中ACO算法收斂速度較慢、路徑折點數較多；GACO算法相比較ACO算法在路徑長度、收斂速度和路徑折點數上均有一定的優化效果，但并未達到比較理想的效果；而本文提出的DG-ACO算法9次就達到了收斂狀態，且路徑長度和路徑折點數均優于其他兩種算法。

b）當柵格地圖增大至30×30時，ACO算法的尋路結果中，路徑折點數明顯增多，由11增大至28，其原因是隨著地圖環境的增大，ACO算法在尋路時對周圍柵格的探索性更強，但是算法尋路的目的性更弱，導致最終的路徑折點較多；GACO算法的收斂次數和路徑折點數也均有明顯增大，相比ACO算法已有比較明顯的優化效果；本文DG-ACO算法收斂次數僅由9增大至11，路徑折點數為6。

經分析本文改進蟻群算法的轉移概率能夠提高算法收斂速度，同時保證算法具有一定的多樣性，且在更大的地圖環境中體現了更好的適應性，在保證擁有較快收斂速度的同時，依然擁有較高的路徑平滑度，路徑長度也具有一定的優化效果。

為了進一步驗證本文算法的收斂性能，在30×30的柵格地圖中進行了10次仿真實驗，并記錄了三種算法的收斂次數和路徑長度，如圖8所示（圖中橫軸為實驗次數，縱軸為路徑長度）。ACO算法收斂次數平均值為61，平均路徑長度為61.882 5；GACO算法收斂次數平均值為29.2，平均路徑長度為48.304 9；本文算法收斂次數平均值為11.2，平均路徑長度為42.805 5。通過對實驗結果分析可知，本文提出的DG-ACO算法相比ACO和GACO收斂速度更快，同時保證路徑長度更短，在較大的地圖環境中具有更強的適應性。

為了驗證本文算法具有較優的全局搜索性能，將本文算法與其他已有的改進算法在30×30的柵格地圖中進行實驗分析對比，實驗結果如表4所示。通過對表4數據的分析可知，在30×30的柵格地圖中本文算法在路徑長度、收斂次數、路徑折點性能方面均優于其他改進算法，尤其在路徑折點數和收斂次數方面擁有較大的優化效果，驗證了本文所提算法擁有較好的全局搜索性能。

4 結束語

本文提出了一種基于方向指引的蟻群算法機器人路徑規劃，該算法通過引入向量夾角構造指引函數，改進蟻群算法的轉移概率，目的是使螞蟻更傾向于選擇偏向于目標點的路徑，加快算法的收斂速度以及縮短所生成路徑的長度，并且對所生成的路徑采用插點策略優化，縮短路徑長度，減少路徑轉折點，提高路徑平滑性。最后，通過仿真實驗驗證，本文算法與ACO算法相比平均收斂次數減少了68%，路徑平均折點數減少了42%，平均路徑長度減少了8%。將本文算法與其他改進算法對比分析可知，本文算法在路徑長度、收斂次數、路徑折點數上均優于其他算法，驗證了本文算法具有較好的全局搜索性能。

本文算法只是針對在已知靜態環境下的機器人最優路徑規劃的問題，并未解決動態環境下機器人緊急避障的問題。在未來的研究工作中，所提出的算法不僅可以為機器人規劃最優路徑，同時針對復雜多變的動態環境可以實現緊急避障，使機器人更適用于現實生活的環境。

參考文獻：

［1］羅德林， 吳順祥. 基于勢場蟻群算法的機器人路徑規劃［J］. 系統工程與電子技術， 2010，32（6）：1277-1280. （Luo Delin，Wu Shunxiang. Ant colony optimization with potential field heuristic for robot path planning［J］. Systems Engineering and Electronics， 2010，32（6）：1277-1280.）

［2］Lai Xin，Li Jiahe，Chambers J. Enhanced center constraint weighted A algorithm for path planning of petrochemical inspection robot［J］. Journal of Intelligent amp; Robotic Systems， 2021，102（4）：1-15.

［3］Gan Yi，Zhang Bin，Ke Chao，et al. Research on robot motion planning based on RRT algorithm with nonholonomic constraints［J］. Neural Processing Letters， 2021，53（4）：3011-3029.

［4］Rivero J，Cuadra D，Calle J，et al. Using the ACO algorithm for path searches in social networks［J］. Applied Intelligence， 2012，36（4）：899-917.

［5］Dudeja C，Kumar P. An improved weighted sum fuzzy Dijkstra’s algorithm for shortest path problem（iWSFDA）［J］. Soft Computing， 2022，26（7）：3217-3226.

［6］Kapanoglu M，Alikalfa M，Ozkan M，et al. A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time［J］. Journal of Intelligent Manufacturing， 2012，23（4）：1035-1045.

［7］Lee J. Heterogeneous-ants-based path planner for global path planning of mobile robot applications［J］. International Journal of Control，Automation and Systems， 2017，15（4）：1754-1769.

［8］馬小陸，梅宏. 基于改進勢場蟻群算法的移動機器人全局路徑規劃［J］. 機械工程學報，2021，57（1）：19-27. （Ma Xiaolu，Mei Hong. Mobile robot global path planning based on improved ant colony system algorithm with potential field［J］. Journal of Mechanical Engineering， 2021，57（1）：19-27.）

［9］徐菱，付文浩，江文輝，等. 基于16方向24鄰域改進蟻群算法的移動機器人路徑規劃［J］. 控制與決策， 2021，36（5）：1137-1146. （Xu Ling，Fu Wenhao，Jiang Wenhui，et al. Mobile robots path planning based on 16-directions 24-neighborhoods improved ant colony algorithm［J］. Control and Decision， 2021，36（5）：1137-1146.）

［10］袁福龍，朱建平. 基于改進蟻群算法的移動移動機器人最優路徑規劃［J］. 現代制造工程，2021（7）：38-47. （Yuan Fulong，Zhu Jianping. Optimal path planning of mobile robot based on improved ant colony algorithm［J］. Modern Manufacturing Engineering， 2021（7）：38-47.）

［11］王曉燕，楊樂，張宇，等. 基于改進勢場蟻群算法的移動機器人路徑規劃［J］. 控制與決策，2018，33（10）：1775-1781. （Wang Xiaoyan，Yang Le，Zhang Yu，et al. Robot path planning based on improved ant colony algorithm with potential field heuristic［J］. Control and Decision， 2018，33（10）：1775-1781.）

［12］Sathyaraj B M，Jain L C，Finn A，et al. Multiple UAVs path planning algorithms：a comparative study［J］. Fuzzy Optimization and Decision Making， 2008，7（3）：257-267.

［13］Liu Jianhua，Yang J，Liu Huaping，et al. An improved ant colony algorithm for robot path planning［J］. Soft Computing，2017，21（19）：5829-5839.

［14］Wang Junfeng，Liu Jihong，Zhong Yifang. A novel ant colony algorithm for assembly sequence planning［J］. The International Journal of Advanced Manufacturing Technology， 2005，25（11）：1137-1143.

［15］Chen Xiong，Kong Yingying，Fang Xiang，et al. A fast two-stage ACO algorithm for robotic path planning［J］. Neural Computing and Applications，2013，22（2）：313-319.

［16］王猛，邢關生. 基于改進蟻群算法的機器人路徑規劃［J］. 電子測量技術，2021，43（24）：52-56. （Wang Meng，Xing Guansheng. Robot path planning based on improved ant colony optimization［J］. Electronic Measurement Technology，2021，43（24）：52-56.）

［17］董箭，初宏晟，盧杬樟，等. 基于A算法的無人機路徑規劃優化模型研究［J］. 海洋測繪，2021，41（3）：28-31. （Dong Jian，Chu Hongsheng，Lu Yuanzhang，et al. UAV path planning optimization model based on A algorithm［J］. Hydrographic Surveying And Charting，2021，41（3）：28-31.）

［18］張志文，張鵬，毛虎平，等. 融合改進A算法和動態窗口法的全局動態路徑規劃［J］. 電光與控制，2021，28（9）：39-43. （Zhang Zhiwen，Zhang Peng，Mao Huping，et al. Global dynamic path planning combining improved A algorithm with dynamic window approach［J］. Electronics Optics amp; Control， 2021，28（9）：39-43.）

收稿日期：2022-07-05；修回日期：2022-09-08 基金項目：河北省教育廳青年基金資助項目（QN2019232）;河北省自然科學基金資助項目（E2019210299）；河北省大型結構健康診斷與控制重點實驗室開放課題（KLLSHMC1909）

作者簡介：趙增旭（1986-），女，河北石家莊人，講師，博士，主要研究方向為機器人導航與控制、智能制造；劉向陽（1995-），男（通信作者），河南周口人，碩士，主要研究方向為機器人導航與控制（2503786241@qq.com）；任彬（1982-），女，河北石家莊人，副教授，碩導，主要研究方向為機械設備狀態檢測、智能故障診斷與預測、機器人控制．