一種改進(jìn)柵格蟻群算法的機(jī)器人路徑規(guī)劃

梁玉清，李 妍，何靜濤

(蚌埠學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，安徽蚌埠 233030)

機(jī)器人路徑規(guī)劃是機(jī)器人在已知的環(huán)境中，自主尋找一條優(yōu)化路徑.多種算法都被應(yīng)用于這一領(lǐng)域，實(shí)踐中發(fā)現(xiàn)，單一的算法，往往存在著效率不高、搜索空間過(guò)大等缺點(diǎn).而將幾種算法結(jié)合在一起，利用各自的優(yōu)點(diǎn)，可以使規(guī)劃的路徑相對(duì)最優(yōu).柵格法能確保穩(wěn)定地找到優(yōu)化路徑，但柵格密度的大小會(huì)影響到算法的效率.蟻群算法模擬了螞蟻尋找食物的路徑行為，常用于解決機(jī)器人的路徑規(guī)劃問題，但也存在著收斂慢及容易出現(xiàn)停滯等不足之處［1－4］.

由于蟻群算法易于與其它算法結(jié)合，很多研究者提出了一些改進(jìn)的蟻群算法.如文獻(xiàn)［5］提出多級(jí)路徑優(yōu)化的路徑規(guī)劃策略，加強(qiáng)蟻群算法搜索的正反饋、高效收斂的優(yōu)勢(shì)，避免算法過(guò)早或過(guò)晚結(jié)束而影響劃分算法的整體性能，使得信息柵格節(jié)點(diǎn)調(diào)度能依據(jù)任務(wù)量和路徑性能進(jìn)行有效分配.但在復(fù)雜結(jié)構(gòu)的真實(shí)信息柵格環(huán)境下的節(jié)點(diǎn)調(diào)度效率還不是很高，在路徑陷阱和可行路徑的平滑性上仍需進(jìn)一步解決.文獻(xiàn)［6］在蟻群算法中融入了遺傳算法的交叉、變異操作以加快算法收斂.改進(jìn)后基于蟻群算法的路徑搜索更簡(jiǎn)單，但如果遇到結(jié)構(gòu)復(fù)雜、障礙物多的環(huán)境時(shí)，因?yàn)閺?fù)雜度的提高，算法的性能會(huì)受到一定的影響.

本文提出的改進(jìn)算法是，在柵格法對(duì)環(huán)境建模的基礎(chǔ)上，通過(guò)調(diào)整距離啟發(fā)信息等改進(jìn)蟻群算法，提高復(fù)雜環(huán)境下最優(yōu)路徑搜索效率，仿真實(shí)驗(yàn)結(jié)果表明這種復(fù)合的算法在復(fù)雜環(huán)境下得到的路徑最短，程序運(yùn)行效率高.

圖1 環(huán)境建模示意圖Fig.1 Schematic diagram of environmental modeling

1 問題定義及建模

如圖1所示，機(jī)器人起始位置為S(xs，ys)，目標(biāo)位置為G(xg，yg)，以S點(diǎn)為坐標(biāo)原點(diǎn)，SG為X'軸，垂直于SG的直線為Y'軸，將線段SG劃分為m等分，再將每一等分線m等分，將規(guī)劃范圍分為m×m柵格.柵格點(diǎn)在新坐標(biāo)系與原坐標(biāo)系的關(guān)系如下，其中為α新坐標(biāo)系旋轉(zhuǎn)的角度.

機(jī)器人的位置坐標(biāo)也用柵格坐標(biāo)表示，機(jī)器人在某位置坐標(biāo)p(x，y)與柵格坐標(biāo)g(x，y)的對(duì)應(yīng)關(guān)系為:

2 蟻群算法

柵格法建模中，將一個(gè)柵格的大小等效為一個(gè)實(shí)際機(jī)器人的大小;從一個(gè)柵格到另一個(gè)柵格的移動(dòng)就相當(dāng)于機(jī)器人實(shí)際從一個(gè)點(diǎn)移動(dòng)到另外一個(gè)點(diǎn);柵格模型中起始點(diǎn)到目標(biāo)點(diǎn)的路徑規(guī)劃完成了，說(shuō)明實(shí)際中機(jī)器人找到了一個(gè)起始點(diǎn)到目的點(diǎn)的路徑.

以機(jī)器人在柵格內(nèi)自由運(yùn)動(dòng)的最長(zhǎng)距離Ra為步長(zhǎng)，SG在X方向的最大值為Xmax，在Y方向的最大值為Ymax.每行的柵格數(shù)Nx=Xmax/Ra，每列的柵格數(shù)為Ny=Ymax/Ra.

任意柵格g的坐標(biāo)g(x，y)，x=row，y=col，row是行號(hào)，col是列號(hào)，坐標(biāo)值與序號(hào)i的對(duì)應(yīng)關(guān)系根據(jù)式(2)確定:

蟻群算法中，信息素是引導(dǎo)螞蟻運(yùn)動(dòng)的重要物質(zhì).螞蟻選擇信息素濃度較高的路移動(dòng)，信息素濃度越高，選擇的可能性越大，這是蟻群算法的正反饋特點(diǎn)［7－8］.

螞蟻的轉(zhuǎn)移有一定的規(guī)則，柵格i的螞蟻k如何選擇下一個(gè)柵格節(jié)點(diǎn)j，應(yīng)按照公式(4)或者公式(5)列出規(guī)則執(zhí)行，j∈allowedk且 j?tabuk.allowedk是可行區(qū)域，tabuk是禁忌表［9］.

其中:q是在［0，1］區(qū)間均勻分布的隨機(jī)數(shù)，q0是一個(gè)參數(shù).當(dāng)q＞q0時(shí)，須先計(jì)算可行節(jié)點(diǎn)的轉(zhuǎn)移概率值，然后運(yùn)用輪盤賭規(guī)則選擇節(jié)點(diǎn) j，以獲得S值.τij是信息素軌跡強(qiáng)度，ηjg是能見度，一般將 ηjg的值設(shè)置為1/d(j，g)，d(j，g)表示距離.積累信息和啟發(fā)信息的相對(duì)重要性用α、β表示.ρlocal是局部信息素?fù)]發(fā)參數(shù)，且 0＜ρlocal≤1.

當(dāng)一條完整的路徑建立后，公式(6)將更新路徑信息.Q是總信息量;己走過(guò)的路程用L表示.

在算法中，全局最優(yōu)的螞蟻才可以釋放信息素，當(dāng)所有螞蟻完成路徑后，式(7)將更新建立的路徑.

ρglobal為全局信息素?fù)]發(fā)系數(shù)，0＜ρglobal≤1.Lbest表示目前為止找出的全局最優(yōu)路徑長(zhǎng)度.螞蟻從柵格gi移動(dòng)到柵格gj后，會(huì)及時(shí)更新局部信息素，目的是減少對(duì)后面的螞蟻的吸引力，從而增加螞蟻選路的多樣性［10－11］.

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

3.1 信息素的存儲(chǔ)處理

信息素存儲(chǔ)一般采用M×M節(jié)點(diǎn)模式.如一個(gè)20×20的柵格，信息素存儲(chǔ)空間為400.但在蟻群算法路徑規(guī)劃中，只會(huì)用到很少的一部分，即每個(gè)節(jié)點(diǎn)鄰域?yàn)?，因此只要建立周圍8個(gè)節(jié)點(diǎn)的信息素關(guān)聯(lián)，而且兩節(jié)點(diǎn)間信息存儲(chǔ)的無(wú)方向，所以每節(jié)點(diǎn)只需4個(gè)信息素關(guān)聯(lián)，信息素存儲(chǔ)空間大大降低.

3.2 調(diào)整距離啟發(fā)信息

距離啟發(fā)信息η一般設(shè)為η=1/Lij或η=1/Ljg.Lij是相鄰兩點(diǎn)的距離.Ljg是j到g的距離.第一條路徑建立時(shí)，需要距離啟發(fā)信息引導(dǎo)，往往會(huì)選擇最短路徑點(diǎn).當(dāng)η值為1/Lij時(shí)，螞蟻傾向于走直線;當(dāng)η的值為1/Ljg時(shí)，螞蟻總傾向于走斜線而非直線，為了均衡兩者的影響我們將η改進(jìn)定義為下式所示的形式:

3.3 螞蟻回退策略

遇到陷阱，一般的處理方法就是消除陷阱.即:在初始環(huán)境時(shí)，將障礙物作給予一定的設(shè)定，使環(huán)境中障礙物變成非凹形，因而凹形障礙造成的陷阱將不復(fù)存在.如圖3所示.

更為復(fù)雜的是，該處理方法可以避免單個(gè)障礙物陷阱，但障礙物與障礙物之間、障礙物與環(huán)境邊界之間的陷阱，如針對(duì)1→6→11→16或5→10→15→20的情形，沒有有效的辦法.為解決上述的問題，本文提出一種螞蟻回退策略，步驟如下:

步驟2:螞蟻從13回到8，N(k)=N(k)+1，tabu(N(k))=8.

步驟4:螞蟻從8回到3，N(k)=N(k)+1，tabu(N(k))=3.

圖2 落入陷阱Fig.2 Fall into the trap

圖3 陷阱障礙物初始處理Fig.3 Traps obstades initial treatment

即使螞蟻通過(guò)回退策略逃離了陷阱，但也會(huì)留下信息素，使得該陷阱周圍的信息素有所增強(qiáng)，而下一代螞蟻很容易再次選擇此路徑.如果這樣的話，找到最短路徑的時(shí)間會(huì)大幅度增加，甚至找不到最優(yōu)化路徑.因而，采用懲罰函數(shù)，使螞蟻盡可能不重復(fù)陷阱周圍的路徑.遇到陷阱時(shí)，用懲罰函數(shù)代替原局部信息素更新公式，以減少陷阱周圍路徑上信息素，以提高搜索效率.懲罰函數(shù)定義如下:

3.4 改進(jìn)蟻群算法的路徑規(guī)劃

步驟1:若干螞蟻位于起始點(diǎn)，設(shè)信息素濃度初始值為l，最大循環(huán)次數(shù)Nc.

步驟2:螞蟻周圍有可轉(zhuǎn)移節(jié)點(diǎn)嗎?如果有，則計(jì)算τij，依據(jù)公式(4)、(5)選擇下一個(gè)節(jié)點(diǎn);如果沒有，表明螞蟻落入陷阱，應(yīng)返回.

步驟3:螞蟻是否到達(dá)目標(biāo)點(diǎn)?到達(dá)，轉(zhuǎn)步驟4;未到，轉(zhuǎn)步驟2.

步驟4:所有螞蟻都從起點(diǎn)到終點(diǎn)后，選出其中的最優(yōu)路徑和最差路徑，利用公式(6)更新信息素.

步驟5:從路徑中選出全局最優(yōu)和最差，利用公式(7)進(jìn)行信息素更新，Nc=Nc+1.

步驟6:是否達(dá)到最大循環(huán)次數(shù)Nc?已經(jīng)達(dá)到，則進(jìn)入步驟7，否則，返回步驟2.

步驟7:輸出最優(yōu)路徑.

4 結(jié)果與分析

實(shí)驗(yàn)采用“博創(chuàng)科技”的自主移動(dòng)機(jī)器人作為實(shí)驗(yàn)平臺(tái)，該平臺(tái)采用高負(fù)載能力和高運(yùn)動(dòng)精度的直流伺服控制，控制計(jì)算機(jī)為嵌入式控制器，配備多種傳感器和機(jī)械手等執(zhí)行器.

實(shí)驗(yàn)場(chǎng)地為6 m×6 m，劃分柵格編號(hào)N為:0～399，機(jī)器人的起點(diǎn)(0，0)，柵格號(hào)N=0，終點(diǎn)為(0，19)，柵格號(hào) N=19.障礙物設(shè)定為4個(gè)矩形，大小為20 cm×10 cm、15 cm×20 cm、40 cm×20 cm、10 cm×10 cm，在路徑規(guī)劃中機(jī)器人可以選擇自由柵格作為它的路徑點(diǎn).

通過(guò)實(shí)驗(yàn)比較基本蟻群算法與改進(jìn)蟻群算法，基本算法和改進(jìn)算法各進(jìn)行10次實(shí)驗(yàn)，對(duì)結(jié)果取平均值.設(shè)定最大循環(huán)次數(shù)為100次(外循環(huán)20次，內(nèi)循環(huán)5次).實(shí)驗(yàn)結(jié)果見表1.

實(shí)驗(yàn)結(jié)果表明，對(duì)信息素更新規(guī)則進(jìn)行修改后，路徑長(zhǎng)度有所縮短，轉(zhuǎn)彎次數(shù)減少，路徑的平滑度有一定優(yōu)化.結(jié)果還顯示，改進(jìn)蟻群算法的平均迭代次數(shù)較之基本蟻群算法大幅減少，收斂性有了較好改善，但因?yàn)樵黾恿藢?duì)局部循環(huán)信息素的更新，使得運(yùn)行時(shí)間有所增加.

改進(jìn)蟻群算法每次實(shí)驗(yàn)的數(shù)據(jù)見表2.數(shù)據(jù)顯示，每次實(shí)驗(yàn)都能找到最優(yōu)路徑，且平均路徑長(zhǎng)度與最優(yōu)路徑長(zhǎng)度相同，說(shuō)明該算法有較高的穩(wěn)定性.實(shí)驗(yàn)迭代次數(shù)除其中有2次較高外，其它均小于18次，說(shuō)明該算法能夠很快地收斂.顯然，改進(jìn)算法的性能優(yōu)于基本算法.

表1 基本算法與改進(jìn)算法對(duì)照表Tab.1 Comparison table of the basic algorithm and improved algorithm

表2 迭代次數(shù)與最優(yōu)路徑長(zhǎng)度Tab.2 Number of iterations and optimal path length

5 結(jié)論

在機(jī)器人的路徑規(guī)劃中，改進(jìn)蟻群算法動(dòng)態(tài)地調(diào)整ρ值，并將ρ值限制在［τmin，τmax］之間，并在算法步驟中，增添了選出局部最優(yōu)值和局部最差值的步驟，在每輪循環(huán)結(jié)束后，增強(qiáng)最優(yōu)，減弱最差，優(yōu)化了路徑長(zhǎng)度和路徑平滑度.但算法中增加了局部循環(huán)信息素的更新，運(yùn)行時(shí)間比基本蟻群算法要長(zhǎng).

［1］張捍東，鄭睿，岑豫皖.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望［J］.系統(tǒng)仿真學(xué)報(bào)，2005，17(2):439－443.

［2］蔡自興，賀漢根，陳虹.未知環(huán)境中移動(dòng)機(jī)器人導(dǎo)航控制研究的若干問題［J］.控制與決策，2002，17(4):385－390.

［3］王志文，郭戈.移動(dòng)機(jī)器人導(dǎo)航技術(shù)現(xiàn)狀與展望［J］.機(jī)器人，2003，25(5):470－474.

［4］朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃綜述［J］.控制與決策，2010，25(7):961－967.

［5］吳沉寒，羅玉臣，陳煒.改進(jìn)蟻群自適應(yīng)多級(jí)柵格路徑優(yōu)化策略［J］.計(jì)算機(jī)工程，2009，35(9):185－186.

［6］范佳，錢徽，朱淼良，等.優(yōu)化路徑分配的多作業(yè)機(jī)器人任務(wù)規(guī)劃［J］.計(jì)算機(jī)工程，2010，36(23):142－145.

［7］周蘭鳳，徐芳.一種考慮不確定性的機(jī)器人路徑規(guī)劃方法［J］.微電子學(xué)與計(jì)算機(jī)，2010，27(7):86－93.

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

［9］Stuezle T，Dorigo M.A short convergence proof for a class of ant colony optimization algorithms［J］.IEEE Transactions on Evolutionary Computation，2002，6(4):358－365.

［10］Meng C，Wang T M.A global optimal path planning algorithm for mobile robot［J］.Robot，2008，30(3):217－222.

［11］Zhu Q B，Zhang Y L.An Ant Colony Algorithm Based on Grid Method for Mobile Robot Path Planning［J］.Robot，2005，27(2):132－135.