基于改進蟻群算法的全向移動機器人全遍歷路徑規(guī)劃①

熊億民

(廈門理工學(xué)院 設(shè)計藝術(shù)學(xué)院,廈門361024)

全向移動機器人的使用使人們的日常生活逐漸受到影響,在全向移動機器人領(lǐng)域中,全遍歷路徑規(guī)劃一直以來都是一個熱點研究話題,路徑規(guī)劃的任務(wù)是在已知地圖信息環(huán)境或未知地圖信息環(huán)境中,依據(jù)時間和距離最短、能耗最低等指標(biāo),規(guī)劃一條全向移動機器人從起點到終點的安全無碰撞路徑[1].

目前,國內(nèi)外很多學(xué)者都在全向移動機器人全遍歷路徑規(guī)劃中做了大量研究,在國外的研究中,將全向移動機器人應(yīng)用到制造行業(yè)的研究進展比較顯著,尤其是美國和日本兩個國家最先將移動機器人引入到國際范圍內(nèi),美國制定了地面天人作戰(zhàn)平臺的戰(zhàn)略計劃,從上世紀(jì)80年代初,就掀起了研究全向移動機器人的序幕.日本除了研究全向移動機器人以外,還將中間件的研究作為未來發(fā)展的重點[2];國內(nèi)的全向移動機器人研究也越來越多,國內(nèi)早就將全向移動機器人技術(shù)的開發(fā)研究作為機器人研究的重要發(fā)展領(lǐng)域[3].傳統(tǒng)蟻群算法運用賦權(quán)矩陣,將機器人途經(jīng)的最短路徑、活動范圍中的障礙物等要素形成一種連通關(guān)系,并采用蟻群算法對各要素的空間距離進行優(yōu)化,從而得到路徑規(guī)劃結(jié)果.雖然傳統(tǒng)蟻群算法考慮了障礙物等對路徑距離產(chǎn)生影響的問題,但是該算法收斂速度慢,容易陷入局部最優(yōu)的缺點.楊洋等[4]為了解決移動機器人在路徑規(guī)劃中遇到的問題,提出面向未知地圖的六足機器人路徑規(guī)劃算法.該算法利用測距組與模糊規(guī)則對障礙物的形狀進行分類,并建立環(huán)境地圖,引入修正的斥力函數(shù),采用人工勢場法進行局部路徑規(guī)劃.仿真實驗結(jié)果顯示,該路徑規(guī)劃方法具有較高的可行性,但是該方法沒有充分考慮全遍歷環(huán)境的影響,導(dǎo)致規(guī)劃得到的路徑較長.王毅等[5]根據(jù)雙圓弧理論提出基于圓弧-直線-圓弧理論的移動機器人路徑規(guī)劃方法,在實驗室環(huán)境下,采用履帶式移動平臺對該方法進行了實驗驗證.實驗結(jié)果表明,該方法在路徑規(guī)劃中橫向誤差均值和縱向誤差均值均較低,表明該方法在應(yīng)用時具有一定的有效性,但是不能有效獲取最優(yōu)路徑.

基于以上背景,對蟻群算法進行改進,并將其應(yīng)用到全向移動機器人全遍歷路徑規(guī)劃中,從而提高全向移動機器人全遍歷路徑的規(guī)劃性能.

1 全向移動機器人全遍歷路徑規(guī)劃方法設(shè)計

1.1 建立全向移動機器人全遍歷環(huán)境模型

采用拓?fù)浣７椒╗6]建立全向移動機器人全遍歷環(huán)境模型,將全遍歷環(huán)境表示為一張具有拓?fù)湟饬x的圖,主要分為可視圖建模法和Voronoi 圖建模法.可視圖建模法[7]是以全遍歷環(huán)境中的障礙物模型為基礎(chǔ),將每一個障礙物都采用多邊形來表示,在可視圖中找到全向移動機器人的起點和終點,并與障礙物之間用直線連接,在連接過程中確保所有連線都不可以穿過障礙物,將最后得到的圖稱為可視圖.如圖1(a)所示.Voronoi 圖建模法[8]是先找出障礙物的頂點位置和邊界,將其余起點和終點相連,得到Voronoi 圖,如圖1(b)所示.

圖1 拓?fù)浣Ｊ疽鈭D

在圖1的基礎(chǔ)上,根據(jù)全向移動機器人的全遍歷空間大小,將全向移動機器人的全遍歷區(qū)域劃分為等間隔的柵格,柵格由全向移動機器人的尺寸來決定.將全向移動機器人在柵格環(huán)境中移動點作為建模的質(zhì)點,灰色表示障礙物,白色表示自由區(qū)域.

在新的環(huán)境建模坐標(biāo)系中,以S(xstart,ystart)為原點,連接全向移動機器人的起點和終點坐標(biāo),順時針旋轉(zhuǎn)?度之后將其作為X軸,將移動機器人在原坐標(biāo)系下的位置坐標(biāo)(X,Y)轉(zhuǎn)換為(X′,Y′),變換式如下:

其中,xstart和ystart表示原點坐標(biāo);a表示偏移角度;b表示目標(biāo)角度.

在拓?fù)浣Ｊ疽鈭D的基礎(chǔ)上,依據(jù)移動機器人在原坐標(biāo)系下的位置信息,利用角度轉(zhuǎn)換建立了新的環(huán)境模型,接下來通過改進蟻群算法為全向移動機器人全遍歷路徑進行規(guī)劃,消除全遍歷環(huán)境的影響.

1.2 改進蟻群算法

傳統(tǒng)蟻群算法在規(guī)劃全向移動機器人全遍歷路徑時初始信息素是相同的,在啟發(fā)信息上蟻群在建立第一條規(guī)劃路徑時,往往比較偏向近目標(biāo)點的位置[9],針對上述問題,為了避免蟻群算法陷入局部最優(yōu),對傳統(tǒng)蟻群算法進行改進,減小啟發(fā)信息對蟻群在搜索過程中的影響,因此,將遞減系數(shù) ξ引入到啟發(fā)函數(shù)中[10],ξ是指函數(shù)的導(dǎo)數(shù)小于0,即隨著自變量的增加,函數(shù)值持續(xù)減少,則得到新的啟發(fā)函數(shù)為:

其中,i和j分別為全遍歷路徑中機器人的起始節(jié)點和終止節(jié)點;g表示全遍歷路徑的中心節(jié)點;dij表示全遍歷路徑節(jié)點i到j(luò)之間的歐式距離;Ljg表示全遍歷路徑節(jié)點j到節(jié)點g之間的距離;Ncmax表示全遍歷路徑規(guī)劃的最大迭代次數(shù);Nc表示當(dāng)前迭代次數(shù).將遞減系數(shù)引入到式(1)中,并根據(jù)式(1)對啟發(fā)函數(shù)進行初始化,從而為信息素的分配提供條件.

當(dāng)螞蟻k從全遍歷路徑節(jié)點i移動到節(jié)點j時,就會更新局部信息素,具體更新規(guī)則為:

其中,λ表示揮發(fā)系數(shù);τ0表示正常量;設(shè)τmax和τmin分別表示信息素的最大值和最小值,當(dāng) τij(t)＜τmin時,則令τij(t)=τmin,當(dāng)τij(t)＞τmax時,則令τij(t)=τmax.當(dāng)所有螞蟻完成一次迭代之后,更新全局信息素[11].在迭代過程中,選擇最優(yōu)螞蟻路徑和最差螞蟻路徑,對最優(yōu)螞蟻執(zhí)行全局更新規(guī)則[12],最差的螞蟻按照下式來更新信息素:

其中,ε表示更新參數(shù);Lworst表示最差螞蟻的路徑長度;Lbest表示最優(yōu)螞蟻的路徑長度.

令迭代閾值為R,當(dāng)?shù)螖?shù)小于R時,揮發(fā)系數(shù)就會隨著迭代次數(shù)的增加而減小,當(dāng)?shù)螖?shù)大于閾值時,揮發(fā)系數(shù)繼續(xù)遞減,即:

其中,γ表示參數(shù);ρ0表示信息素的初始值;Nc表示當(dāng)前迭代次數(shù).

總結(jié)以上計算過程,得到改進蟻群算法的實施步驟如下:

Step 1.初始化迭代參數(shù)

選擇螞蟻行走的起點S、終點G,迭代次數(shù)Nc、最大迭代次數(shù)Ncmax,對螞蟻的數(shù)量、啟發(fā)因子,遞減系數(shù)等進行初始化;

Step 2.分配初始信息素

根據(jù)螞蟻的起點位置和終點位置采用不均衡的方式來分配信息素;

Step 3.選擇螞蟻路徑

將m只螞蟻共同放在起點位置,將起點位置加入到禁忌表中,計算路徑節(jié)點j到終點的距離,得到啟發(fā)信息的具體數(shù)值,再尋找下一個路徑節(jié)點,并添加到禁忌表中,依次循環(huán)上述過程,直到螞蟻到達終點;

Step 4.更新局部信息素

螞蟻每建立一條全遍歷路徑,就會按照式(4)更新一次局部信息素,還要保證每一條信息素的濃度;

Step 5.更新全局信息素

待所有螞蟻完成一次迭代之后,尋找出這一迭代過程中最優(yōu)螞蟻和最差螞蟻,判斷當(dāng)前迭代次數(shù)與閾值的關(guān)系[13],確定揮發(fā)系數(shù),更新最優(yōu)螞蟻和最差螞蟻行走路徑的信息素,確保信息素的濃度;

Step 6.結(jié)束搜索

判斷迭代次數(shù)是否達到最大迭代次數(shù),如果是,將最優(yōu)路徑長度輸出;如果不是,將禁忌表清空,返回Step 3 繼續(xù)進行迭代,直到達到最大迭代次數(shù),將最優(yōu)路徑長度輸出,結(jié)束并行蟻群算法設(shè)計.

根據(jù)蟻群算法存在的問題,將遞減系數(shù)引入到啟發(fā)函數(shù)中,更新局部信息素,通過設(shè)定迭代閾值,調(diào)節(jié)信息素的揮發(fā)系數(shù),對改進蟻群算法進行設(shè)計.接下來通過全向移動機器人全遍歷路徑的規(guī)劃流程設(shè)計,實現(xiàn)全向移動機器人全遍歷路徑的規(guī)劃.

1.3 規(guī)劃全向移動機器人全遍歷路徑

在改進蟻群算法的基礎(chǔ)上,將其應(yīng)用到全向移動機器人全遍歷路徑規(guī)劃中,具體步驟如下:

Step 1.初始化全向移動機器人的行走空間及改進蟻群算法的參數(shù);

Step 2.利用改進的蟻群算法,在分析環(huán)境模型的情況下[14],尋找全向移動機器人的全局路線;

Step 3.將全向移動機器人放置在起點位置,讓全向移動機器人沿著Step 2 的路徑向終點移動,記錄一條新的全向移動機器人行走路線;

Step 4.全向移動機器人邊行走邊探測周圍障礙物的存在情況,如果在行走路線上不能感應(yīng)到動態(tài)障礙物,將Step3 中記錄的機器人行走路線輸出,結(jié)束路徑規(guī)劃;

Step 5.如果全向移動機器人在行走過程中可以感應(yīng)到周圍動態(tài)障礙物,那么就要根據(jù)周圍動態(tài)障礙物的運動規(guī)律[15],判斷機器人是否會與障礙物發(fā)生碰撞;

Step 6.如果兩者之間不會發(fā)生碰撞,全向移動機器人繼續(xù)朝著終點移動;如果兩者之間發(fā)生了碰撞,全向移動機器人就會執(zhí)行避障策略,然后繼續(xù)朝著終點移動;

Step 7.重復(fù)操作Step 3～Step 6,直到全向移動機器人到達終點;

Step 8.輸出全向移動機器人的移動路線,并將全向移動機器人的移動路徑長度輸出.

根據(jù)改進蟻群算法在全向移動機器人全遍歷路徑規(guī)劃中的應(yīng)用步驟,設(shè)計了全向移動機器人全遍歷路徑規(guī)劃流程,如圖2所示.

圖2 全向移動機器人全遍歷路徑規(guī)劃流程

綜上所述,采用拓?fù)浣７椒ㄏ冉⒘巳蛞苿訖C器人全遍歷環(huán)境模型,在改進蟻群算法的基礎(chǔ)上,設(shè)計全向移動機器人全遍歷路徑規(guī)劃流程,實現(xiàn)了全向移動機器人全遍歷路徑的規(guī)劃.

2 實驗對比分析

2.1 地圖建模

全向移動機器人全遍歷環(huán)境建模是規(guī)劃其路徑的前提,通過提取的全遍歷路徑信息,分析得到全向移動機器人可以理解的環(huán)境地圖,使全向移動機器人可以在地圖環(huán)境中規(guī)劃全遍歷路徑.

按照八叉樹規(guī)定全向移動機器人的搜索路徑,將柵格的規(guī)模設(shè)置為Nx行Ny列,第i個柵格的位置坐標(biāo)表示為(xi,yi),全向移動機器人的位置坐標(biāo)與柵格序號的映射關(guān)系為:

其中,Ra表示柵格變長;mod ()表示取余函數(shù);c eil()表示取整函數(shù).

2.2 全向移動機器人全遍歷路徑長度對比試驗

為了對比基于改進蟻群算法的全向移動機器人全遍歷路徑規(guī)劃方法與其他路徑規(guī)劃方法的差異,分別采用所設(shè)計方法、傳統(tǒng)蟻群算法、文獻[4]的全遍歷路徑規(guī)劃方法以及文獻[5]的全遍歷路徑規(guī)劃方法,對全向移動機器人的全遍歷路徑進行規(guī)劃,得到全向移動機器人全遍歷路徑長度對比結(jié)果,如圖3所示.

從圖3的實驗結(jié)果可以看出,采用所設(shè)計方法來規(guī)劃全向移動機器人的全遍歷路徑時,建立了全向移動機器人全遍歷環(huán)境模型,可以讓全向移動機器人更快適應(yīng)工作環(huán)境,并且在改進蟻群算法的基礎(chǔ)上,簡化了全向移動機器人在尋找最優(yōu)路徑時的計算復(fù)雜度,使規(guī)劃得到的全向移動機器人全遍歷路徑長度更短;文獻[5]的全遍歷路徑規(guī)劃方法在規(guī)劃全向移動機器人的全遍歷路徑時,由于該方法不能更好地適應(yīng)全向移動機器人的工作環(huán)境,使規(guī)劃的路徑長度較長;文獻[4]的全遍歷路徑規(guī)劃方法在規(guī)劃全向移動機器人的全遍歷路徑時,由于該方法在全遍歷路徑尋優(yōu)過程中,路徑搜索的時間比較長,且迭代的計算過程也比較復(fù)雜,使規(guī)劃的全遍歷路徑長度較長.而傳統(tǒng)蟻群算法由于存在收斂速度慢,容易陷入局部最優(yōu)的問題,導(dǎo)致路徑長度更長.根據(jù)上述分析可知,所設(shè)計方法能夠有效縮短機器人移動路徑長度,提高路徑規(guī)劃能力.

圖3 全向移動機器人全遍歷路徑長度對比結(jié)果

2.3 全向移動機器人全遍歷路徑規(guī)劃時間對比試驗

以迭代次數(shù)為自變量,分別采用所設(shè)計方法、傳統(tǒng)蟻群算法、文獻[4]的全遍歷路徑規(guī)劃方法以及文獻[5]的全遍歷路徑規(guī)劃方法,對全遍歷路徑進行規(guī)劃,得到路徑規(guī)劃時間對比結(jié)果如表1所示.

從表1的實驗結(jié)果可以看出,隨著迭代次數(shù)的增加,不同方法規(guī)劃全向移動機器人全遍歷路徑的用時都在變長,但是所設(shè)計方法由于將并行蟻群算法應(yīng)用到了全遍歷路徑規(guī)劃中,簡化了全遍歷路徑的尋優(yōu)過程,從而縮短了全遍歷路徑的規(guī)劃時間;文獻[4]的全遍歷路徑規(guī)劃方法、文獻[5]的全遍歷路徑規(guī)劃方法以及傳統(tǒng)蟻群算法由于迭代的過程比較復(fù)雜,使全向移動機器人全遍歷路徑規(guī)劃時間更長.

表1 路徑規(guī)劃時間對比結(jié)果(單位:min)

2.4 全向移動機器人全遍歷路徑規(guī)劃效果對比

為了進一步驗證所設(shè)計方法的優(yōu)勢性,設(shè)置含有障礙物的環(huán)境,運用不同方法在該環(huán)境中進行路徑規(guī)劃,結(jié)果如圖4所示.

圖4 不同方法的路徑規(guī)劃效果

分析圖4可知,傳統(tǒng)蟻群算法、文獻[4]的全遍歷路徑規(guī)劃方法以及文獻[5]的全遍歷路徑規(guī)劃方法不能有效躲避障礙物,使機器人移動過程中產(chǎn)生了一些不必要的路徑,加大了路徑一定成本.相比較之下,所設(shè)計方法規(guī)劃得出的路徑能夠有效躲避障礙物,并且路徑接近于直線,路徑長度更短.這是由于改進蟻群算法將遞減系數(shù) ξ引入到啟發(fā)函數(shù)中,避免了蟻群算法陷入局部最優(yōu)的問題,降低了啟發(fā)信息對蟻群在搜索過程中的影響,因此,提升了路徑規(guī)劃效果.通過上述分析可知,所設(shè)計方法能夠獲得最優(yōu)路徑.

綜合以上實驗結(jié)果,基于并行蟻群算法的全向移動機器人全遍歷路徑規(guī)劃方法無論是在路徑長度和路徑規(guī)劃時間上,相比于其他路徑規(guī)劃方法都具有更大優(yōu)勢,并且該方法能夠獲得最優(yōu)路徑,充分驗證了該方法的有效性.

3 結(jié)束語

本文提出了基于改進蟻群算法的全向移動機器人全遍歷路徑規(guī)劃方法,結(jié)果顯示,該方法在規(guī)劃全向移動機器人全遍歷路徑過程中具有較高的路徑規(guī)劃性能.但是本文設(shè)計的路徑規(guī)劃方法主要應(yīng)用在靜態(tài)電子地圖中,在今后的研究中,要加強在動態(tài)電子地圖中的應(yīng)用,提高其在路徑規(guī)劃上的實用性.