基于一種改進的蟻群算法的移動機器人三維路徑規劃研究

王 飛,江 明

(安徽工程大學 檢測技術與節能裝置重點實驗室，安徽 蕪湖 241000)

路徑規劃技術是移動機器人的關鍵技術，也是移動機器人能夠自主完成各種任務的首要前提，其任務是在環境已知或部分已知情況下，為移動機器人依據距離最短、時間最短、能耗最低等一條指標或多條指標規劃一條從起始點到目標點的無碰撞最優路徑[1]。目前，國內外對此已經進行了大量研究并且提出相應的解決方法，如A*算法[2]、人工勢場法[3]、遺傳算法[4]、粒子群優化算法[5]、神經網絡算法[6]等等，每種算法都有自己的優勢，然而大部分研究都是基于二維空間環境，對于環境復雜、規模較大的三維空間存在一些局限性，而且由于三維環境特殊地貌的影響，路徑規劃的難度也隨之加大，難以取得理想的效果。

蟻群算法是由M.Dorigo等學者提出的一種模擬自然界螞蟻覓食行為的智能優化算法。螞蟻在覓食過程中會分泌出一種信息素并且信息素的多少和螞蟻走過的路徑長度成反比，在路徑節點處螞蟻會傾向于選擇信息素較大的路徑。隨著蟻群大量體的隨機探索，最優路徑上信息素值會越來越大，最終整個蟻群會搜索到最優路徑，因此蟻群算法具有很強的魯棒性和適應性[7]，在解決三維空間路徑規劃的問題上取得了不錯的效果，但是也存在易陷入局部最優解、收斂速度慢等不足之處。文獻[8]將蟻群算法和遺傳算法相結合，提高了算法搜索效率。文獻[9]對死鎖螞蟻采取清零回退機制，實現移動機器人在三維空間中高效避障。文獻[10]建立模糊運動控制系統，實現動態避障，通過模糊集合的優化保證最優路徑。文獻[11]設計了動態搜索模型，提高算法收斂速度和解的質量。

文中研究了移動機器人在三維環境下的路徑規劃，提出一種改進的蟻群優化算法。針對三維環境復雜特點以及蟻群算法的不足，增加了避障策略，構造新的啟發函數，增強算法全局搜索能力；依據起始點和目標點位置優化全局路徑初始信息素值分布，減少搜索初期螞蟻盲目搜索，提高算法搜索效率；提出優質螞蟻更新原則，自適應調整信息素揮發因子，避免算法陷入局部最優解。

1 基本蟻群算法

螞蟻根據路徑上信息素和路徑信息來選擇路徑，在第t次迭代中，螞蟻k由節點i選擇下一節點j的轉移概率表示為：

(1)

(2)

式中,α為信息素啟發因子；β為期望啟發式因子；τij為路徑(i,j)的信息素濃度；allowk表示路徑搜索所有下一可達節點的集合；nij為啟發信息；dij為當前節點i和待選節點j的歐氏距離。所有螞蟻完成一次迭代后，對殘留信息素進行揮發處理，則t+1時刻在路徑(i,j)上信息素按式(3)、式(4)進行更新。

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

(3)

(4)

式中，ρ為信息素揮發系數，ρ∈(0,1)；Δij(i,j)表示本次迭代螞蟻在路徑(i,j)上的信息素增量；Q為信息素強度；Lk表示第k只螞蟻在本次迭代所走路徑的總長度。

2 三維環境路徑規劃

2.1 三維環境建模

環境模型建立的好壞直接影響到路徑規劃算法的精確度，因此合理的將三維環境抽象表達出來是移動機器人在三維環境中自主作業的關鍵[12]。采用柵格法將二維空間擴展到三維空間，如圖1所示，構造三維空間ABCD-EFGH，以A點為原點建立空間坐標系，ABCD平面在XOZ平面上，以原點O沿Y軸方向將AE進行n等分，沿X軸方向將AB進行m等分，沿Z軸方向將AD進行l等分，即得到n個平面，每個平面劃分為m×l個柵格。至此ABCD-EFGH空間可由n×m×l個柵格來表示，空間中任一個柵格都對應一個路徑節點，蟻群算法則在這些節點中進行路徑規劃設計與仿真研究。

圖1 三維空間模型 圖2 三維空間搜索模式

2.2 搜索模式

在三維空間中，由于選擇節點范圍的擴大，導致算法搜索變得異常復雜，而且很容易出現死鎖現象，使得算法收斂性差，全局搜索性低。為此，采用一種分層前進與柵格平面法相結合的搜索模式如圖2所示。設定移動機器人起始點為PS，目標點為PG，選取X軸為主前進方向，規定機器人最大橫向移動距離ymax，最大縱向移動距離Zmax，即螞蟻對下一個節點的搜索存在可達區域。首先螞蟻從起始點PS出發，在第一個平面搜索到可行節點P1(x1,y1,z1)，接著在第二個平面搜索到第二個可行節點P2(x2,y2,z2)，螞蟻依次在各個平面選擇路徑節點，直到搜索到目標點PG結束，即可搜索到一條最優路徑。

2.3 啟發函數設計

啟發函數是整個蟻群算法重要組成部分，其作用是利用距離信息引導移動機器人選擇最短路徑，直接影響到算法的收斂性、穩定性以及最優性[13]。但是螞蟻搜索節點時往往容易貪婪選擇與當前節點最近的節點而忽視了下一節點到目標節點的距離，且在算法搜索前期盲目地選擇節點，而忽視節點周圍障礙物因素，易陷入死鎖狀態。為此增加避障策略構造新的啟發函數，轉移概率式如式(5)所示:

(5)

(6)

(7)

(8)

(9)

式中，τa,a+1為路徑信息素。Ha,a+1為啟發函數信息；D1為當前節點到下一節點的距離的倒數；D2為下一節點到目標點距離的倒數；(ia,ja,ka)為當前節點坐標；(ia+1,ja+1,ka+1)為下一節點坐標；(iG,jG,kG)為目標點坐標；N為當前節點可探索區域內節點總數量；Na+1為當前節點可探索區域內不可行節點的數量；w1、w2、w3為相應的權值。通過引入避障策略以及對啟發信息函數的改進，能夠有效提高算法的全局搜索能力。

2.4 初始信息素分布優化

在蟻群算法搜索前期，由于各路徑信息素初始值相同，算法的正反饋作用不明顯，螞蟻會在搜索過程中盲目搜索，甚至朝著相反的道路探索，極大降低算法的搜索效率[14]。改進蟻群算法在信息素初始化時，設定前進方向中起始點和目標點之間的區域為全局有利區域，規定其信息素初始值大于其他區域信息素初始值，即

(10)

式中，τ0為信息素初始值；C為大于τ0的常數；R為全局有利區域。依據全局地圖信息可知，最優路徑往往是一條從起始點朝著目標點方向出發并逐漸靠攏的路徑，因此不均勻分配信息素，有利于減少蟻群搜索時間，提高搜索效率。

2.5 信息素更新規則

螞蟻在每一次迭代后會對所走過的路徑進行信息素更新，然而每一次迭代中，并非每只螞蟻尋得的路徑都是最優路徑，更有一些螞蟻遇到死鎖，無法走到終點，因此合理的信息素更新是確保螞蟻快速尋到全局最優路徑的保證。基于此提出優質螞蟻更新規則，即每一次螞蟻迭代后，按式(11)只選擇更新達到目標點的螞蟻上的路徑信息素，拋棄陷入死鎖的螞蟻，避免信息素盲目更新，干擾螞蟻對路徑選擇的判斷。然后分別找出每次迭代中最優螞蟻與最差螞蟻，分別按式(12)、式(13)對其路徑上的信息素進行加強與減弱。自適應調整揮發因子ρ，令ρ按式(14)進行調整，即設定在連續T次迭代內蟻群算法求得的最優解都相同，為避免算法陷入局部最優解，之后每次迭代都減少ρ的值，減弱當前搜索到的最優路徑上信息素對螞蟻搜索路徑的影響，ρmin為ρ的最小值，防止ρ過小降低算法收斂速度。γ為信息素衰減系數，為一個小于1的正數，同時限定信息素值上下限τ(t)∈[τmax,τmin]，防止算法因信息素過大或過小陷入局部最優值[15]。

τijk(t+1)=(1-ρ)τijk(t)+ρΔτijk(t,t+1),

(11)

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

(12)

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

(13)

(14)

3 改進算法步驟

步驟1：對機器人工作環境建立抽象模型，選擇起始點和目標點，根據全局地圖信息劃定有利區域，對初始信息素值進行不均勻分配。

步驟2：初始化螞蟻數量m、最大迭代次數Nmax、信息素揮發因子ρ、信息素衰減系數γ等參數，選擇起始節點，根據轉移概率式(5)尋找下一個可達路徑節點，直到螞蟻搜索結束。

圖3 算法流程圖

步驟3：所有螞蟻完成一次迭代搜索后，拋棄陷入死鎖的螞蟻，只對所有走到目標點上的螞蟻進行路徑上信息素更新，另外按式(12)、式(13)分別加強最優螞蟻與減弱最差螞蟻所經過路徑上的信息素，同時限定信息素上下限濃度τ(t)∈[τmax,τmin]。

步驟4：設定迭代閾值T，即連續T次求得最優解沒有變化時，則按式(14)自適應調整信息素揮發因子。

步驟5：判斷迭代次數是否達到上限，如果沒有，則跳轉步驟2，如果迭代次數到達上限結束搜索，保存最優路徑信息。

步驟6：輸出最優路徑長度，算法結束。

算法執行流程圖如圖3所示。

4 仿真實驗與結果分析

隨機生成31m×31m×31m環境模型，在安全避障的前提下，以最短路徑為評價指標。采用改進蟻群算法和經典蟻群算法進行實驗對比，算法運行環境為：Windows 7 64 bit； Matlab 2016a；處理器i5-4590 CPU；內存4 GB。實驗參數取值如表1所示。

4.1 仿真實驗一

設定起始點為(1,15,8)，目標點為(31,16,9)，路徑規劃結果如圖4、圖5、圖6所示，實驗數據如表2所示，可以看出經典蟻群算法迭代了14次才找到了全局最優路徑37.877 6 m，而改進蟻群算法在第8次就找到了全局最優路徑33.949 4 m。改進蟻群算法相比經典蟻群算法迭代次數減少43%，路徑長度減少10%，極大減少了收斂次數，并且啟發函數和信息素更新規則的改進，使得改進算法搜索到的最優路徑長度小于經典蟻群算法。

表1 實驗參數設置

表2 仿真實驗一

圖4 經典蟻群算法路徑規劃 圖5 改進蟻群算法路徑規劃

圖6 兩種算法收斂情況

4.2 仿真實驗二

設定起始點為(1,1,5)，目標點為(31,8,5)，路徑規劃結果如圖7、圖8、圖9所示。實驗數據如表3所示。可以看出經典蟻群算法迭代了15次才找到了全局最優路徑37.192 0 m，而改進蟻群算法在第10次就找到了全局最優路徑35.599 7 m。改進蟻群算法相比經典蟻群算法迭代次數減少了33%，路徑長度減少4%。盡管在算法運行時間上改進蟻群算法耗時稍微多點，這是因為在搜索前期對初始信息素處理，增加避障策略以及信息素更新等方面的改進而增加了一些程序代碼，但是從路徑規劃結果對比分析，算法搜索策略的改進使得改進蟻群算法有效提高算法搜索能力和收斂速度，充分表明了其優越性和可行性。

表3 仿真實驗二

圖7 經典蟻群算法路徑規劃 圖8 改進蟻群算法路徑規劃

圖9 兩種算法收斂情況

5 結論

文中研究了移動機器人在三維環境下路徑規劃的問題，提出一種改進的蟻群優化算法。采用柵格法擴展建立三維抽象環境模型，依據起始點和目標點位置信息，優化初始信息素值分布，避免算法前期螞蟻盲目搜索，提高算法的搜索效率。引入避障策略并且利用當前節點與目標節點的距離信息來改進啟發函數，提高算法全局搜索能力。提出優質螞蟻更新策略，自適應調節信息素揮發因子，防止算法陷入局部最優值。實驗結果表明，在復雜的三維環境下，改進蟻群算法相比經典蟻群算法有效縮短了最優路徑長度，降低了收斂次數，具有較高的全局搜索能力。算法是在全局靜態環境下展開研究的，后續研究將重點放在動態避障上，進一步提高算法的實用性、有效性。