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

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

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

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

1 環(huán)境描述

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

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

2.1 算法原理

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

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

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

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

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

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

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

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

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

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

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

且：

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4] 任春明，張建勛.基于優(yōu)化蟻群算法的機(jī)器人路徑規(guī)劃[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.