孫海洋　夏慶鋒　楊冠男

摘要：

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

關鍵詞：

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

DOIDOI：10.11907/rjdk.182144

中圖分類號：TP303

文獻標識碼：A文章編號文章編號：16727800（2018）009002203

英文標題Research on Robot Path Planning Based on Improved Ant Colony Algorithm

——副標題

英文作者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.

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

0引言

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

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

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

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

1.1路徑規(guī)劃流程

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

（1）使用柵格法構造機器人尋徑地圖。

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

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

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

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

（4）更新路徑以及路徑長度。

（5）重復步驟（3）、步驟（4），直到螞蟻走到終點坐標或陷入死循環(huán)為止。

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

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

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

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

0，螞蟻k不經過i，j（3）

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

1.2啟發(fā)式因子

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

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

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

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

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

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

1.4仿真結果分析

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

2蟻群算法改進

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

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

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

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

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

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

3結語

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

參考文獻參考文獻：

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

[2]葛延峰，陳濤，孔祥勇，等.改進蟻群算法在城市汽車導航中的應用[J].控制工程，2016，23（1）：133137.

[3]葛斌，韓江洪，魏臻，等.最小最大車輛路徑問題的動態(tài)自適應蟻群優(yōu)化算法[J].模式識別與人工智能，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]柴寅，唐秋華，鄧明星，等.機器人路徑規(guī)劃的柵格模型構建與蟻群算法求解[J].機械設計與制造，2016（4）：178181.

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

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

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

[10]張成，凌有鑄，陳孟元.改進蟻群算法求解移動機器人路徑規(guī)劃[J].電子測量與儀器學報，2016（11）：17581764.

[11]柳長安，鄢小虎，劉春陽，等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學報，2011（5）：12201224.

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

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

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

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

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

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

[18]葛延峰，陳濤，孔祥勇，等.改進蟻群算法在城市汽車導航中的應用[J].控制工程，2016（1）：133137.

[19]劉建華，楊建國，劉華平，等.基于勢場蟻群算法的移動機器人全局路徑規(guī)劃方法[J].農業(yè)機械學報，2015，46（9）：1827.

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

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

責任編輯（責任編輯：何麗）