改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究

毛 嘉 琪

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

0 引 言

移動(dòng)機(jī)器人路徑規(guī)劃是當(dāng)下研究熱點(diǎn)，路徑規(guī)劃能力決定了移動(dòng)機(jī)器人的智能水平。路徑規(guī)劃的主要任務(wù)是在具有靜態(tài)或者動(dòng)態(tài)障礙物的環(huán)境中，依據(jù)一定約束條件，尋找到一條沒(méi)有碰撞的路徑。其中路徑規(guī)劃算法顯得極為重要。

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

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

1 環(huán)境模型建立

三種常用的環(huán)境建模方法為網(wǎng)格法、幾何法和拓?fù)鋱D法[4]。柵格法地圖較幾何法和拓?fù)鋱D法具有表達(dá)規(guī)范、易實(shí)現(xiàn)[1]等特點(diǎn)，本文采用柵格法對(duì)環(huán)境進(jìn)行建模。

柵格法中采用1表示障礙物柵格，0表示自由柵格。柵格平臺(tái)是一個(gè)二維環(huán)境，置于正交參考坐標(biāo)系XOY中，計(jì)算每個(gè)網(wǎng)格的坐標(biāo)。假設(shè)整個(gè)網(wǎng)格的標(biāo)號(hào)都是整數(shù)，它們的長(zhǎng)度等于坐標(biāo)的單位長(zhǎng)度[1]，如式(1)所示。

(1)

式中：Nx是每一行的網(wǎng)格數(shù);Ny是每一列的網(wǎng)格數(shù);mod是余數(shù)運(yùn)算;int是整數(shù)運(yùn)算。

圖1為一個(gè)網(wǎng)格映射環(huán)境模型，它每行有20個(gè)網(wǎng)格，每列有20個(gè)網(wǎng)格;黑色網(wǎng)格代表障礙，白色網(wǎng)格代表自由空間。

圖1 柵格法環(huán)境模型

2 A*蟻群算法

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

2.1 基本A*算法分析及其改進(jìn)

A*算法是一種啟發(fā)式搜索算法，它把Dijkstra算法(靠近初始點(diǎn)的結(jié)點(diǎn))和BFS(Breadth First Search)算法[8](靠近目標(biāo)點(diǎn)的結(jié)點(diǎn))的優(yōu)點(diǎn)結(jié)合起來(lái)，在保證搜索效率的同時(shí)得到最優(yōu)路徑。估價(jià)函數(shù)為：

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

(2)

式中：f(n)從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的估計(jì)代價(jià);g(n)在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際代價(jià);h(n)從狀態(tài)n到目標(biāo)狀態(tài)的最佳路徑的估計(jì)代價(jià)。

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

A*算法在搜索的過(guò)程中由于啟發(fā)函數(shù)的幫助可以方向明確地前往目標(biāo)點(diǎn)，但是當(dāng)遇到障礙物的時(shí)候，也會(huì)在障礙物周圍進(jìn)行搜索。對(duì)此，在搜索過(guò)程中采用局部障礙物檢測(cè)方法對(duì)最近障礙物進(jìn)行預(yù)處理，在程序中，先將起始點(diǎn)向目標(biāo)點(diǎn)做一條射線。一旦這條射線觸碰到了障礙，則將障礙進(jìn)行預(yù)處理。如果該射線沒(méi)有碰到障礙，則說(shuō)明前方路徑上沒(méi)有障礙物，那么就可以筆直朝著目標(biāo)點(diǎn)前進(jìn)。

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

圖2 智能車尋路時(shí)所遇障礙

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

圖3 傳統(tǒng)A*搜索范圍

圖4 改進(jìn)A*搜索范圍

2.2 基本蟻群算法

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

2.2.1概率選擇

螞蟻根據(jù)式(3)選擇將要前進(jìn)的節(jié)點(diǎn)。

(3)

(4)

式中：dij為ij間的路徑長(zhǎng)度。

(5)

2.2.2信息素更新

每次所有螞蟻完成一次尋跡后對(duì)全局的信息素進(jìn)行一次更新，所有路徑上的信息素水平將通過(guò)揮發(fā)舊的信息素和添加每只螞蟻儲(chǔ)存的信息素來(lái)更新[14]。信息素更新公式如下：

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

(6)

(7)

(8)

式中：Q是信息素增強(qiáng)系數(shù)，一般為1。

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

2.3.1蟻群算法信息素初始化

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

τ(R)=NC

(9)

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

2.3.2啟發(fā)函數(shù)改進(jìn)

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

某網(wǎng)格j周圍障礙物所有可能分布的情況個(gè)數(shù)可以計(jì)算為：

(10)

式中：Nobs為網(wǎng)格j周圍的障礙物個(gè)數(shù)。

網(wǎng)格j的出口分布情況個(gè)數(shù)可以計(jì)算為：

(11)

SPij計(jì)算如下：

(12)

新的啟發(fā)函數(shù)定義如下：

(13)

式中：djs為下一節(jié)點(diǎn)j與終點(diǎn)s之間的距離，增加了網(wǎng)格j與目標(biāo)點(diǎn)的距離對(duì)啟發(fā)函數(shù)的影響，同時(shí)增加了目標(biāo)點(diǎn)對(duì)路徑的吸引力。SPij增加了節(jié)點(diǎn)障礙物個(gè)數(shù)對(duì)節(jié)點(diǎn)選擇的影響，節(jié)點(diǎn)j周圍的障礙物越多，SPij越小，啟發(fā)函數(shù)就越小，選擇該節(jié)點(diǎn)的概率就越小。

2.3.3自適應(yīng)信息素更新方式

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

(14)

(15)

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

2.3.4動(dòng)態(tài)調(diào)整信息素?fù)]發(fā)因子

信息素?fù)]發(fā)因子ρ通常為一固定常數(shù)，可是若在全局搜索時(shí)ρ若為常數(shù)會(huì)降低搜索效率，現(xiàn)將ρ改進(jìn)為：

(16)

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

引入拐點(diǎn)參數(shù)來(lái)表征信息素的變化，當(dāng)GDmT小于GDmT-1時(shí)，路徑長(zhǎng)度更優(yōu)更平滑，此時(shí)減小ρ值，加快算法收斂速度，當(dāng)GDmT大于GDmT-1時(shí)，增加ρ值，加強(qiáng)算法全局搜索能力。

2.4 改進(jìn)算法的步驟

步驟1環(huán)境建模。

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

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

步驟4將所有螞蟻置于起點(diǎn)準(zhǔn)備開(kāi)始搜索。

步驟5根據(jù)轉(zhuǎn)移概率選擇下一節(jié)點(diǎn)。

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

步驟7重復(fù)步驟5-步驟6。

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

步驟9判斷是否達(dá)到迭代次數(shù)，達(dá)到設(shè)定值則結(jié)束程序，否則轉(zhuǎn)步驟5。

算法流程如圖5所示。

圖5 算法流程

3 仿真實(shí)驗(yàn)

1) 將本文算法與文獻(xiàn)[3]算法、文獻(xiàn)[4]算法、傳統(tǒng)算法進(jìn)行比較。在文獻(xiàn)[3]、文獻(xiàn)[4]中的柵格環(huán)境(20×20)進(jìn)行仿真實(shí)驗(yàn)。

本文參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

圖6中虛線為文獻(xiàn)[4]算法規(guī)劃路徑，實(shí)線為本文算法規(guī)劃路徑，兩算法最短路徑長(zhǎng)度與迭代次數(shù)的關(guān)系如圖7所示。

圖6 文獻(xiàn)[4]算法和本文算法的路徑規(guī)劃圖

圖7 文獻(xiàn)[4]算法和本文算法的收斂曲線

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

表2 文獻(xiàn)[4]算法與本文算法對(duì)比

圖8中虛線為文獻(xiàn)[3]算法規(guī)劃路徑，實(shí)線為本文算法規(guī)劃路徑，兩算法最短路徑長(zhǎng)度與迭代次數(shù)的關(guān)系如圖9所示。

圖8 文獻(xiàn)[3]算法和本文算法的路徑規(guī)劃圖

圖9 文獻(xiàn)[3]算法和本文算法的收斂曲線

由表3可知，在相同復(fù)雜度(20×20)和相同障礙物的情況下，本文算法與文獻(xiàn)[3]算法相比最優(yōu)路徑長(zhǎng)度相同，平均路徑長(zhǎng)度和迭代次數(shù)更優(yōu)。

表3 文獻(xiàn)[3]算法與本文算法對(duì)比

2) 在不同復(fù)雜程度的靜態(tài)環(huán)境中進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。

(1) 在10×10柵格環(huán)境中進(jìn)行實(shí)驗(yàn)，路徑規(guī)劃結(jié)果如圖10所示，路徑長(zhǎng)度為13.899 m，算法收斂曲線如圖11所示。

圖10 10×10路徑規(guī)劃圖

圖11 10×10柵格環(huán)境中的收斂曲線

(2) 在30×30柵格環(huán)境中進(jìn)行實(shí)驗(yàn)，路徑規(guī)劃結(jié)果如圖12所示，路徑長(zhǎng)度為43.355 m，算法收斂曲線如圖13所示。

圖12 30×30路徑規(guī)劃圖

圖13 30×30柵格環(huán)境中的收斂曲線

通過(guò)從簡(jiǎn)單到復(fù)雜的靜態(tài)柵格環(huán)境中進(jìn)行的多個(gè)仿真實(shí)驗(yàn)可以看出，本文算法不僅可以在簡(jiǎn)單的環(huán)境中規(guī)劃出最優(yōu)路徑，在復(fù)雜的環(huán)境中也能規(guī)劃出最優(yōu)的路徑，且迭代次數(shù)也較少，收斂速度快，適用于不同復(fù)雜度的環(huán)境。

4 結(jié) 語(yǔ)

針對(duì)傳統(tǒng)蟻群算法在機(jī)器人路徑規(guī)劃中存在搜索時(shí)間較長(zhǎng)、容易陷入局部最優(yōu)、收斂速度慢等問(wèn)題，本文對(duì)啟發(fā)函數(shù)、信息素更新、信息素?fù)]發(fā)因子進(jìn)行了相應(yīng)改進(jìn)。仿真對(duì)比實(shí)驗(yàn)表明，本文算法不僅提高了搜索效率，加快了收斂速度，還可以在一定程度上提高解的穩(wěn)定性。同時(shí)在不同復(fù)雜度下進(jìn)行仿真，表明了本文算法的可行性與有效性。

本文主要針對(duì)靜態(tài)障礙物情況下的全局路徑規(guī)劃，沒(méi)有考慮存在動(dòng)態(tài)障礙物時(shí)的情況，這也是本文的不足以及后續(xù)研究重點(diǎn)。