基于改進蟻群算法的機器人路徑規劃問題研究

牛龍輝，季野彪

（西安工程大學電子信息學院，西安710600）

1 引 言

在智能體的研究中，路徑規劃問題一直擔任著重要角色，是一個涉及智能控制、材料工程、人工智能和信息處理等相關專業學科的復雜系統工程[1]。機器人規劃路徑時，需要以一定的標準評判。在已知起始點和目標點的障礙環境下，機器人需要進行從起始點到目標點最優路徑的尋找，即解決機器人的路徑規劃問題。文獻[2]提出了一種基于粒子群優化的路徑規劃算法，在障礙環境下對機器人進行導航。首先定義一個隸屬函數來評價路徑的風險程度，考慮風險度和路徑距離這兩個性能優點，對機器人進行有效的路徑規劃。文獻[3]著重介紹和評價了模擬退火（SA）的人工勢場方法，改進了人工勢場法中易陷入局部最優值的缺陷。模擬退火作為一種有效的局部極小值逃逸技術，已被應用于局部和全局路徑規劃中。文獻[3]針對移動機器人室內定位技術的特點，在結構化環境下開發了室內移動機器人路徑規劃系統，針對路徑規劃的不足，提出了一種改進的A*算法，能夠計算具有拐點、旋轉方向和最小旋轉角度的移動機器人定位。移動機器人定位試驗表明，改進算法不僅簡化了路徑規劃，而且可以調整機器人在拐點的姿態，能夠滿足機器人自主運動的要求。采用改進后的蟻群算法對機器人路徑規劃進行研究，提高了路徑規劃的實現效率[4]。

蟻群算法在全局路徑規劃中有著極大優勢，擁有著計算簡便，具有良好魯棒性且易與其他算法相結合的優點，在此，采用改進后的蟻群算法對機器人進行路徑規劃，有效降低路徑長度。

2 環境建模

首先，在機器人路徑規劃前，要進行障礙環境的建模。此處采用柵格法進行建模，在建模前需滿足以下假設條件：考慮機器人的工作環境為二維空間，不考慮高度的影響，且障礙物處于靜止狀態；已知機器人的起始點和目標點，并將機器人視為質點，忽略自身尺寸的影響[5]。

用黑白網格表示環境。黑色柵格代表障礙物，白色柵格代表可行區，矩陣中1 代表障礙物，0 代表自由柵格。建立的環境模型如圖1 所示。

圖1 柵格地圖

以機器人所在柵格為中心，機器人行走的方向節點共8 個，螞蟻對柵格的訪問是以訪問一個柵格的中心點為準，如圖2 所示。

圖2 機器人運動范圍

圖中左上角第一個柵格為序號1，向右序號逐次加一，序號1 的柵格坐標是(0.5,19.5)，序號7 的柵格坐標是(6.5,19.5)，以此類推序號400 的柵格坐標為(19.5,0.5)，也就是右下角柵格。

3 蟻群算法及改進

3.1 基本蟻群算法

蟻群系統（Ant System 或 Ant Colony System）是由意大利學者Dorigo、Maniezzo 等人于20 世紀 90年代首先提出的[6]。他們對螞蟻覓食行為進行研究時，發現蟻群整體處于一種智能的行為中。螞蟻在覓食過程中總是可以找到一條最短的路徑進行食物的搬運。這是因為蟻群內的螞蟻可以通過某種信息機制實現信息的傳遞。后又經進一步研究發現，螞蟻會在其經過的路徑上釋放一種可稱之為“信息素”的物質，蟻群內的螞蟻對“信息素”具有感知能力，它們會在短時間內找到信息素濃度較高的路徑，并在下一次搬運食物時走信息素濃度較高的路徑，同時依舊留下信息素，形成一種正反饋的機制，這樣經過一段時間后，整個蟻群就會沿著最短路徑到達食物源[7]。

選擇下一節點的具體實現公式為：

其中，S 代表按照AS 算法得到的下一節點的概率，allowedk表示當前節點的可選節點集合。τij表示i 點到j 點的信息素量，ηij則是對應點之間的啟發式量，其中表示兩點間的歐式距離[7]。兩點間距離越大，啟發式量則越小，螞蟻在節點i 時選擇節點j 的概率就會較小。α 為信息啟發式因子，表示此路徑的信息素對后續探索時螞蟻選擇此條路徑的影響程度，α 越大，后續螞蟻選擇這條路徑的概率越大，β為期望啟發式因子，反映啟發信息對螞蟻路徑選擇的影響程度。每次迭代結束，路徑信息素都要進行更新。全局更新公式為：

其中ρ 表示信息素揮發因子，τij表示i 與j 點之間的信息素濃度，Δτij表示i 與j 點之間的信息素增量，表示第k 只螞蟻在i 與j 點之間的信息素增量的貢獻量。經典AS 算法通過迭代對信息素進行更新來選取最優路徑[8]。

3.2 改進蟻群算法

在ACS 算法迭代過程中，參數對算法性能有著直接或間接影響，其中信息素揮發度參數ρ 的取值會直接影響算法的收斂速度與全局搜索能力。信息素揮發系數ρ 過大，會導致算法多樣性降低，易出現搜索提前停滯，但收斂速度加快。ρ 較小時，算法的收斂速度慢，但算法多樣性提高，搜索能力加強。所以對ρ 的選擇需要綜合考慮算法的全局搜索能力和收斂速度。

根據上述分析，固定的ρ 值存在一定的弊端，因此，構造一個動態改變信息素揮發度參數ρ 的函數如下：

式中，自變量 n 為迭代次數，σ、μ 為常數。ρ 與迭代次數n 有關，其函數曲線單調遞增。前期隨著n 的增大，ρ 曲線平緩上升；中期隨著 n 的繼續增大，ρ 曲線急速上升；到后期ρ 曲線趨于平緩。在搜索路徑前期，ρ 取較小值是為了保留最優路徑的更多信息；在搜索的中后期，ρ 取較大值，是為了加快收斂速度。

4 仿真及分析

為驗證本算法的有效性，在MATLAB 2014a 上進行仿真實驗。利用上文提到的柵格法構建環境模型，在相同環境下比較本算法與ACS 算法的仿真結果，并對實驗結果進行分析。

算法參數的設置如表1 所示。

表1 參數設置

障礙物條件下（設置起點S=49，終點G=369）的兩種算法的路徑規劃結果及收斂曲線分別如圖3、圖4 所示。其中實直路線代表經典蟻群算法，點線路線代表改進的蟻群算法。

圖3 路徑規劃圖

圖4 收斂曲線

從對圖3 曲線的分析中可知，經典AS 算法在障礙環境中遇見障礙物會出現徘徊現象，無法逃離局部最優解，其多樣性明顯較差，而本算法在快速收斂的同時，可得到全局最優路徑。實驗表明本改進算法在環境障礙物條件下是可行且有效的。

從圖4 收斂曲線可見，本算法所得路徑長度明顯較經典AS 算法短，收斂速度也不慢。綜上分析，通過在障礙環境對算法進行實驗，驗證了改進算法較經典AS 算法具有更強的尋優能力，算法多樣性明顯提高，且具有良好的準確性與魯棒性，在解的質量與收斂速度方面表現出更好的性能。

5 結束語

針對經典AS 算法在路徑規劃中尋優能力不足和算法多樣性低等問題，引入自適應信息素揮發系數，以加強全局尋優能力，提高算法多樣性。仿真實驗表明，改進算法有效地解決了經典AS 算法尋優能力不足缺陷，提高算法多樣性，并具有良好的準確性與魯棒性。