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

萬曉鳳，胡偉，方武義，鄭博嘉

南昌大學信息工程學院，南昌 330031

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

萬曉鳳，胡偉，方武義，鄭博嘉

南昌大學信息工程學院，南昌 330031

移動機器人是一個集環(huán)境監(jiān)測感知、動態(tài)決策與規(guī)劃、行為控制與執(zhí)行等多功能于一體的復雜控制系統(tǒng)[1]。路徑規(guī)劃是機器人研究領域的一個關鍵環(huán)節(jié)，路徑規(guī)劃是指在有障礙物的環(huán)境中依據(jù)某些優(yōu)化準則（如路徑最短，最安全等），尋找一條從起始點到目標點之間安全無碰撞的最優(yōu)或次最優(yōu)路徑[2-3]。國內外針對路徑規(guī)劃問題提出了很多算法，主要有可視圖法、拓撲法、人工勢場法等。隨著智能算法的發(fā)展，神經(jīng)網(wǎng)絡算法、遺傳算法、蟻群算法以及微粒群算法等也被廣泛地應用于機器人路徑規(guī)劃當中[4]。

蟻群算法最早是作為一種解決組合優(yōu)化問題的元啟發(fā)式算法被提出，并成功地應用于旅行商問題。它采用分布式并行計算機制，有易與其他方法結合、魯棒性較強等優(yōu)點[5-6]。本文主要研究改進后的蟻群算法在機器人路徑規(guī)劃中的應用。

1 環(huán)境建模

本文所研究的機器人工作環(huán)境為二維靜態(tài)空間，在描述障礙時采用把障礙物外擴一個機器人的最大直徑，把機器人視作質點，在保障安全性的前提下簡化問題的復雜度。由于柵格法地圖表達規(guī)范，容易實現(xiàn)，并且其模型結構與旅行商問題類似，因此采用柵格法進行建模。

柵格法模型如圖1所示，圖中從左至右，從上至下對柵格進行編碼。坐標以左下方位原點，從左到右為x軸正方向，從下到上為y軸正方向，每個柵格長度記為單位長度（假設為1 cm）。圖中白色柵格為自由柵格，黑色柵格為障礙柵格，障礙不滿一個柵格則填充滿此柵格[7-8]。設柵格序號為c，n為每行每列的柵格數(shù)。圖中序號編碼與坐標對應關系如式（1）所示。

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

2 蟻群算法

2.1 基本蟻群算法

蟻群算法來源于自然界螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，為模擬自然界螞蟻的行為，假設地圖模型中出發(fā)點為蟻穴，目標點為食物源。整個路徑規(guī)劃過程可以看成是蟻群在地圖中尋找食物的過程，螞蟻間通過相互溝通、協(xié)調，最終避開障礙物找到一條最優(yōu)路徑。

現(xiàn)假設螞蟻數(shù)量為M，柵格圖規(guī)模為N×N，算法主要操作步驟如下：

（1）概率選擇。螞蟻根據(jù)公式（2），通過輪盤賭方法來選擇將要前進的節(jié)點，Pm(i，j)是第m只螞蟻從節(jié)點i到節(jié)點j的概率。τ(i，j)表示節(jié)點i至節(jié)點j邊上的信息激素量，各條邊的初始值為同一常數(shù)C。機器人只能向四周八個節(jié)點前進，Ji為節(jié)點i四周八節(jié)點中除去障礙節(jié)點及禁忌節(jié)點的集合，禁忌表TABUm存入螞蟻已行節(jié)點。若螞蟻陷入U型障礙，使得螞蟻無后續(xù)節(jié)點選擇，則默認該螞蟻已經(jīng)死亡，算法刪除該螞蟻及其所尋路徑。η(i，j)表示ij兩節(jié)點間的期望值，與兩節(jié)點間距離成反比。α、β分別為信息激素和期望的啟發(fā)因子[9]。

（2）信息激素量更新。每次所有螞蟻尋跡完成后對信息激素進行全局更新，過去的信息激素量逐漸消逝，并加入新的信息激素量。更新規(guī)則如式（3）所示。參數(shù)ρ為揮發(fā)系數(shù)，一般取0～1之間常數(shù)。Tk(i，j)為k時刻節(jié)點ij間信息激素量，τk+1(i，j)為k+1時刻節(jié)點ij間信息激素量，Δτ(i，j)為本次循環(huán)節(jié)點ij間信息激素增量，由式（4）決定。式中Mij為經(jīng)過路線ij的螞蟻集合，Δτm(i，j)為第m只螞蟻留給節(jié)點ij間的信息激素增量，由式（5）決定。Lm為第m只螞蟻所尋路徑的長度，Q為一適當正常數(shù)[10]。

（3）迭代循環(huán)。每輪信息激素量更新完成后把所有螞蟻再次放回起始點重新尋跡，經(jīng)過K次迭代完成后，計算出最短路徑。

2.2 改進蟻群算法

基本蟻群算法雖然能夠規(guī)劃出從起始點到目標點的路徑，并有較強的魯棒性，但依然存在很多不足，主要有容易過早停滯、搜索時間過長、效率較低等[11-12]。本文對基本算法做出幾點改進，使得算法在更短時間內得出更短更平滑的路徑。

（1）概率公式修改，修改期望值。由于基本蟻群算法期望值采用的是當前節(jié)點到下一個節(jié)點的距離反比函數(shù)，而這種情況下η(i，j)只有兩個值，不利于螞蟻選擇下一個更優(yōu)節(jié)點。而采用節(jié)點j到目標節(jié)點的距離來設定期望值，螞蟻的所有下一個可行節(jié)點的期望值都是不同的，其中距離目標點最近的節(jié)點的期望值最大，這就使得螞蟻更加傾向于選擇離目標節(jié)點更近的節(jié)點，所尋路徑長度也就更優(yōu)。如式（6）所示，η(j，E)為節(jié)點j到目標節(jié)點的期望值，其值為1/LjE。

（2）信息激素更新規(guī)則修改，為使所尋路徑更加平滑，節(jié)省機器人行走時間，加入拐點參數(shù)作為路徑評價之一。機器人所尋路徑中只有三種角，分別為銳角、直角、鈍角，它們的值分別記為3、2、1，把所有角度值相加即得拐點參數(shù)值。由式（5）可知，在基本蟻群算法中，第m只螞蟻經(jīng)過ij段需增加的信息激素量為第m只螞蟻所尋路徑長度的反比函數(shù)，路徑越長，增量越少[13]。而加入路徑拐點參數(shù)按比例與路徑長度相加，則可以利用這兩個參數(shù)一起評價路徑的優(yōu)劣，由此決定需增加的信息激素量，使所尋路徑長度優(yōu)且更加平滑。如式（7）所示，GDm為第m只螞蟻所尋路徑的拐點參數(shù)，λ為加權系數(shù)。

（3）揮發(fā)系數(shù)采用自適應方式，由于螞蟻未走過的路徑因信息激素的衰減而降低被選擇的概率，影響算法的全局搜索能力，若ρ過小，會降低算法的收斂速度，而ρ過大則會影響算法隨機性和搜索能力[14-15]。當經(jīng)過若干次迭代后最優(yōu)路徑無改進時，采用式（8）更新?lián)]發(fā)系數(shù)，本文γ=0.85。

2.3 改進蟻群算法流程

應用改進蟻群算法進行路徑規(guī)劃的具體步驟如下：

（1）構建環(huán)境模型，初始化各參數(shù)，設置最大迭代次數(shù)K，k=1，m=1。

（2）把螞蟻m(m=1，2，…，M)放到初始位置，并把初始點加入禁忌表TABUm中。

（3）根據(jù)概率公式（6）使當前螞蟻m轉移至下一節(jié)點，并修改禁忌表，如此循環(huán)，直到螞蟻到達目標節(jié)點。若中途螞蟻落入U型陷阱，無下一節(jié)點可走，則判斷此螞蟻死亡。

（4）存儲當前螞蟻m的所尋路徑及路徑長度，刪除死亡螞蟻，默認其路徑長度為無窮大。m=m+1，若m＜M，回到（2）。

（5）按信息激素更新公式（3）、（4）及（7）進行全局信息激素更新。迭代次數(shù)k=k+1，若k＜K，則m=1繼續(xù)（2）循環(huán)。

（6）算法結束，輸出最優(yōu)路徑。

3 仿真分析

為驗證改進后算法的有效性，現(xiàn)使用軟件MATLAB7.0對基本蟻群算法和改進蟻群算法進行仿真，并比較它們的仿真結果。

機器人的環(huán)境模型如圖1所示，各參數(shù)設置分別為：α=1，β=2，M=100，N=20，K=200，ρ=0.2，Q=2 000，λ=2，γ=0.85?；鞠伻核惴ê透倪M蟻群算法尋優(yōu)結果分別如圖2和如圖3所示。多次運行兩種算法，比較它們的最優(yōu)路徑及迭代情況，結果如表1所示。

通過圖2和圖3兩種算法尋優(yōu)結果可以直觀地看出基本算法所尋路徑長，拐點參數(shù)大。而改進后算法所尋路徑長度大大減小，且平滑度好。

圖2 基本蟻群算法仿真結果

圖3 改進蟻群算法仿真結果

表1 基本算法與改進算法多次運行結果比較

對比表1數(shù)據(jù)，首先，基本蟻群算法中，最優(yōu)路徑長度遠大于改進蟻群算法最優(yōu)路徑長度，拐點參數(shù)也遠大于改進蟻群算法。十次運行結果中，基本蟻群算法只有兩次最優(yōu)路徑達到35 cm以下，最小拐點參數(shù)為26；而改進后算法只有一次最優(yōu)路徑在30 cm以上，最大拐點參數(shù)也只有16，并且找到了本文地圖環(huán)境下實際最優(yōu)路徑，其長度為28.038 cm，拐點參數(shù)為7。說明改進后算法所尋路徑大大優(yōu)于基本算法。

其次，從迭代次數(shù)看，雖然終值迭代次數(shù)改進算法和基本算法看起來優(yōu)勢不大，但是基本算法很難在50次迭代內尋到長度35 cm以下的路徑。說明基本算法搜索速度慢，算法過早停滯，易陷入局部最優(yōu)。而改進后算法很快就能搜索到長度35 cm以下路徑，在5次迭代之內基本就能完成，并且還能繼續(xù)快速搜索到最優(yōu)路徑。這說明改進后算法收斂速度快，搜索能力強。

分析結果得出，基本蟻群算法搜索能力弱，尋優(yōu)效果差，效率較低。而改進后的蟻群算法搜索能力增強，收斂速度快，效率高，尋優(yōu)效果好，機器人可以快速地避開障礙物安全到達目標點。

4 結論

本文針對基本蟻群算法在機器人路徑規(guī)劃中的不足，對算法做出改進。加入目標點吸引機制，讓機器人更加趨近于目標點移動。揮發(fā)系數(shù)自適應，改善蟻群算法的性能。拐點參數(shù)評價有效地改善了路徑的平滑度。通過對仿真結果的分析，得出改進后的蟻群算法能夠有效地彌補基本蟻群算法的不足，算法搜索速度加快，所尋路徑更短且更平滑，大大提高了機器人的效率。

本文主要研究了機器人在二維靜態(tài)空間內的路徑規(guī)劃，環(huán)境信息完全已知，雖取得了較好的結果，但算法設計上仍有不足之處有待改進。在接下來的研究中，應當更加深入地研究此算法，并且考慮機器人在動態(tài)環(huán)境下障礙探測以及擴展到三維空間內的路徑規(guī)劃問題。

[1]Soulignac M.Feasible and optimal path planning in strong current fields[J].IEEE Transactions on Robotics，2011，27（1）：89-98.

[2]劉華軍，楊靜宇.移動機器人運動規(guī)劃研究綜述[J].中國工程科學，2006，8（1）：85-94.

[3]王娟，吳憲祥.基于改進粒子群優(yōu)化算法的移動機器人路徑規(guī)劃[J].計算機工程與應用，2012，48（15）：240-244.

[4]李學洋，李悅，張亞偉.基于遺傳變異蟻群算法的機器人路徑規(guī)劃的改進[J].電子設計工程，2012，20（15）：38-40.

[5]段海濱，王道波.蟻群算法理論及應用研究的進展[J].控制與決策，2004，19（12）：1321-1326.

[6]Dorigo M，Caro G D.Ant colony optimization：a new meta-heuristic[C]//Proceedings of the 1999 Congress on Evolutionary Computation，1999：1470-1477.

[7]朱磊，樊繼壯.基于柵格法的礦難搜索機器人全局路徑規(guī)劃與局部避障[J].中南大學學報：自然科學版，2011，42（11）：3421-3428.

[8]羅榮貴，屠大維.柵格法視覺傳感集成及機器人實時避障[J].計算機工程與應用，2011，47（24）：233-235.

[9]蔡榮英，王李進，吳超.一種求解旅行商問題的迭代改進蟻群優(yōu)化算法[J].山東大學學報：工學版，2012，42（1）：6-11.

[10]吳華鋒，陳信強，毛奇凰.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學報，2013，34（4）：165-170.

[11]Xiong W，Wei P.A kind of ant colony algorithm for function optimization[C]//Proceeding of the 1st International Conference on Machine Learning and Cybernetics，Beijing，2002：552-555.

[12]周明秀，程科，汪正霞.動態(tài)路徑規(guī)劃中的改進蟻群算法[J].計算機科學，2013，40（1）：314-316.

[13]王越，葉秋冬.蟻群算法在求解最短路徑問題上的改進策略[J].計算機工程與應用，2012，48（13）：35-38.

[14]徐瑾.基于改進蟻群算法的移動機器人路徑規(guī)劃研究[D].河北保定：華北電力大學，2011.

[15]陳一昭，姜麟.蟻群算法參數(shù)分析[J].科學技術與工程，2011，11（36）：9080-9084.

WAN Xiaofeng,HU Wei,FANG Wuyi,ZHENG Bojia

College of Information Engineering,Nanchang University,Nanchang 330031,China

The basic ant colony algorithm applied to robot path planning in the two-dimensional static environment has problems of long search time,inefficiency and easy to fall into local optimization and so on.It makes improvements on the algorithm for these problems.It uses different expectation mechanism,updates the pheromone by taking evaporation coefficient adaptive approach,and joins the inflection point parameter as one evaluation criteria of the path.Simulation of the two algorithms shows the improved ant colony algorithm is stronger of searching ability and more efficient than the basic ant colony algorithm and gets a shorter path.The results show that the improved algorithm improves the efficiency of the algorithm and inhibits algorithm into local optimum and achieves search of robot’s optimal path.Robot can avoid obstacles to reach the target point safely and quickly.

ant colony algorithm;path planning;evaporation coefficient adaptive;inflection point parameter;optimal path

在二維靜態(tài)環(huán)境下的機器人路徑規(guī)劃中，采用基本蟻群算法尋優(yōu)存在搜索時間較長、效率較低、容易陷入局部最優(yōu)等問題。針對這些問題對基本蟻群算法進行改進，改進的蟻群算法使用不同的期望值機制，采用揮發(fā)系數(shù)自適應方式更新信息激素，并加入拐點參數(shù)作為路徑的評價標準之一。對這兩種算法進行仿真分析，可得改進后的蟻群算法比基本蟻群算法搜索能力更強，算法效率更高，所尋路徑更短。結果表明，該改進算法提高了算法效率，抑制了算法陷入局部最優(yōu)并實現(xiàn)了機器人最優(yōu)路徑搜索，使機器人可以快速地避開障礙物安全到達目標點。

蟻群算法；路徑規(guī)劃；揮發(fā)系數(shù)自適應；拐點參數(shù)；最優(yōu)路徑

A

TP18；TP24

10.3778/j.issn.1002-8331.1311-0106

WAN Xiaofeng,HU Wei,FANG Wuyi,et al.Research on path planning of robot based on improved ant colony algorithm.Computer Engineering and Applications,2014,50（18）：63-66.

江西省科技支撐項目（No.20133BBE50029）；江西省科技廳工業(yè)支撐計劃（No.20132BBE50049）。

萬曉鳳（1964—），女，教授，從事計算機控制與嵌入式智能儀表研究。E-mail：xfwan_jxw@163.com

2013-11-11

2013-12-30

1002-8331（2014）18-0063-04

CNKI網(wǎng)絡優(yōu)先出版：2014-04-01,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0106.html