基于改進蟻群算法機器人路徑規劃★

邢協泓， 黃坤榮， 唐德文

（1.南華大學機械工程學院， 湖南 衡陽 412000；2.南華大學核設施應急安全技術與裝備重點實驗室， 湖南 衡陽 412000）

0 引言

隨著社會的發展，機器人在生活、工業生產等方面的應用越來越廣泛。機器人進行自由運動的必要條件是其具備路徑設計功能，而路徑規劃的好壞關鍵在路徑搜索算法的選取上[1]。目前對于機器人路徑規劃提出了多種算法，如：A*算法、D*算法、人工勢場法、人工魚群算法[2]等，與其他算法相比，蟻群算法具有信息正反饋、自組織、并行等特點，所以在路徑規劃中應用更為方便廣泛，但在一些復雜的環境中，傳統的蟻群算法也存在一定的不足，如彎折多，收斂速度慢等。隨著環境復雜性的提高，對算法的要求也會更高，單一算法往往不能尋找出最優路徑。文獻[3]將傳統螞蟻群體計算和D*算法結合，通過優化原始D*算法的啟發式函數和子節點的方法，用傳統蟻群計算的評價方法來改善計算，從而增強了高效性和適應性;文獻[4]融合蟻群算法和遺傳算法，運用遺傳算法的快速搜索對螞蟻群體計算初始信息素加以處理，避免進入局部優化，并且縮短了尋找路徑時間;文獻[5]提出了結合Dijkstra 方法和蟻群方法來解決MRPP 問題，實現在最短時間內獲得全局最優路徑的目標。

蟻群算法是最先提出的模擬蟻群覓食活動的智能模擬算法，該算法由于具有魯棒性、正反饋等特點，易與其他算法相結合并運用到機器人路徑規劃中[6]。本文中提出將單一蟻群算法與Dijkstra 算法相互融合，利用Dijkstra 算法的快速全局查詢能力，對單蟻群算法的信息素進行處理，并利用Dijkstra 算法實現節點選擇，再用蟻群算法進行優化。通過用數學軟件MATLAB 模擬，對融合方法和傳統算法進行比較，實現優化后的方法通過更短的迭代時間達到了最佳路徑設計。

1 傳統路徑規劃算法

1.1 蟻群算法

蟻群計算，是尋求優化途徑的一個模擬進化算法[7]，是依據螞蟻覓食的基本原理而得到。螞蟻在行走的步驟中產生信息素，用以記錄自己的步行路程。

在構建路徑的每一步中，使用輪盤賭法來選定下一次到達的節點。其節點的選取方程是：

式中：i、j 分別為起點和終點；α 為信息素因子；β 為啟發函數因子；τij（t）為時間t 時由i 到j 的信息素濃度；ηij（t）=1/dij（t）是兩點i、j 路徑距離的倒數；Aallowed，k為尚未訪問過的節點的集合。

其中dij表示i、j 之間的歐式幾何距離[8]，如式（2）所示：

搜索時，由于螞蟻種類的增多，路徑中的信息素含量會相應提高，因為信息元素帶有波動性，信息元素含量會隨著持續時間的延長而減少。

其表達式為：

式中：τij（t+1）為經過一次更新后路徑上的信息素濃度；ρ 為信息素揮發系數且0<ρ<1；為第k 只螞蟻在路徑（i，j）上的信息素增量；N 為蟻群總數量；Q為信息素增量系數；Lk為第k 只螞蟻搜索經過的路徑長度。

1.2 Dijkstra 算法

Dijkstra 算法是一種經典的求解最短路徑的算法，用于計算一個節點到其他各個不相關節點的最小移動價值[9]。

在路徑規劃中，先假定起點為s，再引入S 和U。S記錄已求出最短路徑的頂點和相應的最短路徑長度的集合，U 記錄還未求出最短路徑的頂點以及該頂點到s 的距離的集合。如果所找出的點到一節點的路不通，則距離視為∞。

Dijkstra 算法在節點的選取過程中實質上從某個節點出發，然后沿著地圖的邊通過路徑到達另一節點，再選取在每條邊上權重之和最小的路徑[10-12]，將相鄰的下一個節點進行標記，比較起點到下一節點的距離大小，篩選出離起點較短的節點，刪除較長的節點。在改進的算法中，只需要將障礙物的各頂點加入到U 中，這樣既縮短了搜索時間，又使得搜索更具有導向性，路徑更短。

2 改進蟻群算法路徑規劃

本文改進蟻群算法的基本思想是搜索初期使用Dijkstra 算法重新進行節點的選取，使其將搜索目標向最優解靠攏，再用蟻群算法優化節點尋找最優路徑，防止機器人離障礙物太近。

2.1 路徑規劃環境建模

環境建模的方法有柵格法、拓撲法、可視圖法等[13]。由于柵格法直觀且建模容易，本文采用柵格法進行環境建模。圖1 是柵格法的基本模型，20 cm×20 cm 格子表示機器人所處總環境，黑色格子表示環境中的障礙物，沒有障礙物的自由移動環境用白色格子表示每一格為1 cm。在建模過程中，可能存在不足一格的現象，應進行膨化處理，不足一格用一格代替[14]。

圖1 柵格法環境建模

在柵格圖中坐標表示為：

式中：b 為柵格邊長；mod 為取余；ceil 為取最小整數；xi，yi為每個柵格的坐標位置[15]。

2.2 節點選取

機器人在尋找最短路徑時，首先要越過障礙物，文獻[16]中介紹了越過圓形障礙物的可達路徑，即從起點經過圓的切線，如圖2 所示。

圖2 經過圓形障礙物可達路徑[16]

基于此，本文改進算法引入切點，在柵格法建模的環境中，將障礙物的頂點看成切點，如圖3 所示，正方形ABCD 為障礙物，起點為O，終點N；從起點到終點，按照圓形障礙物可達路徑方式，越過柵格環境有4 條路徑，分別為O→B→N；O→C→N；O→A→N；O→D→N。但考慮無法直接越過障礙物，機器人會選擇B、C 作為中間節點。

圖3 經過柵格環境障礙物可達路徑

將改進后的可達路徑與傳統算法進行比較，如圖4 所示。

圖4 改進與傳統路徑比較

圖4 所示，OMN 為傳統路徑，OCN 為改進路徑，OE+EC>OC，CF+FN>CN，EC=MF，CF=EM?OM+MN>OC+CN，改進后的路徑比傳統路徑更短且更優。

由圖4 對比可知，機器人會選擇走經過B、C 兩點的路徑。若選擇經過A、D 兩點，則需要繞過障礙物，路徑的權重之和變大，則Dijkstra 算法的S、U 表中將刪除A、D 兩點。

2.3 節點優化

經過多個障礙物時，先將所有障礙物的端點進行標記加入到U 表中，用Dijkstra 算法選擇出權值和最小的路徑，而當離障礙物很近時，直接用Dijkstra 算法進行節點選擇時會讓路徑可行性降低，改用蟻群算法進行路徑更優化選擇。

優化原則：在柵格法建模的環境中，當螞蟻離障礙物的水平距離少于一個單位時，用蟻群算法選擇水平點，如圖5 所示。

圖5 蟻群算法優化原理

設起點坐標O（x0，y0），B 點坐標（x1，y1），則A 點坐標為（x0，y1），將式（3）進行更新，得到：

更新后的啟發式函數計算如式（8）所示：

如圖5 所示，障礙物在起點右方，用優化后的算法更新后得到A 點。B 點為Dijkstra 算法找出的權值最小的點，A 為蟻群算法優化找出的節點。在三角形OAB 中，OB 為斜邊，OA 為直角邊，直角邊比斜邊短，權重更小，A 為最優點，將B 點從U 表中刪除，A點放入U 中。

用蟻群算法優化更新后的距離更短，路徑更優，同時也避免了機器人在移動的過程中與障礙物發生碰撞，實現了路徑最優的要求。

2.4 改進蟻群算法

在未知環境中，將蟻群算法和Dijkstra 算法相融合，使機器人在路徑規劃中，初期使用Dijkstra 算法將搜索目標向最優解靠攏，再用蟻群算法尋找最優路徑。機器人遇到障礙物時，利用融合算法將切點作為節點放入S 進行搜索，選擇距離起始點最近的切點，若切點離障礙物過近，再將切點平移后的點移到U中，隨后更新信息素以及迭代次數，輸出最優路徑，其算法流程如圖6 所示。

圖6 融合算法流程

3 仿真結果與討論

本文采用MATLAB_R2022a 進行仿真，對機器人在建立的已知地圖上進行實驗，分別運行傳統蟻群算法以及本文改進融合蟻群算法，從最短路徑長度、迭代次數、運行總時間這三方面分析比較，實驗環境建模如圖1 所示，設置的蟻群初始參數如表1 所示，起點為（0.5，19.5），終點為（19.5，0.5）。

表1 蟻群算法初始參數

仿真結果中，圖7-1 為傳統蟻群算法路徑規劃，圖7-2 為改進融合蟻群算法路徑規劃，對比可知，傳統算法路徑軌跡有14 個彎折點，改進后的算法有7個彎折點，融合后的蟻群算法比傳統蟻群算法路徑彎折點減少了50%，路徑更為平穩。

圖7 傳統與改進算法路徑規劃對比

圖8-1 為傳統蟻群算法收斂曲線，迭代次數在50 次趨于平穩，最短路徑為30.38 cm；圖8-2 為改進融合蟻群算法收斂曲線，可知最小路徑迭代到32 次時趨于平穩，最短路徑為26.21 cm。迭代最短路徑由30.38 cm 降到26.21 cm，迭代次數由50 次降到32次，可見改進后的算法路徑更優，搜索效率更高。

圖8 傳統與改進算法收斂曲線對比

綜上，數據對比如表2 所示，傳統蟻群算法的最短路徑為30.38 cm，迭代次數為50 次，而經過優化融合后的蟻群算法的最短路徑為26.21 cm，迭代次數為32 次，減少了40%的路徑長度，同時改進后的算法也增加了收斂效率，相比于傳統蟻群算法增加了37%，優化后的算法執行時間大大縮短，搜索效率更高，路線彎折更少。

表2 數據對比

4 結語

本文采用了柵格法環境模型，面對蟻群算法中收斂速度慢且極易陷入局部求解的難題，提出了融合Dijkstra 算法與蟻群算法的方法：搜索初期用Dijkstra算法引入切點向最優解靠攏，后期用蟻群算法優化節點選擇。實驗表明，在同一環境下改進后的算法路徑長度縮短了14%，收斂速度提高了37%，彎折點減少了50%，在路徑長度、迭代次數、搜索時間、彎折點等方面均優于傳統蟻群算法。利用MATLAB 仿真證實了融合后的算法可以進一步提高收斂速率，并使得搜索的路徑更有引導性，相比于常規的蟻群方法，經過改進后的方法路徑彎折更少，易獲得最優的路徑。