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

任紅格，胡鴻長，史濤

(1.天津城建大學 控制與機械工程學院，天津 300384；2.華北理工大學 電氣工程學院，河北 唐山 063210)

移動機器人路徑規劃是機器人學研究領域中的一個重要組成部分，其任務是在具有障礙物的環境內，按照一定的評價標準(工作代價最小、行進路線最短等)尋找一條從起始狀態(包括位置和姿態)到目標狀態(包括位置和姿態)、與障礙物無碰的路徑[1]。根據環境信息的已知程度不同，移動機器人路徑規劃又可分為環境已知的全局路徑規劃及環境未知的局部路徑規劃。全局路徑規劃主要分為2個問題，即環境構建與搜索算法。目前，可視圖法、柵格法等在環境構建中應用較多，對于搜尋路徑最優的算法，比較流行的是A*算法[2-5]、遺傳算法、蟻群算法等[6-9]。

蟻群算法最早成功應用于解決著名的TSP(Travelling salesman problem )，該算法采用了分布式并行計算機制，易于和其他方法結合，而且具有較強的魯棒性,因此，也常常將蟻群算法應用到許多實際問題上。金飛虎等[10]將蟻群算法應用于自由飛行空間機器人的路徑規劃中，文獻[11]則將蟻群算法應用于圖像分類中。該項目則提出一種改進蟻群算法，采用修改算法路徑搜索策略、啟發函數以及信息素揮發系數，改進算法與傳統算法相比，不僅具有更快的收斂速度，而且搜索到的路徑也更優。

1改進蟻群算法

1.1 環境建模

本文采用柵格法對已知的環境信息進行建模，通過將序號以及二維直角坐標相結合的方式對柵格進行標記。為了確保機器人與障礙物無碰撞，障礙物采用膨化的方式，以機器人的半徑大小進行膨化，由此在柵格圖中將機器人視為一個點，建好的柵格圖如圖1所示。

圖1 柵格圖

設柵格圖列數為c，則序號n與坐標(x，y)的對應關系由式(1)給出：

(1)

式中mod為取余運算，floor為向負無窮方向取整。

1.2 路徑搜索策略的改進

當路徑上存在類似于U型障礙物的特殊形狀障礙物時，傳統蟻群算法缺乏逃出此類特殊環境的手段，因此該算法在這類環境中不僅搜索效率低下，而且還有可能陷入停滯。U型障礙物如圖2所示。

圖2 U型障礙物

劉徐迅等[12]提出一種螞蟻回退策略，既在螞蟻陷入U型障礙物時，螞蟻通過反復回退，跳出障礙物，增加了計算量。康冰等[13]則在其基礎上，提出一種禁忌柵格優化法，通過改進螞蟻跳出U型障礙物的手段，在一定程度上減少了計算量。以上算法追求的都是在螞蟻陷入U型陷阱后，通過提高螞蟻的逃出速度來降低算法計算量。該研究不局限于跨越U型陷阱這個點，而是修改算法路徑搜索策略，既在螞蟻陷入U型障礙物時，螞蟻無需回退，而是直接放棄此次搜索過程，進行下一次搜索。當螞蟻搜索陷入U型障礙物時，即使螞蟻最終跳出陷阱，找到目標點，此次路徑也不會是最優的，放棄這條路徑，不僅能減少計算量，還能避免劣質路徑對螞蟻搜索的干擾。

1.3 基于方向性原則的啟發函數

在傳統蟻群算法中，啟發函數ηij(t)是相鄰柵格之間距離的倒數，因此螞蟻在相鄰柵格中的啟發權值差異并不明顯，這使得啟發函數在螞蟻轉移決策中并沒有起到很明顯的作用，使得算法的搜索效率比較低。螞蟻一次轉移的可能性如圖3所示。

圖3 螞蟻可能的選擇方向

由圖3可以看出，螞蟻在一次節點轉移中，它的啟發函數值僅有2種可能性，且比值僅為1：√2。在起點終點位置已知，方向明確的情況下，按照基本蟻群算法的啟發函數公式計算狀態轉移概率，啟發函數既沒有利用上路徑起點終點的方向信息，又不能很明確地反映出相鄰節點的差異，這導致螞蟻在相鄰節點轉移時會做許多無用功，既增加了搜索時間，又延長了搜索的路徑。

基于方向性原則的啟發函數則是取下一個可行節點與終點距離的倒數的平方，表達式如式(2)所示。

ηjd=1/[(xj-xd)2+(yj-yd)2]

(2)

式中，(xj,yj)是下一個可行節點的坐標，(xd,yd)是目標節點的坐標。

1.4 基于時空信息交互的信息素更新策略

在基本蟻群算法中，螞蟻種群在完成一次迭代之后，所有螞蟻都要進行信息素更新。在螞蟻種群進行反復迭代更新之后，路徑各節點之間的信息素會出現很大差異，信息素高的節點經過的螞蟻越多，而經過的螞蟻就越多，節點的信息素就越高，這是一個正反饋過程。然而，在迭代次數不高的時候，種群中的螞蟻搜尋到的大部分都不是最優解，即在算法搜索前期，信息素的更新更容易受到劣質解的干擾，劣質解不僅會使蟻群算法尋優搜索時間增長，降低其效率，而且在劣質解大量存在的時候，算法易陷入局部最優解。文獻[14]給出了一種自適應調整揮發系數的信息更新策略，調整方案為：

ρ(t)=max[γρ(t-1),ρmin]

(3)

式中，ρmin為揮發系數最小值。

在張煜東等[14]的基礎上，進一步提出一種基于時間空間的信息素更新策略。基于時間空間的信息素更新策略是將路徑信息與迭代次數同時應用在信息揮發系數ρ上，動態調整ρ，使信息素滿足蟻群在不同時刻，不同區域的取值需求。信息素更新策略如式(4)～式(6)：

(4)

ρ(t)=max[μρ(t-1),ρmin]

(5)

τij(t+Δt)=[1-ρ(l)-ρ(t)]·τij(t)+Δτij(t)

(6)

式中，dmid是蟻群在一次迭代過程中路徑長度的平均值；dbest是迭代過程中的最短路徑，δ為常數，用來調整ρ(l)的值，使ρ(l)∈(0,1)；μ是衰減系數，ρmin是揮發系數最小值。

由式(4)～式(5)可以看出，ρ(l)包含的是關于路徑的空間信息，主要由最短路徑與平均路徑長度構成。在一次迭代過程中，若最短路徑與平均路徑長度相差過大，則意味著迭代過程中包含了太多的劣質解，此時應該增大信息素揮發系數，加快信息素的揮發，避免算法受劣質解干擾。ρ(t)將揮發系數與時間聯系起來，讓系數隨著時間的積累而逐漸減小，直至取到最小值。即在蟻群搜索前期，信息素揮發系數較大，蟻群之間協作性較弱，搜索隨機性較強，搜索范圍增大，而在后期，系數減小，蟻群之間協作性增強，搜索范圍逐漸向最優解區域收縮，加快了算法后期的收斂性。

2改進蟻群算法的算法流程

在蟻群算法中引入了新的路徑搜索策略以及改進的信息素跟新策略后，算法流程圖如圖4所示，具體步驟如下：

圖4 改進蟻群算法的算法流程圖

步驟1：利用柵格法對地圖環境進行建模，設置起點，終點以及障礙柵格。

步驟2：算法流程及各參數初始化。設置時間t=0，循環次數NC=0，取最大循環次數NCmax，設定好ρ、β、μ等各參數值。

步驟3：循環次數NC=NC+1，k=1。

步驟4：螞蟻數目k=k+1。

步驟5：每只螞蟻都從初始節點出發開始搜索遍歷，螞蟻個體根據狀態轉移概率公式計算的概率,使用輪盤賭法，選擇下一步可行點并前進。

步驟6：修改禁忌表指針，選擇好可行點之后將螞蟻移動到新的柵格，并把該點加入到此螞蟻個體的禁忌表中。

步驟7：按改進的螞蟻搜索策略進行路徑搜索，如果螞蟻搜索到終點，則計算該螞蟻搜索到的路徑長度，返回步驟4；如果沒有，則返回步驟5；如果螞蟻陷入U型障礙物則放棄此次搜索，并對該陷阱進行標記，返回步驟3。

步驟8：如果k>m(m為螞蟻數目，即一次迭代過程中搜索的次數)，按信息素更新策略更新路徑信息素并返回步驟3。

步驟9：如果NC>NCmax，輸出算法計算結果，算法結束。

3算法仿真及結果分析

為了驗證改進后的ACO的性能，使用MATLAB編寫仿真程序，算法的仿真參數設置如如表1所示。

表1 仿真參數值

本文分別從3個方面對算法進行仿真分析：(1)比較2個算法最終規劃出的最優路徑；(2)比較算法在運行過程中，所有螞蟻的運動軌跡；(3)比較2個算法的收斂曲線。

3.1 算法最優路徑仿真實驗

將傳統蟻群算法與改進蟻群算法在相同的環境下進行對比，圖5和圖6分別為2種算法規劃出的最優路徑，圖7和圖8分別為一次路徑規劃中傳統和改進蟻群算法所有螞蟻尋優路徑圖。

圖5 傳統蟻群算法的尋優路徑

圖6 改進蟻群算法的尋優路徑

圖7 傳統蟻群算法的所有螞蟻尋優路徑圖

圖8 改進蟻群算法的所有螞蟻尋優路徑圖

由圖5，圖6對比可看出，改進蟻群算法不僅能準確地搜索到最優路徑，相對于傳統蟻群算法，其路徑拐點也更少，路徑更為平滑。

由圖7，圖8對比可看出，傳統蟻群算法在尋優路徑的過程中，相當于是遍歷整個柵格圖，反映了傳統蟻群算法在前期存在的盲目性搜索以及后期收斂速度慢的問題，而在改進蟻群算法中螞蟻的尋優路徑則更集中于起點與終點之間的重要區域，且更加集中，螞蟻基本沒有探索過地圖的邊緣位置，反映了改進蟻群算法的路徑搜索更具有目標性，搜索效率更高。

3.2 算法收斂仿真實驗

圖9、圖10是2種算法的收斂曲線圖，反應了2種算法的收斂速度，同時亦比較了2種算法規劃出的最優路徑的長短。

圖9 傳統蟻群算法的收斂曲線 圖10 改進蟻群算法是收斂曲線

由圖9、圖10對比可以看出，改進蟻群算法相對于傳統蟻群算法的收斂速度更快，而且搜索到的路徑長度也更短。

表2提取了圖9和圖10中的收斂曲線相關數據，分別比較了螞蟻在整個路徑搜索過程中所走過的最長、最短路徑，算法的迭代次數以及搜索時間。

表2 改進算法與傳統算法的性能比較

從表2中可以看出，改進的ACO在路徑規劃方面比傳統ACO具有更多優勢。 就搜索路徑長度而言，在整個路徑規劃過程中，改進的ACO搜索的最長路徑比傳統ACO的搜索最短路徑短，改進的算法迭代次數更少，搜索時間更短。

4結論

針對傳統ACO在移動機器人路徑規劃中出現的搜索結果不理想，有時無法搜索到最優路徑等的不足，提出一種時空信息交互蟻群算法，通過修改蟻群算法路徑搜索策略，并在螞蟻搜索過程中，加強螞蟻對搜索時間與地圖環境空間的感知，相對于原算法，螞蟻的搜索效率提高了37%，路徑長度縮短了41%，并且路徑質量也得到了改善，為路徑規劃尋優問題提供了新的思路和方法。