付 寧，張東霞，國(guó)海濤

(1.濰坊工程職業(yè)學(xué)院，山東青州 262500;2.魯東大學(xué)，山東煙臺(tái) 264025)

蟻群算法在機(jī)器人路徑規(guī)劃中研究及發(fā)展趨勢(shì)

付 寧1，張東霞1，國(guó)海濤2

(1.濰坊工程職業(yè)學(xué)院，山東青州 262500;2.魯東大學(xué)，山東煙臺(tái) 264025)

移動(dòng)機(jī)器人研究中的一個(gè)重要領(lǐng)域是機(jī)器人路徑規(guī)劃方法。本文對(duì)蟻群算法在機(jī)器人路徑規(guī)劃方法的研究現(xiàn)狀進(jìn)行了概括與總結(jié)，指出了各種改進(jìn)方法的優(yōu)點(diǎn)及不足，最后對(duì)其發(fā)展方向進(jìn)行了展望。

移動(dòng)機(jī)器人;蟻群算法;動(dòng)態(tài)路徑規(guī)劃

1 蟻群算法基本原理

20世紀(jì)90年代，意大利學(xué)者 M·Dorigo、V· Maniezzao、A·Colorni等人從生物進(jìn)化的機(jī)理中受到啟發(fā)，通過(guò)模擬自然界螞蟻尋食的行為，提出了一種全新的模擬進(jìn)化算法：蟻群優(yōu)化算法［1］(Ant Colony Optimization Algorithm簡(jiǎn)稱(chēng)ACOA)。其算法基本原理是：經(jīng)過(guò)大量的研究發(fā)現(xiàn)，螞蟻個(gè)體之間是通過(guò)一種稱(chēng)之為外激素的物質(zhì)進(jìn)行信息傳遞，從而能相互協(xié)作，完成復(fù)雜的任務(wù)。同時(shí)，螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一種物質(zhì)，而且能夠感知這種物質(zhì)的存在及其強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)。這種物質(zhì)在蟻群算法中稱(chēng)為信息素。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。螞蟻個(gè)體之間就是通過(guò)這種信息的交流選擇出最佳路線，達(dá)到搜索食物的目的。

2 蟻群算法在機(jī)器人路徑規(guī)劃中的應(yīng)用現(xiàn)狀

移動(dòng)機(jī)器人路徑規(guī)劃［2］是指在有障礙物的工作環(huán)境中，尋找一條從給定起始點(diǎn)到終止點(diǎn)的較優(yōu)的運(yùn)動(dòng)路徑，使機(jī)器人在運(yùn)動(dòng)過(guò)程中能安全、無(wú)碰撞地繞過(guò)所有障礙物，且所走路徑較短。移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人學(xué)中非常重要的研究分支，是研究機(jī)器人控制系統(tǒng)的重要基礎(chǔ)問(wèn)題，因而受到了廣大研究者的關(guān)注并成為經(jīng)久不衰的研究熱點(diǎn)，在這一領(lǐng)域取得了很多重要成果，諸如傳統(tǒng)的人工勢(shì)場(chǎng)法［3］、A*算法［4］等。但傳統(tǒng)的優(yōu)化方法在機(jī)器人路徑規(guī)劃這類(lèi)復(fù)雜非線性?xún)?yōu)化問(wèn)題中缺乏自適應(yīng)性，計(jì)算太復(fù)雜，優(yōu)化過(guò)程缺乏魯棒性［5］，近年來(lái)，隨著智能方法的廣泛應(yīng)用，機(jī)器人路徑規(guī)劃方法也有了長(zhǎng)足的進(jìn)展，許多研究者把目光放在了基于智能方法的路徑規(guī)劃研究上。其中蟻群算法成為研究熱點(diǎn)。

樊小平［6］等人首先將基本蟻群算法引入到機(jī)器人路徑規(guī)劃研究領(lǐng)域，并嘗試在蟻群算法中通過(guò)調(diào)整避障系數(shù)，得到不同的優(yōu)化軌跡。但由于傳統(tǒng)的蟻群算法存在一定的不足，如算法收斂速度慢，不能解決復(fù)雜環(huán)境下尤其是具有凹型障礙環(huán)境的路徑規(guī)劃問(wèn)題，所以隨后很多學(xué)者對(duì)其進(jìn)行了改進(jìn)。文獻(xiàn)［7］首次將蟻群算法與柵格法環(huán)境建模相結(jié)合用于機(jī)器人路徑規(guī)劃中，并提出了雙螞蟻思想，但該算法沒(méi)有考慮機(jī)器人路徑規(guī)劃中的死鎖問(wèn)題。文獻(xiàn)［8］中的算法提出了螞蟻死亡的概念，即當(dāng)螞蟻無(wú)路可選時(shí)，螞蟻死亡，重新初始化一只螞蟻，這樣避免了死鎖。此文中也是采用雙向螞蟻相向搜索，但是兩組螞蟻采用的搜索策略不同。澳大利亞學(xué)者Russell設(shè)計(jì)了一種用于移動(dòng)機(jī)器人的氣味傳感器導(dǎo)航機(jī)制［9］，并深入分析了蟻群算法在該領(lǐng)域應(yīng)用的魯棒性。瑞士學(xué)者M(jìn)ichael等將蟻群算法的程序編入微型機(jī)器人中，使眾多微型機(jī)器人象螞蟻一樣協(xié)同工作，完成復(fù)雜任務(wù)。這項(xiàng)研究成果已被國(guó)際著名刊物《Nature》報(bào)道［10］。

文獻(xiàn)［11］提出使用偽隨機(jī)比例狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個(gè)節(jié)點(diǎn)，僅讓每一代中最好的個(gè)體所走過(guò)的路徑上的信息素進(jìn)行更新，以加快收斂速度。由于強(qiáng)化了最優(yōu)信息的反饋，會(huì)導(dǎo)致早熟、停滯現(xiàn)象。文獻(xiàn)［12］提出最大 -最小螞蟻系統(tǒng)(Max-Min Ant System，MMAS)，對(duì)路徑上的信息素進(jìn)行限制，雖然在一定程度上避免了早熟、停滯現(xiàn)象，但在解的分布較分散時(shí)收斂速度較慢。

傳統(tǒng)的蟻群算法一方面存在算法初期信息素匱乏導(dǎo)致搜索時(shí)間過(guò)長(zhǎng)，難以滿(mǎn)足實(shí)時(shí)規(guī)劃或?qū)Ш降囊蟮热毕?另一方面不能擴(kuò)大解的搜索范圍導(dǎo)致解空間的探索不夠、搜索容易陷入局部最優(yōu)導(dǎo)致搜索易于停滯，難以保證每次都能找到全局最優(yōu)或者較優(yōu)路徑。雖然有的改進(jìn)方法較好地避免了搜索的局部停滯，但是由于只更新最優(yōu)路徑上的信息素，因此也會(huì)導(dǎo)致路徑的搜索陷入停滯。

3 蟻群算法在機(jī)器人路徑規(guī)劃中的研究趨勢(shì)

目前蟻群算法用于機(jī)器人路徑規(guī)劃時(shí)所建立的模型與方案不是很成熟，仍具有很大的研究空間。雖然學(xué)者們提出了各種各樣的改進(jìn)蟻群算法，但所有的改進(jìn)都是基于原始模型的，仍然有不少關(guān)鍵理論和技術(shù)問(wèn)題急需解決。就目前改進(jìn)的蟻群算法而言仍有共同問(wèn)題存在：由于其信息素加強(qiáng)正反饋的同時(shí)造成了早收斂，無(wú)法對(duì)解空間進(jìn)一步搜索，而不能發(fā)現(xiàn)全局最優(yōu)路徑。信息素的更新不是很合理使最優(yōu)路徑、次優(yōu)路徑、不可行路徑之間的信息素差距不是很大，限制了搜索的多樣性，容易陷入局部循環(huán)當(dāng)中，以至于早熟，而不能發(fā)現(xiàn)全局最優(yōu)。因此如何解決容易早熟、停滯和收斂速度之間的矛盾，如何在加大搜索空間的同時(shí)又能跳離局部最優(yōu)解，是該領(lǐng)域當(dāng)前急需解決的問(wèn)題。

［1］Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of coopera——ting agents［J］.IEEE Transactions on SMC，1996，26(1)：29-41.

［2］蔣新松.機(jī)器人學(xué)導(dǎo)論［M］.沈陽(yáng)：遼寧科學(xué)技術(shù)出版社，1994.

［3］Min Gyu Park，Min Cheol Lee.Artificial Potential Field Based Path Planning for Mobile Robots Using a Virtual Obstacle Concept.IEEE/ASME International Conference on Advanced Intelligent Mechatronics，Kobe，Japan，2003：735-740.

［4］A.Yahja，S.Singb，A.Stenz.An Efficient On-line Path Planner for Outdoor Mobile Robots［J］.Robotics and Autonomous Systems，2000，32(2-3)：129-143.

［5］謝宏斌.動(dòng)態(tài)環(huán)境中移動(dòng)機(jī)器人路徑規(guī)劃的研究［D］.無(wú)錫：江南大學(xué)碩士學(xué)位論文，2003.

［6］Xiaoping Fan，Xiong Luo，Sheng Yi，Shengyue Yang，Heng Zhang.Optimal Path Planning for Mobile Robots Based on Intensified Ant Colony Optimization Algorithm［C］.Proceedings of the 2003 IEEE Intemational Conferenceon Robotics，Intelligent Systemsand Signal Processing，2003，(1)：131-136.

［7］朱慶保，張玉蘭.基于柵格法的機(jī)器人路徑規(guī)劃蟻群算法機(jī)器人［J］.機(jī)器人，2005，27(2)：132-136.

［8］Mohd M.Mohamad，Matthew W.Dunnigan，Nicholas K.Taylor.Ant Colony Robot Motion Planning［C］.EUROCON 2005 IEEE：213-216.

［9］Russell R A.Ant t rails-An example for robots to follow［C］∥Proc of the 1999 IEEE Int Conf on Robotics and Automation.Detroit，1999，2698-2703.

［10］Michael J B K，Jean-Bernard B，Laurent K.Ant-like task and recruitment in coop- -erative robots［J］.Nature，2000，406 (31)：992-995.

［11］Mohd M.Mohamad，Matthew W.Dunnigan，Nicholas K.Taylor.Ant Colony Robot Motion Planning［C］.EUROCON 2005 IEEE：213-216.

［12］Stutzle T，Hoos H H.Max-min ant system［J］.Future Generation Computer System，2000，16(8)：889-914.

2011-08-24

付寧(1981-)，男，山東青州人，濰坊工程職業(yè)學(xué)院講師。

TP242 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1009-2080(2011)05-0081-02

(責(zé)任編輯：潘 敏)