自適應(yīng)避障蟻群算法的移動機器人路徑規(guī)劃

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

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

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

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

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

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

1 移動機器人環(huán)境建模

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

圖1 柵格地圖

(1)

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

τ

(

t

+1)=(1-

ρ

)·

τ

(

t

)+

Δτ

,

(2)

式中,

ρ

(0<

ρ

<1)是路徑上的信息素揮發(fā)系數(shù)；1-

ρ

是信息素的持久系數(shù)；

Δτ

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

i

到

j

的路線上的信息素量，即

(3)

(4)

其中，

Q

為常數(shù)，通常設(shè)為1;

L

表示第

k

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

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

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

τ

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

2.1 引入避障因子的狀態(tài)轉(zhuǎn)移概率

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

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

χ

，其計算公式為：

(5)

式中，每個柵格節(jié)點有8個在螞蟻移動步長范圍內(nèi)的相鄰柵格，其中，

A

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

經(jīng)過改進的狀態(tài)轉(zhuǎn)移概率公式為：

(6)

式中，

ε

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

η

(

t

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

η

(

t

)計算公式為：

(7)

式中，

i

為螞蟻當前所在的柵格；

j

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

2.2 自適應(yīng)信息素揮發(fā)因子

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

ρ

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

ρ

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

ρ

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

ρ

如果為定值，算法的適應(yīng)性會較差。改進信息素揮發(fā)因子

ρ

，使其從定值變?yōu)殡S時間變化的動態(tài)值，根據(jù)算法的運行狀況自適應(yīng)地改變信息素的持久性系數(shù)，不但可以加速算法的收斂，還可以增大搜索到全局最優(yōu)路線的概率。改進的信息素揮發(fā)因子計算公式為：

(8)

式中，

ρ

(

t

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

t

=

k

為當前迭代次數(shù)，

σ

和

μ

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

μ

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

ρ

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

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

2.3 改進蟻群算法步驟

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

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

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

NC

、螞蟻數(shù)量

M

、信息素啟發(fā)式因子

α

以及期望啟發(fā)因子

β

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

tabu

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

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

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

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

m

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

m

完成搜索，到達終點；

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

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

NC

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

3 仿真和實驗

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

ρ

大小則根據(jù)調(diào)試經(jīng)驗確定。

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

圖2 機器人運動軌跡對比

圖3 算法收斂曲線對比

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

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

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

圖4 AOA蟻群算法運行結(jié)果

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

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

4 結(jié)論

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