孫海洋　夏慶鋒　楊冠男

摘要：

蟻群算法是機(jī)器人路徑規(guī)劃中的經(jīng)典算法之一，在二維靜態(tài)環(huán)境中，傳統(tǒng)蟻群算法在機(jī)器人路徑規(guī)劃中還存在一些缺點(diǎn)，如算法收斂較慢、容易陷入局部最優(yōu)并可能導(dǎo)致算法停滯等。針對(duì)這些缺陷，對(duì)傳統(tǒng)蟻群算法提出相應(yīng)改進(jìn)，引入自適應(yīng)啟發(fā)式因子、拐點(diǎn)個(gè)數(shù)等參數(shù)，并采用不同啟發(fā)式因子對(duì)隨機(jī)概率進(jìn)行更新。使用Matlab對(duì)改進(jìn)前后算法的收斂速度、避障尋徑和最短路徑長(zhǎng)度等進(jìn)行對(duì)比分析。結(jié)果顯示，改進(jìn)后的算法較傳統(tǒng)算法不僅可以使機(jī)器人有效避開所有障礙物，而且能夠高效尋找到最短路徑，在很大程度上避免了算法陷入局部最優(yōu)。

關(guān)鍵詞：

路徑規(guī)劃；蟻群算法；最優(yōu)路徑；拐點(diǎn)個(gè)數(shù)；啟發(fā)式因子

DOIDOI：10.11907/rjdk.182144

中圖分類號(hào)：TP303

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2018）009002203

英文標(biāo)題Research on Robot Path Planning Based on Improved Ant Colony Algorithm

——副標(biāo)題

英文作者SUN Haiyang，XIA Qingfeng，YANG Guannan，GUO Lili

英文作者單位（School of Information Science and Engineering，Jinling College of Nanjing University， Nanjing 210000，China）

英文摘要Abstract：Ant colony algorithm is one of the classical algorithms in robot path planning.The traditional ant colony algorithm still has some shortcomings in robot path planning. For example， the algorithm converges slowly， it is easy to fall into local optimum， and it may cause the algorithm to stagnate. For these defects， the traditional ant colony algorithm is proposed to improve accordingly， adaptive heuristic factors and parameters such as the number of inflection points are introduced， and different heuristic factors are used to update the random probability. Matlab simulation is used to compare the convergence speed， obstacle avoidance path and the shortest path length of the improved algorithm. The results show that compared with the traditional algorithm， the improved algorithm can not only make the robot avoid all obstacles efficiently， but also can find the shortest path efficiently， and it also avoids the defect of falling into local optimum to a large extent.

英文關(guān)鍵詞Key Words：route plan；ant colony algorithm；optimal path；the number of inflection points；heuristic factor

0引言

蟻群算法由意大利學(xué)者Dorigo、Maniezzo等于20世紀(jì)90年代首次提出，是來自大自然的隨機(jī)搜索尋優(yōu)算法，現(xiàn)已陸續(xù)應(yīng)用到組合優(yōu)化、通訊等各個(gè)領(lǐng)域，具有很好的適應(yīng)性[13]。蟻群算法在機(jī)器人路徑規(guī)劃應(yīng)用中占有非常重要的地位，但傳統(tǒng)蟻群算法在機(jī)器人路徑規(guī)劃中還存在一些問題，如收斂速度慢、容易陷入局部最優(yōu)等[45]。

文獻(xiàn)[6]利用蟻群算法的進(jìn)化機(jī)制，融合多路徑選擇和概率選擇策略，尋找最短行走路徑，在一定程度上能有效求解機(jī)器人路徑規(guī)劃問題。文獻(xiàn)[2]、文獻(xiàn)[7]提出動(dòng)態(tài)有限區(qū)域搜索策略，將蟻群算法與A*算法相結(jié)合，增強(qiáng)了全局搜索能力，縮小了搜索范圍，提高了搜索效率，得到較短的尋優(yōu)時(shí)間，但在一定程度上增加了算法復(fù)雜度。文獻(xiàn)[8]提出的螞蟻相遇策略提高了算法搜索效率，通過設(shè)置信息素感應(yīng)閾值擴(kuò)大算法前期的搜索范圍，提高了收斂速度。文獻(xiàn)[9]提出參數(shù)自適應(yīng)的偽隨機(jī)轉(zhuǎn)移策略，有助于螞蟻尋找全局最優(yōu)解。仿真結(jié)果表明，新算法明顯提高了收斂速度和尋優(yōu)能力，能夠較好地滿足復(fù)雜環(huán)境下機(jī)器人路徑規(guī)劃的需求。

本文提出一種自適應(yīng)啟發(fā)式因子蟻群算法，以提高算法的收斂速度、全局搜索能力，并引入拐點(diǎn)個(gè)數(shù)，以進(jìn)一步縮短所尋路徑并起到平滑處理的作用。通過Matlab仿真對(duì)比驗(yàn)證，得出改進(jìn)算法的有效性和優(yōu)越性。

1傳統(tǒng)蟻群算法在路徑規(guī)劃中的應(yīng)用

1.1路徑規(guī)劃流程

傳統(tǒng)蟻群算法應(yīng)用于機(jī)器人路徑優(yōu)化問題的主要步驟如下：

（1）使用柵格法構(gòu)造機(jī)器人尋徑地圖。

（2）初始化信息素矩陣，假設(shè)所有位置的初始信息素是相同的，并設(shè)置初始化參數(shù)及起止坐標(biāo)[10]。

（3）根據(jù)當(dāng)前信息素算出下一步可前往每一個(gè)節(jié)點(diǎn)的概率，并計(jì)算下一個(gè)節(jié)點(diǎn)[1011]的選擇概率pkij（t），如式（1）所示。

pkij（t）=[τij（t）]α·[ηij]β∑k∈{N-tabuk}[τij（t）]α·[ηij]β j∈{N-tabuk}0其它（1）

其中，τij（t）表示地圖中坐標(biāo)為（i，j）點(diǎn)的信息素濃度；ηij表示啟發(fā)式信息值；α、β表示信息素濃度及啟發(fā)式信息值的權(quán)重參數(shù)。

（4）更新路徑以及路徑長(zhǎng)度。

（5）重復(fù)步驟（3）、步驟（4），直到螞蟻?zhàn)叩浇K點(diǎn)坐標(biāo)或陷入死循環(huán)為止。

（6）重復(fù)步驟（3）-步驟（5），直到某一代m只螞蟻全部尋徑完畢。

（7）根據(jù)式（2）、式（3）更新信息素的矩陣，沒有走到目的地的螞蟻不計(jì)在其中。

τij（t+1）=（1-ρ）τij（t）+Δτij（2）

Δτij（t）=QLk（t），螞蟻k經(jīng)過i，j

0，螞蟻k不經(jīng)過i，j（3）

重復(fù)步驟（3）-步驟（7），直到n代螞蟻全部迭代結(jié)束。算法流程如圖1所示。

1.2啟發(fā)式因子

啟發(fā)式因子采用自適應(yīng)方式。設(shè)蟻群算法的啟發(fā)式因子為α、β，其中α表示信息啟發(fā)式因子，是之前螞蟻所累積信息素對(duì)后面螞蟻的運(yùn)動(dòng)起到的作用，其值越小，說明之前螞蟻所累積的信息素對(duì)后面螞蟻的作用越小，螞蟻之間的合作性就越小[1213]，反之，螞蟻之間的合作性就越大，但同時(shí)隨機(jī)選擇的概率也會(huì)降低，則不容易陷入局部最優(yōu)的情況；β表示信息素期望啟發(fā)式因子，是對(duì)啟發(fā)式信息在路徑規(guī)劃中的作用，其值越大，算法速度會(huì)相應(yīng)增加，選擇概率會(huì)越小，相反，如果其值越小，啟發(fā)式信息所起到的作用就越小，隨機(jī)性就越大[13]。所以需根據(jù)是否存在障礙物對(duì)α、β選擇不同的值。例如，當(dāng)周圍存在障礙時(shí)，其值可設(shè)置為α=10、β=70；反之，其值可設(shè)置為α=1、β=7。

1.3 基于固定啟發(fā)式因子的蟻群算法仿真

對(duì)環(huán)境的建模采用柵格法[14]，黑色柵格表示障礙物，白色柵格表示自由空間[1516]。采用20×20的柵格建立環(huán)境模型，對(duì)基于傳統(tǒng)蟻群算法的機(jī)器人路徑規(guī)劃進(jìn)行Matlab仿真驗(yàn)證。對(duì)函數(shù)中各個(gè)參數(shù)進(jìn)行初始化：設(shè)問題規(guī)模的大小為M，螞蟻個(gè)數(shù)為N，迭代次數(shù)為K，信息素權(quán)重參數(shù)為α，啟發(fā)因子權(quán)重參數(shù)為β，信息素增加強(qiáng)度系數(shù)為Q，信息素蒸發(fā)系數(shù)為ρ。

在滿足K=200、M=50、N=100、ρ=0.8、Q=200的情況下，啟發(fā)式因子設(shè)計(jì)為α=1、β=10，對(duì)該傳統(tǒng)固定啟發(fā)式因子的蟻群算法進(jìn)行Matlab仿真，得到機(jī)器人運(yùn)動(dòng)軌跡及算法收斂曲線分別如圖2（a）、圖2（b）所示。

由圖2（a）可以看出，該傳統(tǒng)算法的路徑規(guī)劃雖也可從起點(diǎn)到達(dá)終點(diǎn)，且能夠避開所有障礙，但存在一段“迂回路徑”，故不是最短路徑。

由圖2（b）可以看出，在啟發(fā)式因子α=1、β=10的情況下，算法大概在第160次迭代之后趨于穩(wěn)定，最短路徑長(zhǎng)度約為34。

1.4仿真結(jié)果分析

基于傳統(tǒng)固定啟發(fā)式因子的蟻群算法，機(jī)器人也可以繞過所有障礙尋到最優(yōu)路徑[1720]。通過圖2（b）可以看出，在該地圖環(huán)境下，采用傳統(tǒng)固定啟發(fā)式因子蟻群算法的機(jī)器人路徑規(guī)劃方案，大約需經(jīng)過160次迭代之后，其最短路徑長(zhǎng)度才趨于一個(gè)穩(wěn)定值，該穩(wěn)定值即為最短路徑長(zhǎng)度，約為34。由此可知，雖然傳統(tǒng)蟻群算法也能尋找到最短路徑，但其收斂速度較慢。

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

本文不采用固定的啟發(fā)式因子，而使用能夠根據(jù)環(huán)境自適應(yīng)調(diào)整的啟發(fā)式因子[21]。

修改信息素的更新規(guī)則，為了減少機(jī)器人運(yùn)動(dòng)的時(shí)間，加入拐點(diǎn)個(gè)數(shù)作為路徑的評(píng)價(jià)之一。在機(jī)器人仿真運(yùn)動(dòng)中只存在3種可能角度：銳角、直角、鈍角，若賦予其權(quán)重分別記為3、2、1，在螞蟻尋優(yōu)完成之后計(jì)算該路徑上拐點(diǎn)的個(gè)數(shù)，個(gè)數(shù)越小路徑就越平滑，路徑長(zhǎng)度也就越短。更新后的信息素公式如式（4）所示，其中GD為第k只螞蟻尋到的路徑拐點(diǎn)個(gè)數(shù)。

Δτk（i，j）=QLk+GD（4）

在初始參數(shù)為K=200、M=50、ρ=0.8、Q=200的環(huán)境下，對(duì)引入拐點(diǎn)個(gè)數(shù)因子并采用自適應(yīng)式啟發(fā)因子的改進(jìn)蟻群算法進(jìn)行Matlab仿真。

由圖3（a）可以直觀地看出，改進(jìn)算法已經(jīng)去掉了傳統(tǒng)算法對(duì)應(yīng)路徑軌跡中多走的一段“迂回路徑”。

由圖3（b）可知，引入拐點(diǎn)個(gè)數(shù)及自適應(yīng)式啟發(fā)因子的改進(jìn)蟻群算法，大約在第9次迭代之后收斂于穩(wěn)定值，最小路徑長(zhǎng)度約為31。

3結(jié)語

針對(duì)傳統(tǒng)蟻群算法在路徑規(guī)劃方案中存在的收斂速度慢、容易陷入局部最優(yōu)等問題，本文引入了自適應(yīng)式啟發(fā)因子、設(shè)置路徑拐點(diǎn)個(gè)數(shù)等參數(shù)的改進(jìn)蟻群算法。通過Matlab仿真實(shí)驗(yàn)，改進(jìn)算法在一定程度上避免了陷入局部最優(yōu)，大大提高了收斂速度，并且所尋路徑更短、更圓滑，證明了改進(jìn)算法的有效性和可行性。

參考文獻(xiàn)參考文獻(xiàn)：

[1]張美玉，黃翰，郝志峰，等.基于蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用，2005（25）：3437.

[2]葛延峰，陳濤，孔祥勇，等.改進(jìn)蟻群算法在城市汽車導(dǎo)航中的應(yīng)用[J].控制工程，2016，23（1）：133137.

[3]葛斌，韓江洪，魏臻，等.最小最大車輛路徑問題的動(dòng)態(tài)自適應(yīng)蟻群優(yōu)化算法[J].模式識(shí)別與人工智能，2015，28（10）：930938.

[4]TUNCER A，YILDIRIM M.Dynamic path planning of mobile robots with improved genetic algotithm[J].Comptuers & Electrical Engineering，2012，38（6）：15641572.

[5]DEEPAK B L，PARHI D R，KUNDU S.Innate immune based path path planner of an autonomous mobile robot [J].Procedia Engineering，2012，38：26632671.

[6]柴寅，唐秋華，鄧明星，等.機(jī)器人路徑規(guī)劃的柵格模型構(gòu)建與蟻群算法求解[J].機(jī)械設(shè)計(jì)與制造，2016（4）：178181.

[7]李龍澍，喻環(huán).改進(jìn)蟻群算法在復(fù)雜環(huán)境中機(jī)器人路徑規(guī)劃上的應(yīng)用[J].小型微型計(jì)算機(jī)系統(tǒng)，2017，38（9）：20672071.

[8]王志中.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].機(jī)械設(shè)計(jì)與制造，2018（1）：242244.

[9]王欽釗，程金勇，李小龍.復(fù)雜環(huán)境下機(jī)器人路徑規(guī)劃方法研究[J].計(jì)算機(jī)仿真，2017，34（10）：296300.

[10]張成，凌有鑄，陳孟元.改進(jìn)蟻群算法求解移動(dòng)機(jī)器人路徑規(guī)劃[J].電子測(cè)量與儀器學(xué)報(bào)，2016（11）：17581764.

[11]柳長(zhǎng)安，鄢小虎，劉春陽(yáng)，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J].電子學(xué)報(bào)，2011（5）：12201224.

[12]吳虎發(fā)，李學(xué)俊，章玉龍.改進(jìn)的蟻群算法求最短路徑問題[J].計(jì)算機(jī)仿真，2012 （8）：215218.

[13]THOMAS STUTZLE T，HOLGER H HOOS.Maxmin ant system[J].Future Generation Computer Systems，2000，16（8）：889914.

[14]卜新蘋，蘇虎，鄒偉，等.基于復(fù)雜環(huán)境非均勻建模的蟻群路徑規(guī)劃[J].機(jī)器人，2016，38（3）：276284.

[15]曾明如，徐小勇，劉亮，等.改進(jìn)的勢(shì)場(chǎng)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（22）：3337.

[16]游曉明，劉升，呂金秋.一種動(dòng)態(tài)搜索策略的蟻群算法及其在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].控制與決策，2017，32（3）：552556.

[17]袁亞博，劉羿，吳斌.改進(jìn)蟻群算法求解最短路徑問題[J].計(jì)算機(jī)工程與應(yīng)用，2016（6）：812.

[18]葛延峰，陳濤，孔祥勇，等.改進(jìn)蟻群算法在城市汽車導(dǎo)航中的應(yīng)用[J].控制工程，2016（1）：133137.

[19]劉建華，楊建國(guó)，劉華平，等.基于勢(shì)場(chǎng)蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015，46（9）：1827.

[20]游曉明，劉升，呂金秋.一種動(dòng)態(tài)搜索策略的蟻群算法及其在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].控制與決策，2017，32（3）：552556.

[21]屈鴻，黃利偉，柯星.動(dòng)態(tài)環(huán)境下基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究[J].電子科技大學(xué)學(xué)報(bào)，2015，44（2）：260265.

責(zé)任編輯（責(zé)任編輯：何麗）