基于改進蟻群算法的移動機器人路徑規(guī)劃*

李文振，李富康，蔡宗琰，楊 嘉，楊新坤，趙寧寧

(長安大學工程機械學院，西安 710064)

0 引言

移動機器人的路徑規(guī)劃是通過避開障礙物，在其工作空間內找到起點和目標點之間的行程最短且無碰撞的最優(yōu)路徑[1]。為解決路徑規(guī)劃中存在的問題，學者們提出了人工勢場法(APF)[2]、動態(tài)窗口法(DWA)[3]、遺傳算法(GA)[4]、模糊邏輯法(FLA)[5]、神經網絡法(NN)[6]和模擬退火算法(SA)[7]等。然而，這些算法都有一定自身的缺陷，如局部最小化、搜索效率低、收斂時間長、自適應能力差等問題，已不能很好地滿足當下移動機器人獲得最優(yōu)路徑的需求。

意大利研究人員在上世紀90年代提出了蟻群算法[8]，這是一種具有隨機性的啟發(fā)式搜索算法，屬于群智能算法的一種，它源自于自然界中螞蟻的集體覓食行為。由于自身善于解決分配問題的特點，蟻群算法已被成功地應用于作業(yè)分配、生產調度等相關領域[9]，蟻群算法還因為具有良好的自組織性、協(xié)同性和自適應能力強等特點，已逐漸在移動機器人路徑規(guī)劃領域得到應用[10]。

研究表明，蟻群算法中的轉移規(guī)則是找到最短路徑的關鍵，通過改進轉移概率以幫助螞蟻選擇一個有很多安全出口的柵格；并基于全局啟發(fā)式信息使其適應于大規(guī)模應用；同時，建立了一個改進的信息素更新規(guī)則，以提高全局搜索能力和加速收斂速度。

1 環(huán)境建模

三種常用的機器人環(huán)境建模方法有幾何法、拓撲圖法和柵格法。本文借助柵格法創(chuàng)建機器人的作業(yè)環(huán)境，工作區(qū)域被劃分為二進制信息的柵格單元，其中二進制信息表示障礙物柵格為“1”，自由柵格為“0”。柵格地圖為二維環(huán)境，置于正交參考坐標系XOY中，計算每個網格的坐標。通過假設整個柵格具有整數及其長度等于坐標的單位長度，柵格i所對應的坐標公式為：

(1)

式中，mod為取余運算；i為柵格的序號；int為取整運算；Nx表示每行的柵格數；Ny表示每列的柵格數。

圖1為一個10×10柵格地圖，其中黑色柵格代表空間障礙物，白色柵格代表自由空間。從圖中可以看出，機器人可以向前、向后、右、左、右上、右下、左上、左下8個方向移動。

圖1 柵格地圖

2 蟻群算法理論

蟻群算法是一種求解優(yōu)化問題的進化智能啟發(fā)式搜索算法。它是根據螞蟻在尋找從居住地到食物來源的捷徑時的行為而開發(fā)的。在隨機探索環(huán)境尋找食物的過程中，每只螞蟻在經過的路徑上都會釋放出一定量的信息素；一旦有螞蟻找到了食物，螞蟻就會向信息素濃度高的方向移動，因為它們可以察覺到信息素的強度。當螞蟻繼續(xù)向信息素強的路徑前進時，導致該路徑信息素濃度增加，這將會吸引更多的螞蟻到這條路徑上，從而進一步增加該路徑上的信息素濃度，以此類推，螞蟻最終就會找到一條最短路徑。

在每個時間t，螞蟻k從它當前的柵格i移動到一個未訪問的柵格j，基于它們之間的距離和連接它們的邊緣上的信息素的數量。如果存在多個未訪問的柵格，則螞蟻k將根據以下的轉換概率選擇下一個柵格的位置。

(2)

式中，α和β表示路徑選擇過程中影響信息素和啟發(fā)式信息的權重系數，Jk(i)表示未被訪問的柵格集合，τij表示路徑上的信息素濃度，ηij為啟發(fā)式因子，表示從柵格i轉移到柵格j的期望程度。

其中，ηij等于柵格i到柵格j之間距離的倒數，如公式(3)所示：

(3)

當所有的螞蟻完成一次游歷，路徑上的信息素濃度將通過蒸發(fā)原有的信息素和增加螞蟻積累的信息素來進行更新。信息素更新公式為：

τij(t+n)=(1-ρ)τijt+△τij

(4)

其中，ρ(0<ρ<1)表示路徑上信息素的蒸發(fā)系數，1-ρ表示信息素的持久性系數；△τij表示本次迭代中邊ij上信息素的增量，即：

(5)

(6)

3 改進蟻群算法

在傳統(tǒng)的蟻群算法中，概率選擇并不總能保證得出最優(yōu)解，有時在優(yōu)化早期段，算法就可能陷入局部最優(yōu)；同時由于啟發(fā)式搜索的局限性，算法收斂速度較慢。為了提高原有蟻群算法的性能并克服其缺陷，本文進行了以下改進。

3.1 改進轉移概率

轉移概率是一個組合運算，為了讓螞蟻更容易地選擇下一個最佳柵格，它必須是一個可訪問的柵格且有多個出口指向目標。這個概率取決于柵格周圍障礙物的數量。所以，柵格周圍的障礙物越少，概率就越大，柵格就越有吸引力。要確定轉移概率，需要以下組合。

C(8，Nobw)是某一柵格i周圍障礙物可能分布的個數，計算如下：

(7)

C(8-Nobw-1，1)，表示螞蟻k可以離開柵格j的出口數量，表示為：

(8)

(9)

改進轉移概率計算公式如(10)所示：

(10)

3.2 改進全局啟發(fā)式信息

原有蟻群算法中，步長固定于相鄰兩個柵格之間，降低了柵格搜索的效率，導致收斂速度降低，使得算法無法找到最短路徑。為了避免這些問題，采用了無限步長原理[16]，建立了新的全局信息，即在無限的啟發(fā)式搜索和一個擴展視野的基礎上的，移動機器人視野中的所有柵格都可以參與到下一個柵格的選擇過程。

假設i和j分別是當前和下一個柵格，S和E分別是開始和目標柵格，d為兩者之間的距離d(S,i)，d(i,E)，d(S,j)，d(j,E)，d(i,i)和d(S,E)。

在初始時刻，螞蟻的運動方向必須朝向目標柵格，

(11)

在初始時刻之后，我們加入了多樣性啟發(fā)式搜索，我們必須保持既定目標柵格的方向不變。

如果d(S，i)

d(i，E)>d(j，E)，則：

(12)

如果d(S，i)

d(i，E)

(13)

如果d(S，i)>d(S，j)，則：

(14)

3.3 改進信息素更新原則

信息素的數量是選擇一條最優(yōu)路徑的必要因素，然而，這其中含有一定數量的不良信息素，是由最劣的螞蟻產生的，它可以使其他螞蟻移動到目標不可達點或可能導致“早熟”停滯現象。因此，這就要求我們在每次迭代過程中，使最差局部路徑的信息素濃度盡可能的減少，去增加最優(yōu)局部路徑的信息素濃度，以獲得最優(yōu)路徑。

τij(t+1)=(1-ρ)·τij(t)+

(15)

式中，

(16)

(17)

式中，spmax和spmin分別為轉移概率的最大值和最小值，nbest和nworst分別為最優(yōu)和最劣螞蟻的個數，Lbest和Lworst分別為最優(yōu)和最劣局部路徑的長度。

4 算法實現

具體算法實現步驟如下：

步驟1：柵格化模型構建；

步驟2：參數初始化，令t=0，迭代次數NC=0，設定最大迭代次數T，起始點S，目標點E，螞蟻數量m，啟發(fā)因子α，β，蒸發(fā)系數ρ等參數；

步驟3：路徑選擇, 螞蟻根據改進的狀態(tài)轉移概率公式(10)算出下一個柵格j；

步驟4：找出本次迭代的最佳路徑并記錄，利用公式(14)進行信息素更新；

步驟5：判斷是否達到最大迭代次數T，如果滿足條件輸出最佳路徑，否則返回繼續(xù)執(zhí)行步驟2。

改進算法的流程圖如圖2所示。

圖2 改進蟻群算法流程圖

5 仿真分析

為了驗證改進蟻群算法的有效性，在(15×15)、(20×20)的柵格環(huán)境下分別對傳統(tǒng)的蟻群算法和改進后的蟻群算法進行了MATLAB仿真驗證。設定參數值分別為：m=50，T=100，α=1，β=5，ρ=0.5，Q=30。其中，起始點S位于左上角，結束點E位于右下角。

仿真結果如圖3～圖6所示，其中圖3和圖5分別為(15×15)、(20×20)的柵格環(huán)境下兩種蟻群算法的路徑；圖4、圖6為兩種的柵格環(huán)境下的傳統(tǒng)算法和改進算法的收斂曲線。表1為兩種算法的統(tǒng)計結果。

(a) 傳統(tǒng)蟻群算法 (b) 改進蟻群算法圖3 (15×15)柵格環(huán)境下兩種算法的路徑圖

圖4 (15×15)柵格環(huán)境下兩種算法的收斂曲線

(a) 傳統(tǒng)蟻群算法的路徑 (b) 改進蟻群算法的路徑圖5 (20×20)柵格環(huán)境下兩種算法的路徑圖

圖6 (20×20)柵格環(huán)境下兩種算法的收斂曲線

表1 兩種算法統(tǒng)計結果

可以看出，改進蟻群算法比傳統(tǒng)算法具有更短的搜索路徑、更快的收斂速度、更小的迭代次數等特點。因此，優(yōu)化后的蟻群算法與傳統(tǒng)蟻群算法相比具有一定的優(yōu)越性。

6 結束語

本文提出了一種改進的蟻群算法，并在解決移動機器人路徑規(guī)劃問題時與傳統(tǒng)算法進行了比較，證明了改進后蟻群算法的優(yōu)越性。主要在以下三個方面進行了改進：提出了一種基于轉移概率的轉移準則，用以選擇一個安全可達的柵格；采用自由步長的方法，建立了新的全局啟發(fā)式信息原則，增加了可視精度和搜索效率；改進了信息素更新原則，提高了全局搜索能力和收斂速度。仿真結果表明，本文提出的改進蟻群算法在縮短搜索路徑和提高收斂速度方面明顯優(yōu)于傳統(tǒng)蟻群算法。由此可見，研究結果證明了所改進的蟻群算法在解決靜態(tài)環(huán)境下的路徑規(guī)劃問題的潛力。

未來，將進一步針對動態(tài)環(huán)境中的路徑規(guī)劃問題，對所提出的算法進行后續(xù)的優(yōu)化改進以及實驗驗證。