熊億民

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 2.分配初始信息素

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

Step 3.選擇螞蟻路徑

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

Step 4.更新局部信息素

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

Step 5.更新全局信息素

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

Step 6.結(jié)束搜索

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

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

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

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

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

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

Step 3.將全向移動(dòng)機(jī)器人放置在起點(diǎn)位置,讓全向移動(dòng)機(jī)器人沿著Step 2 的路徑向終點(diǎn)移動(dòng),記錄一條新的全向移動(dòng)機(jī)器人行走路線;

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

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

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

Step 7.重復(fù)操作Step 3～Step 6,直到全向移動(dòng)機(jī)器人到達(dá)終點(diǎn);

Step 8.輸出全向移動(dòng)機(jī)器人的移動(dòng)路線,并將全向移動(dòng)機(jī)器人的移動(dòng)路徑長(zhǎng)度輸出.

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

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

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

2 實(shí)驗(yàn)對(duì)比分析

2.1 地圖建模

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

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

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

2.2 全向移動(dòng)機(jī)器人全遍歷路徑長(zhǎng)度對(duì)比試驗(yàn)

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

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

圖3 全向移動(dòng)機(jī)器人全遍歷路徑長(zhǎng)度對(duì)比結(jié)果

2.3 全向移動(dòng)機(jī)器人全遍歷路徑規(guī)劃時(shí)間對(duì)比試驗(yàn)

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

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

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

2.4 全向移動(dòng)機(jī)器人全遍歷路徑規(guī)劃效果對(duì)比

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

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

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

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

3 結(jié)束語(yǔ)

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