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

南昌大學(xué)信息工程學(xué)院，南昌 330031

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

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

南昌大學(xué)信息工程學(xué)院，南昌 330031

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

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

1 環(huán)境建模

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

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

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

2 蟻群算法

2.1 基本蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真分析

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

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

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

圖2 基本蟻群算法仿真結(jié)果

圖3 改進(jìn)蟻群算法仿真結(jié)果

表1 基本算法與改進(jìn)算法多次運(yùn)行結(jié)果比較

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

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

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

4 結(jié)論

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

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

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

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

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

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

[5]段海濱，王道波.蟻群算法理論及應(yīng)用研究的進(jìn)展[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]朱磊，樊繼壯.基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，42（11）：3421-3428.

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

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

[10]吳華鋒，陳信強(qiáng)，毛奇凰.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學(xué)報(bào)，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ìn)蟻群算法[J].計(jì)算機(jī)科學(xué)，2013，40（1）：314-316.

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

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

[15]陳一昭，姜麟.蟻群算法參數(shù)分析[J].科學(xué)技術(shù)與工程，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)境下的機(jī)器人路徑規(guī)劃中，采用基本蟻群算法尋優(yōu)存在搜索時(shí)間較長、效率較低、容易陷入局部最優(yōu)等問題。針對這些問題對基本蟻群算法進(jìn)行改進(jìn)，改進(jìn)的蟻群算法使用不同的期望值機(jī)制，采用揮發(fā)系數(shù)自適應(yīng)方式更新信息激素，并加入拐點(diǎn)參數(shù)作為路徑的評價(jià)標(biāo)準(zhǔn)之一。對這兩種算法進(jìn)行仿真分析，可得改進(jìn)后的蟻群算法比基本蟻群算法搜索能力更強(qiáng)，算法效率更高，所尋路徑更短。結(jié)果表明，該改進(jìn)算法提高了算法效率，抑制了算法陷入局部最優(yōu)并實(shí)現(xiàn)了機(jī)器人最優(yōu)路徑搜索，使機(jī)器人可以快速地避開障礙物安全到達(dá)目標(biāo)點(diǎn)。

蟻群算法；路徑規(guī)劃；揮發(fā)系數(shù)自適應(yīng)；拐點(diǎn)參數(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.

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

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

2013-11-11

2013-12-30

1002-8331（2014）18-0063-04

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