基于變步長蟻群算法的移動機器人路徑規劃

趙高杰魯守銀袁魯浩

(山東建筑大學 信息與電氣工程學院，山東 濟南 250101)

0 引言

機器人路徑規劃一直是機器人領域的關鍵技術之一，其是指移動機器人在特定環境中，找出一條連接起點與終點的最佳路徑[1]。路徑規劃算法具有代表性的有A*(A-Star Search Method， A*)法[2]、快速擴展隨機樹(A Rapidly Exploring Random Tree，RRT)法[3]、人工勢場法[4]、神經網絡算法[5]等。除此之外，還有大量仿生算法，如粒子群算法[6]、遺傳算法[7]、蟻群算法[8]等。其中，蟻群算法的應用最廣泛，主要是因為其具有正反饋策略、尋優效果好等優點。

蟻群算法是根據螞蟻搜尋食物行為設計提出的，已證明具有很多優點，但同時也具有穩定性不強、容易陷入局部收斂等不足。因此，在此基礎之上，學者們設計了諸多不同的蟻群算法改進方案。2021年，SANGEETHA 等[9]引入了一種基于能量優化的蟻群算法，考慮到規劃的路徑與消耗的能量是一一對應的，改進了增益函數的信息素增強機制，減少了動態場景中路徑規劃過程消耗的總能量，從而起到路徑優化的效果。然而，其本質仍為傳統的蟻群算法，僅映射了問題，其收斂性和最優解情況仍有待提升。而MASOUMI 等[10]則考慮到地理信息系統中用戶的需求，改進了蟻群算法目標函數，可適應不同優先級的多目標優化問題。這種方法有利于提升用戶的體驗性， 但其迭代次數仍較多。ABDULAKAREEM 等[11]則引入了基于概率路線圖和三次樣條插值的改進蟻群算法，分別采樣目標點、構造路線圖，隨后使用蟻群算法優化，并使用三次樣條插值進行平滑并降低路徑長度從而獲得最優路徑，然而由于環節較多，因此計算量較大、搜索時間長。高茂源等[12]提出了一種基于環境改進的蟻群算法，其基于柵格環境選擇機器人的步長，改進信息素揮發因子，使其尺寸分布服從高斯分布，從而加快了改進后蟻群算法的收斂效率，但對原始數據的分布具有較嚴格的要求，從而其應用場合較為有限。此外，徐玉瓊等[13]為改進傳統蟻群算法穩定性不足的問題，設計了一種自適應蟻群算法，能夠依據算法中解的分布情況，動態地更新調節信息素；同時在多步長選擇模型中選取最佳步長，提升算法全局搜索性能，但不足在于沒有考慮移動機器人實際工作環境的高度因素。

綜上所述，目前對改進蟻群算法的研究仍存在未觸及蟻群算法內部環節和本質、應用場合受限、未考慮移動機器人實際工作環境等問題。針對上述問題，文章基于移動機器人實際的工作環境，提出了一種改進的變步長蟻群算法，主要設計了一種不定步長的選擇模型，同時針對移動機器人實際運行時可能出現坡度大的環境，在啟發函數中引入高度信息。另外，改進了算法中信息素更新模型，采用動態揮發系數，以提升算法尋優效率。

1 移動機器人路徑規劃的環境建模

機器人路徑規劃問題指的是在特定的約束下，搜尋出一條最佳路徑，由式(1)表示為

式中f(p)為路徑的目標函數；ps、po分別為起始點和目標點；Γ(ps，po)為起終點之間的路徑節點集合。

機器人路徑規劃中常見的建模方法主要有柵格地圖、三維仿真地圖、拓撲圖等。其中，柵格地圖容易構建且易于維護，因此選定柵格圖作為研究移動機器人建模的環境。柵格的粒徑由移動機器人的規格決定，其大小必須可以容納移動機器人自由運行且保持柵格邊界與移動機器人一定的安全距離。在柵格圖中用黑色和白色部分分別代表不可行區域和可自由通行區域。為保障移動機器人的工作安全，假定移動機器人工作時不能沿著障礙物邊緣及頂點行走。另外，如果障礙物不足一個柵格時，則將其膨化為一個柵格。

機器人柵格環境模型如圖1 所示，其中黑色區塊為障礙物，白色區塊為機器人可行走的區域。通過設定柵格圖的柵格號從下至上、從左到右都分別遞增。柵格地圖規格為m行n列，柵格號和柵格粒徑分別為N和1，每個柵格的中心點位置坐標(x，y)可由式(2)表示為

圖1 柵格模型圖

式中mod 為取余操作；int 為求整。

2 移動機器人路徑規劃蟻群算法改進

2.1 傳統蟻群算法

蟻群算法是模仿蟻群尋找食物的行動模式而設計的算法。蟻群在搜尋食物時會在路徑上分泌不等的信息素，而信息素的多少跟路徑距離有關。其他的個體則會根據路徑上信息素的濃度做出相應決策，最終蟻群將逐步地聚攏在最短路徑上。

個體在尋優迭代過程中的第t次，由節點i轉移至節點j的概率計算公式由式(3)表示為

式中n為個體序號；i和j分別為當前節點和下一節點；s為所允許的轉移起始節點；allowedi為所允許的點坐標集合；τ為信息素濃度；η為啟發函數；α、β分別為信息素和啟發式預期值；U為個體可搜尋柵格的集合。其中，節點i、j之間的距離d(i，j)由式(4)表示為

而在算法尋優時，環境中信息素更新公式由式(5)和(6)表示為

式中ρ為信息素揮發因子；Q為信息素強度；Ln為序號為n的個體走過的總路程；K為蟻群中個體總數；V為序號為n的個體走過柵格的集合。

2.2 基于傳統蟻群算法的啟發函數優化

傳統蟻群算法中，啟發函數只和路徑長度有關，只能保證距離因素，無法適應真實工作環境中高度不定的情形。因此對啟發函數進行改進，由式(7)表示為

式中v為高度因素，其多元函數形式由式(8)表示為

式中h為環境中柵格的高度矩陣；λ和σ為高度調節常數；hmin、hmax分別為相鄰柵格中與當前柵格的最小、最大高度差，m；C為常數，C＝0.001，保證在最小、最大高度差相等時分母不為零。

2.3 基于傳統蟻群算法的信息素更新機制改進

2.3.1 信息素增量

為更加真實地模擬機器人可能遇到的具有高度起伏的工作環境，加入了高度啟發因素，因此對信息素增量公式做修正，由式(9)和(10)表示為

式中Zn(t)為路徑的綜合指標；Sn(t)為路徑長度，m；Hn(t)為路徑的轉彎次數，路徑的綜合指標越低，說明路徑越平直，路徑的收斂性和優化程度越高。

2.3.2 揮發系數

傳統蟻群算法中揮發系數自始至終都是維持不變的，無法適應實際環境。因此，為提升改進算法的全局性，提出一種自適應策略，在搜索前期增大ρ的值，加快收斂，而在后期減小其值，增強算法全局性。具體公式由式(11)表示為

式中a、b均為常數；ρmax、ρmin分別為揮發系數最大及最小值。

2.3.3 限定信息素范圍

在蟻群算法的優化迭代過程中，設定路徑上的信息素取值由式(12)表示為

通過范圍限制，豐富了結果的多樣性，從而可以提升算法的尋優效率。

2.4 基于傳統蟻群算法的變步長選擇策略改進

傳統蟻群算法中采用的是單步移動的模式，且轉移的方向只能為0°、±45°、±90°、±135°、180°共8個角度。在傳統的單步長移動模式下，其路徑距離更長，且轉折次數也更多。因此，采用變步長移動機制，此時個體在進行移動時不再局限于單步長，且每一步的移動方向可以任意選擇，從而減短路徑距離，此兩種步長模式對比圖如圖2 所示。

圖2 兩種步長模式對比圖

變步長移動機制具體方案為:

先利用改進的蟻群算法搜尋出單步長模式下最佳路徑，如圖2 中的虛線所示，再次對此路徑進行規劃，即將當前柵格與下一柵格直接相連，判斷路徑是否遇到障礙物，若沒有則接著尋找下一個柵格，直至碰撞障礙區域。此時形成的柵格節點連線為最優路徑，如圖2 中實線所示，可以看出變步長選擇策略模式下路徑距離更短且轉折次數更少。

2.5 改進變步長蟻群算法流程

基于算法的相關分析，改進變步長蟻群算法相應的執行流程示意如圖3 所示。

圖3 算法流程圖

其步驟主要為

(1)建立柵格地圖環境，設置算法參數初始值；

(2)設置起始及目標位置，初始化信息素；

(3)采用變步長移動策略，根據式(3)計算轉移概率，得到下一節點坐標。而在本輪迭代結束后，則需要根據式(9)～(11)更新算法中的信息素；

(4)判斷本次迭代是否結束，如果結束繼續執行，否則需要重新計算下一節點坐標；

(5)判斷算法是否超過迭代次數最大值，如果是，則輸出最優路徑，否則繼續下輪迭代。

3 蟻群算法實驗仿真及分析

為了驗證所提出的變步長蟻群算法在機器人路徑規劃上的有效性，通過數學軟件MATLAB 評價改進后蟻群算法在路徑規劃上的可行性和高效性，并與張曉莉等[14]使用的傳統蟻群算法、WANG 等[15]提出的基于粒子群優化 (Particle Swarm Optimization， PSO)改進的蟻群算法進行對比。在仿真測試中，建立了二維柵格地圖[16]，其中柵格環境模型的尺寸為30 m×30 m。實驗中二維柵格地圖的參數設置為:單位柵格長度為1 m、總長30 m，機器人起始坐標為(0.5，0.5)、終點為(29.5，29.5)。

在性能對比實驗的算法參數中，設置個體數目(m值)為50，算法的迭代最大次數為50 次，信息素重要程度因子α、啟發函數重要程度因子β、信息素增加強度系數Q和信息素揮發系數ρ分別設為1、3.2、1.1 和0.6，揮發系數的閾值ρmin和ρmax分別為0.01和0.8。選取hmax＝0.4 m、hmin＝0 m。高度調節因子選為λ ＝0.5、σ ＝0.5。除此之外，3 種算法所設定的其他參數都使用相同的參數設置。

對傳統蟻群算法、PSO 優化蟻群算法以及改進蟻群算法在相同的二維柵格地圖進行仿真測試，所得到的路徑結果如圖4 所示，其中的綠色部分表示柵格上的高度分布情況。而3 種算法在相同的二維柵格地圖路徑規劃過程中的路徑長度、轉彎次數及綜合指標對比結果如圖5～7 所示。

圖4 傳統蟻群算法、PSO 優化蟻群算法和改進變步長蟻群算法在相同二維柵格地圖路徑結果圖

圖5 3 種算法在相同的二維柵格地圖路徑長度對比圖

由圖4～6 可知，傳統蟻群算法及PSO 優化蟻群算法的移動機器人路徑規劃方法的避障能力不足，使得機器人移動過程中產生了一些冗余的路徑，且需要多次迭代才可找出最優路徑，迭代次數達到設定的最大迭代次數時，其最少轉彎次數均＞10 次、最小路徑長度為47 m。相對比之下，由于轉彎方向的任意選擇性，改進變步長蟻群算法規劃所得出的路徑的避障效果較好，路徑較為平直，最優路徑僅需要9 次轉彎，最優路徑長度為44 m，相比于其他二者減小了3 m。

圖6 3 種算法在相同的二維柵格地圖轉彎次數對比圖

若綜合考慮算法的收斂性和效率，如圖7 所示，可發現改進變步長蟻群算法的收斂效率相比于PSO優化蟻群算法提升了72%，比傳統蟻群算法提升了84%。此外，改進變步長蟻群算法的綜合指標相比于傳統蟻群算法減少了33%，比PSO 優化蟻群算法減少了12%，也就是說其路徑規劃的效率和綜合效果是最佳的。

圖7 3 種算法在相同的二維柵格地圖綜合指標對比圖

綜合以上評價指標的實驗結果可以看出，在蟻群算法基礎上提出的基于變步長蟻群算法的移動機器人路徑規劃方法，在路徑長度、轉彎次數及綜合效果等常用的路徑規劃評價指標方面，對比于傳統的蟻群算法和PSO 優化蟻群算法的路徑規劃方法都具有更明顯的優勢。

4 結論

在傳統蟻群算法基礎上，提出了在移動機器人路徑規劃上應用的一種改進變步長的蟻群算法，并對比了傳統蟻群算法及粒子群優化蟻群算法，經過分析得出以下結論:

(1)在蟻群的啟發函數中增加了高度分布函數，表征機器人移動的高度起伏。仿真結果表明，改進變步長蟻群算法對高度函數具有穩定性，規劃出的路徑規避了高度起伏較大的區域，并保證了一定的平直性，其轉彎次數僅為9 次，相對于傳統蟻群算法及PSO 優化蟻群算法提升了約45%。

(2)改進變步長蟻群算法增加了長度和方向的選擇特性，可提供根據環境不同而改變自身步長的搜索模式，總路徑長度相比于其他二者算法減少了約5%。

(3)在收斂性和尋優效率方面，仿真結果表明改進變步長蟻群算法收斂所需的迭代次數僅需8 ～10 次，相比于其他二者減少了5～15 次，路徑綜合指標提升了約30%。