林海濤　徐高晶　徐韜　俞學(xué)宏

摘要：該文將蟻群算法運(yùn)用到機(jī)器人全局路徑規(guī)劃上，主要針對(duì)螞蟻算法在搜索路徑過(guò)程中落入障礙物陷阱而造成算法停滯的現(xiàn)象，提出了改進(jìn)策略，同時(shí)基于對(duì)機(jī)器人所處環(huán)境的表示方法及算法中對(duì)應(yīng)問(wèn)題的描述和定義的研究，對(duì)相關(guān)參數(shù)進(jìn)行了改進(jìn)探討。通過(guò)對(duì)算法的改進(jìn)，增強(qiáng)了機(jī)器人的蟻群算法在復(fù)雜環(huán)境路徑規(guī)劃下的適應(yīng)能力。

關(guān)鍵詞：機(jī)器人；路徑規(guī)劃；蟻群算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）01-0130-03

1 環(huán)境描述

機(jī)器人在路徑規(guī)劃前必須建立其所處的環(huán)境模型，假設(shè)機(jī)器人所處環(huán)境中存在有限數(shù)量的靜止障礙，并且障礙物大小位置已知，并且當(dāng)機(jī)器人處于動(dòng)態(tài)情況下，障礙的方位和形狀都是恒定的。利用機(jī)器人的傳感器獲取環(huán)境的相關(guān)信息后，提取相關(guān)環(huán)境信息數(shù)據(jù)，完成環(huán)境數(shù)據(jù)搜集后，將搜集到的圖像按照柵格來(lái)劃分，并且柵格內(nèi)部有障礙物與無(wú)障礙物柵格分別用陰影實(shí)體與空白表示，處理之后可以得到障礙物分布在各個(gè)柵格內(nèi)，對(duì)未布滿整個(gè)柵格的按照一個(gè)柵格來(lái)計(jì)算。

2 蟻群算法及相關(guān)問(wèn)題描述

2.1 算法原理

研究發(fā)現(xiàn)：在尋找食物的過(guò)程中，螞蟻?zhàn)陨頃?huì)釋放一種信息素，該元素可以被其他個(gè)體所感知，并且會(huì)傾向于朝著信息素濃度高的方向移動(dòng)，所以，在螞蟻尋找食物的過(guò)程中，群體的行為會(huì)呈現(xiàn)出一種趨勢(shì)：如果某一個(gè)目標(biāo)路徑的距離越短，則該路徑上螞蟻的通過(guò)率越高，在該路徑上信息素的釋放量也是越多，而后來(lái)的蟻群都會(huì)感知信息素濃度大小，并會(huì)傾向于選擇距離最短的那條路徑，螞蟻個(gè)體之間這種搜尋食物的過(guò)程也是蟻群算法的最初基礎(chǔ)，蟻群算法實(shí)際就是模擬螞蟻群體尋找食物過(guò)程的優(yōu)化算法。

通過(guò)對(duì)N個(gè)城市的TSP問(wèn)題求解可得到蟻群算法的基本模型。城市的TSP問(wèn)題就是要尋找求解出從出發(fā)城市到終點(diǎn)城市距離最近的路徑，其中的條件就是該過(guò)程需要通過(guò)每一個(gè)城市，且只能通過(guò)一次。設(shè)m表示螞蟻數(shù)量，[dij（i，j=1，2，???，m）]表示城市i和城市j之間的距離，[τij（t）]表示t時(shí)刻i，j連線上的信息量，設(shè)[τij（0）=C]為常數(shù)。任一螞蟻k（k=1，2，...，m），它的移動(dòng)方向是由路徑上信息量的含量決定的，在t時(shí)刻螞蟻由i向j移動(dòng)的概率[pkij（t）]可由下式表示：

[pkij（t）=[τij（t）]α?[ηij（t）]βs∈allowedk[τij（t）]??[τij（t）]β，j∈allowedk0， 否則]

上式中，[τij]表示t時(shí)刻i、j連線上的信息素量；[ηij]表示t時(shí)刻螞蟻從i移動(dòng)到j(luò)的期望程度；[allowedk]表示螞蟻下一次移動(dòng)可以選擇的城市，[allowedk]={1，2，...，n}-[tabuk]；α，β分別代表某一路段上的[τij]和[ηij]的重要程度；[tabuk]表示螞蟻已走過(guò)城市的集合，當(dāng)[tabuk]將所有城市包含時(shí)，表示螞蟻已完成了一次路徑選擇，并且該選擇路徑成為最優(yōu)路徑問(wèn)題的備選解。

2.2 相關(guān)問(wèn)題的描述與定義

對(duì)于機(jī)器人路徑規(guī)劃問(wèn)題，可以設(shè)起始點(diǎn)為[gbegin]，終結(jié)點(diǎn)為[gaim]，具體描述如下：

1） City={1，2，...，n}表示劃分區(qū)域的集合；Ant={1，2，...，m}表示螞蟻的集合；G={[g1，g2，???，gN?N]}，G為所有柵格節(jié)點(diǎn)[gi]的集合。

2） 螞蟻經(jīng)過(guò)路段上留下的信息素會(huì)隨著時(shí)間的積累逐漸揮發(fā)消散，有下式：

[τij（t+h）=（1-ρ）τij（t）+Δτij（t）]

上式表示螞蟻t時(shí)刻在分割區(qū)[pi，pj]連線上所剩的信息素，[τij（t）∈[τmin，τmax]]，其中[ρ]為信息素?fù)]發(fā)系數(shù)，[Δτij（t）=k=1m]為該次運(yùn)動(dòng)過(guò)程中路徑i，j上的信息增量：

[Δτij（t）=k=1mΔτkij]

且：

[Δτkij=QLk，第k只螞蟻在h時(shí)間內(nèi)走過(guò)路徑p（i，j）0， 否則]

其中，Q為常數(shù)，[Lk]為第k只螞蟻選擇路徑的總長(zhǎng)度。

3） 任意分割區(qū)間的距離是指兩分割區(qū)間中心點(diǎn)的連線長(zhǎng)度，即[d（pl，pm），l，m∈G]，則可以計(jì)算：

[d（pl，pm）=（xl-xm）2+（yl-ym）2]

2.3 算法改進(jìn)策略

機(jī)器人處在實(shí)際環(huán)境中搜索路徑時(shí)可能會(huì)遇到可陷入的障礙，這樣會(huì)造成螞蟻無(wú)法選擇下一分割區(qū)，如表1所示，螞蟻k在眾多可選擇爬行路徑中，假設(shè)選取的是從[g7]處到[g12]，再到[g17]，此時(shí)螞蟻將無(wú)后續(xù)結(jié)點(diǎn)可以選擇，即落入陷阱，此時(shí)，該螞蟻就會(huì)停滯不前，最終導(dǎo)致算法提前停滯，對(duì)于這種問(wèn)題，通常采取的方法是，在初始化環(huán)境過(guò)程中，假定環(huán)境中存在的這類障礙都為凸?fàn)疃皇前紶睿耘懦砂紶钫系K引起的算法停滯問(wèn)題。表1的柵格環(huán)境進(jìn)行凸處理后得到的結(jié)果示意如表2所示。

在螞蟻前進(jìn)過(guò)程中，如果出現(xiàn)沒(méi)有后續(xù)分割區(qū)供選擇的情況時(shí)，我們就判定此時(shí)的螞蟻已經(jīng)陷入障礙，需要退回到上一個(gè)分割區(qū)，然后開始再一次的判定，判定依據(jù)和執(zhí)行過(guò)程都相同，直到螞蟻不再陷入障礙為止。螞蟻在退回時(shí)，需要將未退回時(shí)的當(dāng)前柵格加入螞蟻的禁忌表，以保證該螞蟻不會(huì)落入一個(gè)障礙兩次，最終螞蟻完成整個(gè)路徑的搜索。

2.3.1 螞蟻算法參數(shù)的改進(jìn)

1） 信息量[τij（t）]和期望度[ηij（t）]分析。[τij（t）]是表示過(guò)去的信息素，而[ηij（t）]則是表示未來(lái)信息的載體，他們會(huì)對(duì)蟻群算法的求解范圍和效率產(chǎn)生很大的影響。該文中的各個(gè)路徑段上的[τij（t）]的更新要從全局和局部展開，[ηij（t）]為相關(guān)路段長(zhǎng)度的倒數(shù)。

2） [τij]啟發(fā)式因子α和[ηij]啟發(fā)式因子β的選取。其中α的值越大，螞蟻選擇過(guò)去路徑的可能性越大，選擇的隨機(jī)性也隨之減少；如果其值過(guò)小，則會(huì)增加路徑選擇的隨機(jī)性，只能局部性選擇，而不能實(shí)現(xiàn)全局規(guī)劃。β的值越大，則螞蟻選擇路徑時(shí)選擇局部最短路徑的可能性較大，這樣就會(huì)容易陷入局部最優(yōu)。該文兩個(gè)參數(shù)取值在0-5之間。

3） 揮發(fā)系數(shù)[ρ]分析。[ρ]的取值過(guò)大時(shí)，之前被搜尋的路徑很有可能被再次選中，這樣就會(huì)降低算法的全局規(guī)劃能力和隨機(jī)性，如果取值過(guò)小，會(huì)降低算法的收斂速度，影響搜索效率。所以，信息素?fù)]發(fā)系數(shù)的選擇，必須要同時(shí)考慮到算法的全局規(guī)劃能力和搜尋速度，[ρ]可以取0.9。

2.3 改進(jìn)蟻群算法的實(shí)現(xiàn)

改進(jìn)的算法流程圖如圖3所示。

3 結(jié)論

本文首先利用柵格法對(duì)機(jī)器人的移動(dòng)環(huán)境進(jìn)行建模，在此基礎(chǔ)上，主要針對(duì)在復(fù)雜地形環(huán)境中，蟻群算法容易導(dǎo)致螞蟻陷入“陷阱”而造成的算法停滯的現(xiàn)象，對(duì)蟻群算法進(jìn)行了改進(jìn)，最后得到改進(jìn)蟻群算法的相關(guān)流程與步驟，使得蟻群算法的魯棒性和適應(yīng)性得到提高，增強(qiáng)了蟻群算法在復(fù)雜環(huán)境下的適應(yīng)能力，使其能夠有效解決復(fù)雜環(huán)境中的機(jī)器人路徑規(guī)劃問(wèn)題。

參考文獻(xiàn)：

[1] 蔡自興.機(jī)器人學(xué)[M].北京：清華大學(xué)出版社，2009：256-261.

[2] 喬茹.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃[J].安徽工業(yè)大學(xué)學(xué)報(bào)，2009，26（1）：77-80.

[3] 朱慶保.復(fù)雜環(huán)境下的機(jī)器人路徑規(guī)劃螞蟻算法[J].自動(dòng)化學(xué)報(bào)，2006，32（4）：287-293

[4] 任春明，張建勛.基于優(yōu)化蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程，2008，34（15）：1-3，35.

[5] LIU Shi-rong，MAO lin-bo.Path Planning Based on Ant Colony Algorithm and Distributed Local Navigation for Multi-Robot-Systems[C]//2006 IEEE International Conference on Mechatronics and Automation，2006：1733-1738.