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

熊億民

(廈門理工學院 設計藝術學院,廈門361024)

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

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

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

1 全向移動機器人全遍歷路徑規劃方法設計

1.1 建立全向移動機器人全遍歷環境模型

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

圖1 拓撲建模示意圖

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

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

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

在拓撲建模示意圖的基礎上,依據移動機器人在原坐標系下的位置信息,利用角度轉換建立了新的環境模型,接下來通過改進蟻群算法為全向移動機器人全遍歷路徑進行規劃,消除全遍歷環境的影響.

1.2 改進蟻群算法

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

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

當螞蟻k從全遍歷路徑節點i移動到節點j時,就會更新局部信息素,具體更新規則為:

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

其中,ε表示更新參數;Lworst表示最差螞蟻的路徑長度;Lbest表示最優螞蟻的路徑長度.

令迭代閾值為R,當迭代次數小于R時,揮發系數就會隨著迭代次數的增加而減小,當迭代次數大于閾值時,揮發系數繼續遞減,即:

其中,γ表示參數;ρ0表示信息素的初始值;Nc表示當前迭代次數.

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

Step 1.初始化迭代參數

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

Step 2.分配初始信息素

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

Step 3.選擇螞蟻路徑

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

Step 4.更新局部信息素

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

Step 5.更新全局信息素

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

Step 6.結束搜索

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

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

1.3 規劃全向移動機器人全遍歷路徑

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

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

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

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

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

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

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

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

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

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

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

綜上所述,采用拓撲建模方法先建立了全向移動機器人全遍歷環境模型,在改進蟻群算法的基礎上,設計全向移動機器人全遍歷路徑規劃流程,實現了全向移動機器人全遍歷路徑的規劃.

2 實驗對比分析

2.1 地圖建模

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

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

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

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

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

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

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

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

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

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

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

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

為了進一步驗證所設計方法的優勢性,設置含有障礙物的環境,運用不同方法在該環境中進行路徑規劃,結果如圖4所示.

圖4 不同方法的路徑規劃效果

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

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

3 結束語

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