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

(長安大學(xué)工程機(jī)械學(xué)院，西安 710064)

0 引言

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

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

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

1 環(huán)境建模

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

(1)

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

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

圖1 柵格地圖

2 蟻群算法理論

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

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

(2)

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

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

(3)

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

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

(4)

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

(5)

(6)

3 改進(jìn)蟻群算法

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

3.1 改進(jìn)轉(zhuǎn)移概率

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

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

(7)

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

(8)

(9)

改進(jìn)轉(zhuǎn)移概率計算公式如(10)所示：

(10)

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

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

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

在初始時刻，螞蟻的運(yùn)動方向必須朝向目標(biāo)柵格，

(11)

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

如果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 改進(jìn)信息素更新原則

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

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

(15)

式中，

(16)

(17)

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

4 算法實現(xiàn)

具體算法實現(xiàn)步驟如下：

步驟1：柵格化模型構(gòu)建；

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

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

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

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

改進(jìn)算法的流程圖如圖2所示。

圖2 改進(jìn)蟻群算法流程圖

5 仿真分析

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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