基于改進蟻群算法的移動機器人路徑規劃方法

李燕 季建楠 沈葭櫟 蘇瑞

1 南京信息工程大學 自動化學院,南京,210044 2 南京信息工程大學濱江學院 物聯網工程學院,無錫,214105

0 引言

隨著移動機器人的飛速發展，路徑規劃問題成為移動機器人研究領域的基礎與核心.移動機器人路徑規劃技術是機器人在復雜的環境中，從起點到終點之間無數條搜索路徑里，智能地選擇一條最優路徑或者較優路徑[1].傳統的解決路徑規劃問題的算法主要包括廣度優先搜索( BFS) 、深度優先搜索( DFS) 、Dijkstra 算法和A*的算法.近年來一些研究人員采用仿生智能優化算法解決路徑規劃問題，這些仿生智能優化算法主要包括蟻群算法、遺傳算法、粒子群算法、免疫算法、模擬退火算法、DNA計算方法以及各算法之間的組合優化算法等[2-5].

蟻群算法是一種啟發式的隨機搜索算法，由意大利學者Maniezzo團隊受螞蟻覓食行為的啟發，在1991年首次提出[6].蟻群算法模擬螞蟻合作覓食行為，具有正反饋、高穩健性和并行性、易于與其他算法相結合等優點.但傳統蟻群算法容易出現局部最優解、計算量大、收斂速度慢等問題[7].近年來國內外學者相繼提出了一些改進的蟻群算法.2000年，Stutzle等[8]提出了最大最小螞蟻系統( MMAS)，通過限制路徑上信息素的上下限，在一定程度上避免了陷入局部最優解問題.2018年，張原藝等[9]提出一種改進的多步長蟻群算法，將蟻群每次迭代產生的最優路徑作為引導徑，利用路徑引導搜索策略確定多步長的移動路徑，提高了搜索范圍的多樣性.2018年，占偉等[10]提出改進啟發因子的方法，給定一個初步的引導方向，最終大大增加了算法的時間有效性，減少了算法收斂的時間,保證了最短路徑的搜索方向向著最短目標最優方向進行.2020年，陳勁峰等[11]提出了一種自適應信息素給予機制，提高了蟻群算法的收斂速度和路徑全局優化能力.

針對現有蟻群算法的不足，本文提出了一種用于移動機器人路徑規劃的改進蟻群算法.首先用柵格法進行環境建模，然后通過優化信息素總量增強全局搜索能力，增加搜索的目的性，最后改善啟發式函數來提高狀態轉移概率，以便快速地得到路徑最優解.仿真結果表明改進的蟻群算法在性能指標上有顯著提高.

1 環境建模

機器人環境建模的方法主要有柵格法、構型空間法、自由空間法

等幾種.其中柵格法在機器人的環境建模上應用最多[12].柵格法主要任務是根據環境構建路徑網格圖，基本原理是將機器人的工作環境劃分為許多微小的網格單元，每個網格的規格由機器人的步驟決定.網格由自由網格和障礙網格組成.白色的網格表示自由網格，黑色的網格表示障礙網格.圖1是20×20的網格節點圖，每行的節點數Nx=20和每列的節點數Ny=20.坐標原點定在柵格空間的左下方，定義x軸正方向為從左到右，y軸正方向為從下到上.第1個點的坐標為(0，19)，第2個點的坐標為(1，19)，以此類推.假設S={1,2,3,…,N}是一組節點的數量，第i個節點的坐標為(xi,yi)，從起始點坐標(0，0)開始到終點坐標(19，19)結束.機器人只能在白色的自由網格中移動，需要避開黑色的障礙網格.根據網格的位置，網格可以分為中間網格和邊界網格.對于中間網格，機器人的下一個動作可選擇8個方向.當機器人運動到邊界網格時，它的運動方向需舍去無法到達的方向.

圖1 20×20的節點圖Fig.1 20×20 node graph

2 傳統蟻群算法

蟻群算法是一種群體智能仿生啟發式算法，它通過模擬螞蟻覓食的行為來找到食物源與其蟻巢之間的最佳路徑.螞蟻在通過的路徑上會釋放信息素.通過這些信息素，螞蟻可以彼此交流并最終找到一條起點到終點的最短路徑.在搜索過程中螞蟻會隨機選擇前進的運動方向，信息素在路徑上遺留的越多，對信息素濃度大的路徑選擇的概率就越大，在尋找路徑的過程中蟻群個體之間的協作形成了一種正反饋機制.

在尋找路徑的過程中螞蟻依據路徑上的信息量和啟發式信息計算轉移概率：

(1)

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

(2)

(3)

(4)

(5)

3 改進的蟻群算法路徑規劃

3.1 優化信息素總量

對于傳統的蟻群算法，完成一次完整路徑搜索后所釋放的信息素總量是一個定值.隨著迭代次數的增加,后期路徑上的信息素濃度易積累過高，導致螞蟻一定程度上失去搜索優質解能力，信息素濃度在揮發因子的作用下降低，極可能增加陷入局部最優解的概率.本文提出了對信息素總量Q進行自適應調整的機制，隨著迭代次數的增加Q逐步降低，大大降低陷入局部最優解的概率.方法如下：

(6)

其中Niter表示迭代次數，Nc,iter是當前的迭代數.

3.2 啟發函數的改進

傳統蟻群算法初始階段在路徑上沒有遺留信息素，螞蟻無法根據信息素濃度選擇方向，搜索沒有目的性，不能快速搜索到可行路徑.針對這一問題，本文對迭代搜索的啟發函數進行改進，采用當前節點到下一節點的距離與下一節點到目標節點距離之和的平方來優化啟發函數，使得螞蟻在搜索初期能夠獲得一個引導方向，增加目標節點對下一節點的影響，改進的啟發函數如下：

(7)

(8)

其中djD表示節點j到目標點D的歐式距離.將傳統的dij改為(dij+djD)2，增強了搜索的目的性，降低了陷入局部最優解的概率.

3.3 蟻群算法相關參數

蟻群算法中，參數的選取影響收斂速度和尋優結果，主要涉及的參數有螞蟻數量、信息素揮發系數、啟發因子α與期望啟發因子β、迭代次數.具體分析如下：

1)螞蟻數量.算法中蟻群數量是一個關鍵的參數，蟻群數量過大，搜索路徑上的信息素會趨于相等，無法確定最優路徑；蟻群數量過小，有可能出現早熟，不能獲取全局最優路徑.本文螞蟻數量M設置為50.

2)信息素揮發系數.信息素反映螞蟻搜索進程中積攢的信息量，指導蟻群搜索路徑的方向.隨著蟻群算法迭代的進行，節點上的信息素將逐漸揮發.信息素揮發系數ρ對蟻群算法的收斂速度和尋優能力都有著至關重要的影響.ρ增大信息素揮發加快，蟻群算法的隨機性和搜索能力降低;ρ減小，全局搜索能力提高，但收斂速度也相應減慢.本文信息素揮發系數ρ設置為0.2.

3)啟發因子α與期望啟發因子β.啟發因子α表示路徑上的信息素濃度對整個蟻群的指導作用;期望啟發因子β表示路徑相關信息對蟻群的影響.α的大小決定螞蟻選擇之前路徑的概率大小，β的大小決定了算法的搜索效率.本文啟發因子α設置為0.9、期望啟發因子β設置為4.

4) 最大迭代次數.迭代次數主要根據執行的收斂軌跡來調整，迭代次數過小，會導致算法未收斂就已結束，過大會造成資源浪費.本文迭代次數設置為200.

3.4 路徑規劃步驟

為了實現改進的路徑規劃算法，本文對算法整體流程進行了設計.路徑規劃流程如圖2所示，具體步驟如下：

圖2 路徑規劃流程Fig.2 Path planning

1)利用柵格法進行環境建模；

2)對最大的迭代數、螞蟻個數,以及其他參數如α,β,ρ等進行初始化；

3)將所有螞蟻放在起點處，計算啟發信息；

4)根據狀態轉移概率方程確定要選擇的路徑；

5)蟻群遍歷所有節點后根據信息素策略更新信息素；

6)保存每個循環中每只螞蟻的路徑和路徑長度；

7)循環執行4)至6)直到獲得最優解或者達到最大迭代數.

4 實驗結果與分析

為了檢測改進的蟻群算法在機器人尋找最優路徑中的效率，本文實驗通過pycharm在Windows 10的系統下進行了大量的仿真實驗.通過20×20的柵格環境，0表示障礙節點，1表示自由節點，環境中的所有障礙的范圍都可以由各章障礙節點組合形成.對傳統蟻群算法[14]、文獻[10]中改進的蟻群算法和本文改進的蟻群算法在相同的障礙環境下進行仿真比較.3種蟻群算法初始設置為螞蟻的個數M=50,最大迭代數為200，α=0.9，β=4，ρ=0.2，Q=2.

圖3a—3c分別為傳統蟻群算法、文獻[10]蟻群算法以及本文改進蟻群算法的最優路徑搜尋圖，可以發現圖3a和3b都能夠在起始點到目標節點之間找到一條最短的移動路徑，但傳統的蟻群算法在初始環境相同的情況下明顯比文獻[10]蟻群算法得到的可行路徑長.圖3b和圖3c相比，圖3c中的最優路徑長度優于圖3b中的最優路徑長度.

圖3 最優路徑搜尋效果對比Fig.3 Optimal paths obtained by traditional ant colony (a),algorithm in Ref.[10] (b),and the improved ant colony algorithm (c)

圖4a—4c分別為傳統蟻群算法、文獻[10]蟻群算法以及本文算法的收斂曲線.由圖4a可以看出傳統蟻群算法在復雜環境下收斂曲線波動較大，尋優能力極不理想，在大規模的環境中其缺點暴露得非常明顯，在迭代第82次找到最優路徑并逐漸趨于穩定.圖4b顯示文獻[10]算法在迭代第69次找到最優路徑，在迭代第69次后趨于穩定.本文算法收斂曲線(圖4c)顯示在迭代第59次找到最優路徑，在此之后趨于穩定.

圖4 收斂曲線Fig.4 Convergence comparison between traditional ant colony (a),algorithm in Ref.[10] (b),and the improved ant colony algorithm (c)

通過3個算法收斂曲線的對比，明顯可以看出：傳統蟻群算法收斂曲線波動較大、轉折點過多；文獻[10]中的蟻群算法和改進的蟻群算法在達到最大迭代數時雖都已收斂，但本文改進的蟻群算法收斂速度更快、更穩定，尋優的效果更好.3種算法多次仿真實驗的數據對比結果如表1所示.

表1 仿真結果對比

從表1中的實驗數據可以看出，本文改進的蟻群算法相對于傳統算法和文獻[10]中的算法最優路徑長度縮短，收斂的速度也更迅速，且在各代路線的平均長度也優于其他兩種算法.本文改進的蟻群算法從起點到終點規劃軌跡有9個轉折點，而傳統的蟻群算法轉折點有15 個，說明改進的算法具有更好的路徑搜索效率.仿真結果表明本文改進的算法具有更好的路徑規劃效果.

5 結束語

本文利用柵格法的便捷性對環境進行建模，對每個柵格進行標記，應用改進的蟻群算法從初始柵格移動到目標柵格進行路徑搜索，找到最優路徑.本文主要創新在于：1)針對傳統算法搜索的目的性弱、不能快速搜索到可行路徑的問題，通過改進啟發函數，增加蟻群搜索的目的性，降低陷入局部最優解的概率；2)本文提出了一種自適應變化信息素總量的方式，通過迭代次數的增加對信息素總量進行調整，提高全局搜索能力，使算法獲得較快收斂速度.通過實驗仿真驗證了改進后的蟻群算法的優越性和有效性.