自適應避障蟻群算法的移動機器人路徑規劃

劉雙雙，詹京吳，黃宜慶*

(1.高端裝備感知與智能控制教育部重點實驗室，安徽 蕪湖 241000；2.安徽省電氣傳動與控制重點實驗室，安徽 蕪湖 241000)

路徑規劃一直都是移動機器人領域的重點研究對象，在存在障礙物的環境里，機器人需要從中找到從起點到目標點的最短路徑。機器人在行進中不能碰撞到障礙物，要求路徑規劃出的路線安全以避免碰撞，距離最短以降低機器人的能耗。

在機器人的路徑規劃方法里，傳統方法有人工勢場法、Dijkstra算法、A*算法等。隨著移動機器人工作環境變得多樣化，一些傳統方法無法滿足其在復雜環境中的運行要求，而智能算法的出現克服了傳統方法的不足。目前，大多數移動機器人的路徑規劃采用智能算法，如蟻群算法、粒子群算法、人工魚群算法等。其中，蟻群算法由于其算法收斂較快、算法的性能好和魯棒性強等長處被普遍應用。

傳統的蟻群算法搜索時間較長，收斂速度慢，并且容易出現算法停滯不前的問題，因此，許多科研工作者提出了改進的方法。如精英螞蟻系統、最大-最小(MAX-MIN)蟻群系統、自適應蟻群算法。文獻[10]在算法中建立了局部的信息素擴散模型，改進了啟發函數以及信息素揮發因子，提高了算法的收斂速度。文獻[11]用曼哈頓距離來替代歐式距離作為距離計算方法，引入了方向角啟發因子，增大了選擇當前節點和下一節點的方向向量與下一節點和終點的方向向量夾角小的路徑的概率，提高了算法的效率。文獻[12]將A*算法的估計函數結合到蟻群算法的啟發因子里，并改進了信息素揮發因子，使得蟻群算法在收斂性和尋優路徑上均有所提升。文獻[13]在啟發函數中加入當前節點與下一節點的距離，并用Laplace分布對信息素揮發因子進行了改進，防止算法陷入局部最優，并加快了收斂。文獻[14]提出在算法前期加入避障策略，利用優質螞蟻更新原則指導信息素的更新，并對得到的路徑進行二次規劃，使得到的路徑更優，提高機器人的運行效率。

針對傳統蟻群算法易陷入局部最優、收斂慢等不足，研究對傳統的蟻群算法進行改進。首先，在狀態轉移概率公式中添加避障因子，減少螞蟻搜索路徑的過程中陷入死鎖的數量，用曼哈頓距離替代歐式距離進行節點間的距離計算，減少在開平方之后取近似值而帶來的誤差影響，加快計算速度。然后，改進信息素揮發因子，使其從定值變為隨迭代次數變化的動態值，并限定信息素的范圍，避免算法停滯。經過仿真的結果對比，改進的蟻群算法收斂比傳統的蟻群算法快，在復雜地圖中也能進行高效合理的路徑規劃。

1 移動機器人環境建模

移動機器人的運行環境具有多樣性和一定的復雜性，因此，若進行路徑規劃，環境模型的建立要符合實際環境情況。研究中的移動機器人在平面上運行，采用柵格法構建地圖模型,在柵格地圖中，機器人可自由通過的區域用白色柵格表示，障礙物用黑色柵格表示，機器人不可通過黑色柵格區域。機器人只被允許從當前所在的柵格移動到與該柵格相鄰的8個柵格，規模為10*10的柵格地圖如圖1所示。由圖1可知，起點和終點即為移動機器人的起點和終點，若機器人此時在柵格i，相鄰的柵格共有8個，序號1～8標記。其中，2號柵格和3號柵格為障礙物，則移動機器人下一步可以到達的柵格只有1號以及4～8號，并且每個柵格僅可以通行一次。

圖1 柵格地圖

(1)

當所有螞蟻完成一次路徑搜索后，每條路徑上的信息素量都要進行更新。更新的方式如式(2)所示：

τ

(

t

+1)=(1-

ρ

)·

τ

(

t

)+

Δτ

,

(2)

式中,

ρ

(0<

ρ

<1)是路徑上的信息素揮發系數；1-

ρ

是信息素的持久系數；

Δτ

描述此次搜索過程里所有螞蟻遺留在節點

i

到

j

的路線上的信息素量，即

(3)

(4)

其中，

Q

為常數，通常設為1;

L

表示第

k

只螞蟻在此次路徑搜索中行走路徑的長度。

2 自適應避障(AOA)蟻群算法

研究在螞蟻的狀態轉移概率以及信息素揮發因子上進行改進。為減少螞蟻在前期搜索過程中向遠離終點的方向前進的概率，只在以起始點和終止點為頂點的柵格地圖區域設置初始信息素，其初始值為

τ

，用來減少螞蟻盲目的搜索次數，提高收斂速度。

2.1 引入避障因子的狀態轉移概率

在蟻群的初期搜索過程中，信息素濃度和啟發信息的值都較小，對螞蟻選擇下一步前進節點的引導作用很小。因此，螞蟻搜索范圍較大，搜索出的路徑容易產生交叉現象，再加上禁忌表以及地圖障礙物陷阱的影響，螞蟻容易陷入死鎖，無法到達終點。不僅如此，死鎖螞蟻遺留下的信息素信息會誤導后面的螞蟻也陷入死鎖狀態，嚴重影響算法的運行。

為避免上述情況的出現，根據人工勢場法的原理加入障礙物斥力思想，提高螞蟻避開障礙物陷阱的能力，螞蟻將傾向于選擇周圍障礙物更少的節點。在狀態轉移公式里引入安全避障因子。該避障因子設為

χ

，其計算公式為：

(5)

式中，每個柵格節點有8個在螞蟻移動步長范圍內的相鄰柵格，其中，

A

表示除去被禁忌表限制以及障礙柵格外的所有可行柵格。

經過改進的狀態轉移概率公式為：

(6)

式中，

ε

表示避障因子的相對重要程度，取值根據地圖的復雜程度決定，是一可變參數，通常取值為一個小的正數。增加了避障函數后，蟻群算法的迭代速度加快，螞蟻陷入死鎖的數量大大減少。除此之外，對于啟發因子

η

(

t

)，用曼哈頓距離替代歐式距離進行節點間的距離計算，減少計算開平方的時間，也減少在開方后取近似值的誤差。啟發因子

η

(

t

)計算公式為：

(7)

式中，

i

為螞蟻當前所在的柵格；

j

為螞蟻前進的下一柵格位置。

2.2 自適應信息素揮發因子

自然界中，在螞蟻尋找路徑并不停釋放信息素的過程中，信息素也會以一定的速率揮發掉，該速率被稱為信息素揮發因子。傳統算法里，信息素揮發因子

ρ

的取值范圍為(0,1),表示信息素的蒸發程度，它實際上反應的是蟻群中各個螞蟻個體之間相互影響程度的強弱。當

ρ

過小時，螞蟻更加傾向于選擇之前行走的路徑，這樣會對算法進行全局搜索的能力造成影響，如果這條路徑不是最優路徑的話，就造成算法收斂在局部，只能得到次優路徑。當

ρ

過大時，路徑上殘存的信息素量相對較低，雖然可以加強蟻群全局搜索路徑的能力以及搜索的隨機性，但是無用搜索的增多會影響算法的收斂速度。因此，

ρ

如果為定值，算法的適應性會較差。改進信息素揮發因子

ρ

，使其從定值變為隨時間變化的動態值，根據算法的運行狀況自適應地改變信息素的持久性系數，不但可以加速算法的收斂，還可以增大搜索到全局最優路線的概率。改進的信息素揮發因子計算公式為：

(8)

式中，

ρ

(

t

)的取值范圍為(0,1)。令

t

=

k

為當前迭代次數，

σ

和

μ

為可變參數，根據地圖的復雜程度和實驗確定兩者的取值，在當前迭代和設定的

μ

值相等時，信息素揮發因子取得最大值，

ρ

為一常數值，是用以保證信息素的揮發因子不會過小的最低值。

由于改進的信息素揮發因子的計算公式遵循高斯(Gaussian Distribution)分布的規律，那么在蟻群搜索可行路徑的前期，揮發因子的值較小，有利于蟻群根據信息素的指引向較優的路徑上靠攏；在搜索中期，信息素已經積累到一定的量，為防止算法陷入局部最優，提高全局搜索的能力，此時信息素揮發因子取得較大值；在蟻群搜索路徑的后期，可選擇的路徑比較少，因此，為了加快收斂的速度，揮發因子取得一個較小值。

2.3 改進蟻群算法步驟

AOA蟻群算法具體步驟如下：

(1)使用柵格法對移動機器人運行的環境構建二維靜態地圖，在構建的柵格地圖中，黑色柵格表示障礙物，白色柵格表示機器人可通行的節點，機器人不可以在障礙柵格上運行，但可以在白色柵格自由行進；

(2)設置初始化參數，將以起點與終點為頂點的初始信息素設置為一較小值，設置最大迭代次數

NC

、螞蟻數量

M

、信息素啟發式因子

α

以及期望啟發因子

β

等基本參數；(3)將所有螞蟻放置在起點，并將每只螞蟻的禁忌表

tabu

的第一個元素設置為起點，準備開始搜索路徑；

(4)每只螞蟻個體根據輪盤賭法以及加入避障因子的狀態轉移式(6)對將要行進的下一節點進行選擇；

(5)更改禁忌表，當螞蟻行進到新的節點后，將上一個節點加入該螞蟻的個體禁忌表里；

(6)更新信息素，在螞蟻

m

完成搜索后，根據AOA蟻群算法進行信息素的更新，其中，信息素揮發因子的值根據式(8)進行計算；(7)重復步驟(4)～(6)，直到螞蟻

m

完成搜索，到達終點；

(8)迭代次數加一，清空每只螞蟻的禁忌表以進行下一次的迭代搜索；

(9)判斷迭代次數是否等于事先設定的

NC

，如果相等，則程序結束，輸出結果，否則轉到步驟(3)。

3 仿真和實驗

研究算法的仿真平臺為MATLAB。計算機配置為：Windows 10，處理器為Inter(R) Core(TM) i5-7200U CPU @ 2.50 GHz 2.71 GHz，內存4 GB。使用柵格法建立規模為20*20三種障礙物不同分布的環境，初始化參數設置為：螞蟻數量50，信息素因子為1，啟發信息因子為8，傳統蟻群算法的信息素揮發因子取值為0.4，AOA蟻群算法中的避障因子的指數部分以及信息素揮發因子

ρ

大小則根據調試經驗確定。

研究設計了三種柵格地圖，地圖的規模都是20*20，但是障礙物的數目和分布情況都不相同，代表機器人的三種運行環境。基于這三種地圖對蟻群的傳統算法和研究的AOA蟻群算法進行了仿真實驗，并進行對比。三種柵格環境分別命名為柵格環境A、柵格環境B、柵格環境C，相應的軌跡圖和迭代圖如圖2所示。從圖2可知，傳統的蟻群算法和改進的蟻群算法都可在該種障礙物分布的20*20柵格地圖中得到較為合理的路徑規劃結果。若在算法運行過程中，所找到的路徑在某次迭代后保持不變，則將該次迭代數稱為初次收斂迭代次數，即之后的所有螞蟻都會沿著該次迭代得到的路徑行走，不會再探索其他的可行路徑。算法收斂曲線對比如圖3所示。對圖3中得到的兩種算法的收斂曲線進行比較，結果如表1所示。

圖2 機器人運動軌跡對比

圖3 算法收斂曲線對比

表1 三種柵格地圖下的算法比較

由圖1和圖2可以得出，傳統的蟻群算法存在著以下兩個問題。其一是無法找到全局最優路徑，算法最終輸出的路徑是次優路徑，并且初次收斂的迭代次數較大。其二是算法經過若干次迭代找到了全局最優路徑，但是由于次優路徑上的信息素量高于最優路徑，所以算法最終收斂于次優路徑長度。由表1可得，在三種不同的柵格環境中，AOA蟻群算法最終收斂得到的最小路徑長度比傳統蟻群算法得到的最小路徑長度更短，并且在初次收斂迭代次數上，改進的蟻群算法明顯少于傳統的蟻群算法，這兩點顯示出改進的蟻群算法更具優越性。

為進一步驗證改進算法的可靠性，設置同文獻[16]相同的柵格地圖進行對比實驗，AOA蟻群算法運行結果如圖4所示。與文獻[16]的算法對比如表2所示。由表2可知，所找到的路徑均為最優路徑，但是，研究算法的初次迭代收斂次數明顯降低，即AOA蟻群算法具有更快的搜索最優路徑的能力和更好的收斂速度。

圖4 AOA蟻群算法運行結果

表2 與文獻[16]的算法對比

由實驗可知，在規模為20*20的三種障礙物分布不同的柵格地圖的仿真結果以及與改進算法的對比實驗均表明，研究設計的AOA蟻群算法在機器人路徑規劃方面更具優越性。

4 結論

針對傳統的蟻群算法容易陷入局部最優和收斂速度慢的不足對算法進行了改進。在螞蟻的狀態轉移概率計算公式中添加了避障因子，減少了螞蟻的死鎖數量，加快了螞蟻搜索路徑的速度。對于固定的信息素揮發因子可能使算法陷入局部最優或者收斂速度慢的不足，給出了基于高斯分布的改進信息素揮發因子，使信息素揮發因子從固定值變為隨時間變化的自適應值，使得算法得到的路徑更優，大大加快了算法的收斂速度。對比兩種算法的仿真結果，AOA蟻群算法在最短路徑的尋找以及收斂速度上都比傳統的蟻群算法更好。下一步將嘗試改變螞蟻的步長，進一步減小路徑的長度，使得路徑更加平滑，并嘗試將得到的仿真結果應用到現實生活中，實時實現移動機器人的路徑規劃與避障。