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

毛 嘉 琪

(湘潭大學信息工程學院 湖南 湘潭 411100)

0 引 言

移動機器人路徑規劃是當下研究熱點，路徑規劃能力決定了移動機器人的智能水平。路徑規劃的主要任務是在具有靜態或者動態障礙物的環境中，依據一定約束條件，尋找到一條沒有碰撞的路徑。其中路徑規劃算法顯得極為重要。

現有常見路徑規劃算法有蟻群算法[1-4]、Dijkstra算法[5-8]、A*算法[6-8]、人工勢場法[9-10]、遺傳算法[11-12]等。在A*算法中，啟發函數無法完全確定，可能存在多個最小值，極易陷入死循環。人工勢場法在靠近障礙物時易產生震蕩和陷入局部最優點，使機器人難以到達目標點。遺傳算法涉及大量的個體計算，同時也容易陷入局部最優點，而蟻群算法因具有并行性、強魯棒性[13]等優勢在移動機器人路徑規劃問題的解決中得到廣泛應用，傳統蟻群算法主要是用于解決旅行商問題(Travelling Salesman Problem,TSP)。文獻[1]改進了啟發函數以及信息素揮發因子的更新規則，引入了以節點周圍障礙物分布個數為變量的刺激函數，有效提高了算法的性能。文獻[3]將當前節點和目標點的聯系引入到啟發函數中，提高了算法的收斂速度。文獻[5]加入了進化選擇概率，通過此概率來選擇不同的概率轉移公式，并且使用動態閉環調節來改進進化選擇概率，提高了算法的抗干擾能力。文獻[8]定義了一種新的引力函數，提高了算法的效率。文獻[9]分析了蟻群優化中較為關鍵的參數，自適應調整算法參數，提高了算法的精度。

本文針對蟻群算法進行路徑規劃時存在收斂速度慢、易陷入局部最優以及初期信息素匱乏使得搜索初期比較盲目等問題，提出一種改進的蟻群算法。該算法首先使用改進的A*算法快速得到一條較優路徑，來優化信息素初值。引入文獻[1]的刺激函數到蟻群算法的啟發函數中，提高路徑避障能力。根據前后兩次迭代的路徑長度調整信息素更新，提高算法收斂速度。同時加入拐點參數來改變信息素揮發因子，使得算法路徑搜索效率更高，更加穩定。在MATLAB軟件中的仿真實驗表明了該算法的有效性與可行性。

1 環境模型建立

三種常用的環境建模方法為網格法、幾何法和拓撲圖法[4]。柵格法地圖較幾何法和拓撲圖法具有表達規范、易實現[1]等特點，本文采用柵格法對環境進行建模。

柵格法中采用1表示障礙物柵格，0表示自由柵格。柵格平臺是一個二維環境，置于正交參考坐標系XOY中，計算每個網格的坐標。假設整個網格的標號都是整數，它們的長度等于坐標的單位長度[1]，如式(1)所示。

(1)

式中：Nx是每一行的網格數;Ny是每一列的網格數;mod是余數運算;int是整數運算。

圖1為一個網格映射環境模型，它每行有20個網格，每列有20個網格;黑色網格代表障礙，白色網格代表自由空間。

圖1 柵格法環境模型

2 A*蟻群算法

A*蟻群算法的主要原理為借用改進A*算法先得到一條相對較優的路徑并將此路徑記為R，提高此路徑上的信息素初值。在此基礎上用改進蟻群算法繼續搜索最優路徑。這樣既可以加快搜索速度，也可以減少蟻群算法搜索初期的盲目性。

2.1 基本A*算法分析及其改進

A*算法是一種啟發式搜索算法，它把Dijkstra算法(靠近初始點的結點)和BFS(Breadth First Search)算法[8](靠近目標點的結點)的優點結合起來，在保證搜索效率的同時得到最優路徑。估價函數為：

f(n)=g(n)+h(n)

(2)

式中：f(n)從初始狀態經由狀態n到目標狀態的估計代價;g(n)在狀態空間中從初始狀態到狀態n的實際代價;h(n)從狀態n到目標狀態的最佳路徑的估計代價。

兩種極端情況分別為：(1) 若h(n)為0，則只有g(n)起作用，此時A*演變成Dijkstra算法，這保證能找到最短路徑；(2) 若h(n)遠大于g(n)，僅h(n)起作用，A*演變成BFS算法。

A*算法在搜索的過程中由于啟發函數的幫助可以方向明確地前往目標點，但是當遇到障礙物的時候，也會在障礙物周圍進行搜索。對此，在搜索過程中采用局部障礙物檢測方法對最近障礙物進行預處理，在程序中，先將起始點向目標點做一條射線。一旦這條射線觸碰到了障礙，則將障礙進行預處理。如果該射線沒有碰到障礙，則說明前方路徑上沒有障礙物，那么就可以筆直朝著目標點前進。

首先記錄下柵格圖的障礙物的邊界點，障礙物的邊界點就是障礙物的起始點或者終止點(由起始點、方向向量、障礙物長度共同得到)，如果是兩障礙物相交，那么障礙物交點不會被當作是邊界點，如圖2所示。

圖2 智能車尋路時所遇障礙

圖2中A、B為障礙物邊界點，O為起始點，C為目標點)。然后需要計算OA+AC和OB+BC的繞行距離。假設此時選擇從B點繞行，那么就將目標點臨時改為B點，先規劃出從O到B的路徑，再將B點作為起始點，C點作為終點重復之前步驟。仿真對比結果如圖3、圖4所示。

圖3 傳統A*搜索范圍

圖4 改進A*搜索范圍

2.2 基本蟻群算法

蟻群算法是一種模擬螞蟻覓食行為的模擬優化算法，它是由意大利學者Dorigo等[12]于1991年首先提出，并首先使用在解決TSP(旅行商問題)上。之后，又系統研究了蟻群算法的基本原理和數學模型。

2.2.1概率選擇

螞蟻根據式(3)選擇將要前進的節點。

(3)

(4)

式中：dij為ij間的路徑長度。

(5)

2.2.2信息素更新

每次所有螞蟻完成一次尋跡后對全局的信息素進行一次更新，所有路徑上的信息素水平將通過揮發舊的信息素和添加每只螞蟻儲存的信息素來更新[14]。信息素更新公式如下：

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

(6)

(7)

(8)

式中：Q是信息素增強系數，一般為1。

2.3 改進蟻群算法

2.3.1蟻群算法信息素初始化

將之前改進A*算法得到的路徑記為R，并將路徑R上的信息素初始化為：

τ(R)=NC

(9)

式中：N為大于零的常數，其余路徑上的信息素仍然初始化為常數C。

2.3.2啟發函數改進

為了讓螞蟻更容易地選擇最佳的下一個網格，下一個網格必須是一個可訪問的網格，并且有多個出口指向目標。這個概率取決于網格周圍障礙物的數量。網格周圍的障礙物越少，概率越大，網格就越有吸引力。這里引入文獻[1]中的刺激概率SPij。

某網格j周圍障礙物所有可能分布的情況個數可以計算為：

(10)

式中：Nobs為網格j周圍的障礙物個數。

網格j的出口分布情況個數可以計算為：

(11)

SPij計算如下：

(12)

新的啟發函數定義如下：

(13)

式中：djs為下一節點j與終點s之間的距離，增加了網格j與目標點的距離對啟發函數的影響，同時增加了目標點對路徑的吸引力。SPij增加了節點障礙物個數對節點選擇的影響，節點j周圍的障礙物越多，SPij越小，啟發函數就越小，選擇該節點的概率就越小。

2.3.3自適應信息素更新方式

為使螞蟻能更快地搜索到最短路徑，將信息素更新規則修改如下：

(14)

(15)

當上一路徑Lk-1長度大于當前路徑Lk，λ>1，則增加Lk的信息素增量。若上一路徑Lk-1長度小于當前路徑Lk，λ<1，則減少Lk的信息素增量。

2.3.4動態調整信息素揮發因子

信息素揮發因子ρ通常為一固定常數，可是若在全局搜索時ρ若為常數會降低搜索效率，現將ρ改進為：

(16)

式中：GDmT、GDmT-1分別為第T次迭代與第T-1次迭代中拐點參數平均值。機器人所尋路徑中只有三種角，分別為銳角、直角、鈍角，其相應值分別記為3、2、1，拐點參數值即所有角度值之和。

引入拐點參數來表征信息素的變化，當GDmT小于GDmT-1時，路徑長度更優更平滑，此時減小ρ值，加快算法收斂速度，當GDmT大于GDmT-1時，增加ρ值，加強算法全局搜索能力。

2.4 改進算法的步驟

步驟1環境建模。

步驟2利用改進A*算法得到一條相對最優路徑，并提高將此路徑上的信息素初始值。

步驟3初始化蟻群算法參數，例如迭代次數、信息素因子和啟發函數因子等。

步驟4將所有螞蟻置于起點準備開始搜索。

步驟5根據轉移概率選擇下一節點。

步驟6在螞蟻k完成搜索后，進行信息素的更新。

步驟7重復步驟5-步驟6。

步驟8將所有螞蟻重置到起點，清空禁忌表。

步驟9判斷是否達到迭代次數，達到設定值則結束程序，否則轉步驟5。

算法流程如圖5所示。

圖5 算法流程

3 仿真實驗

1) 將本文算法與文獻[3]算法、文獻[4]算法、傳統算法進行比較。在文獻[3]、文獻[4]中的柵格環境(20×20)進行仿真實驗。

本文參數設置如表1所示。

表1 參數設置

圖6中虛線為文獻[4]算法規劃路徑，實線為本文算法規劃路徑，兩算法最短路徑長度與迭代次數的關系如圖7所示。

圖6 文獻[4]算法和本文算法的路徑規劃圖

圖7 文獻[4]算法和本文算法的收斂曲線

由表2可知，在相同復雜度(20×20)和相同障礙物的情況下，本文算法與文獻[4]算法路徑長度相同，但是平均路徑長度以及迭代次數均優于文獻[4]算法，特別是由仿真10次的結果可以看出，本文算法比文獻[4]算法有著更好的穩定性。

表2 文獻[4]算法與本文算法對比

圖8中虛線為文獻[3]算法規劃路徑，實線為本文算法規劃路徑，兩算法最短路徑長度與迭代次數的關系如圖9所示。

圖8 文獻[3]算法和本文算法的路徑規劃圖

圖9 文獻[3]算法和本文算法的收斂曲線

由表3可知，在相同復雜度(20×20)和相同障礙物的情況下，本文算法與文獻[3]算法相比最優路徑長度相同，平均路徑長度和迭代次數更優。

表3 文獻[3]算法與本文算法對比

2) 在不同復雜程度的靜態環境中進行仿真實驗，實驗參數設置如表1所示。

(1) 在10×10柵格環境中進行實驗，路徑規劃結果如圖10所示，路徑長度為13.899 m，算法收斂曲線如圖11所示。

圖10 10×10路徑規劃圖

圖11 10×10柵格環境中的收斂曲線

(2) 在30×30柵格環境中進行實驗，路徑規劃結果如圖12所示，路徑長度為43.355 m，算法收斂曲線如圖13所示。

圖12 30×30路徑規劃圖

圖13 30×30柵格環境中的收斂曲線

通過從簡單到復雜的靜態柵格環境中進行的多個仿真實驗可以看出，本文算法不僅可以在簡單的環境中規劃出最優路徑，在復雜的環境中也能規劃出最優的路徑，且迭代次數也較少，收斂速度快，適用于不同復雜度的環境。

4 結 語

針對傳統蟻群算法在機器人路徑規劃中存在搜索時間較長、容易陷入局部最優、收斂速度慢等問題，本文對啟發函數、信息素更新、信息素揮發因子進行了相應改進。仿真對比實驗表明，本文算法不僅提高了搜索效率，加快了收斂速度，還可以在一定程度上提高解的穩定性。同時在不同復雜度下進行仿真，表明了本文算法的可行性與有效性。

本文主要針對靜態障礙物情況下的全局路徑規劃，沒有考慮存在動態障礙物時的情況，這也是本文的不足以及后續研究重點。