基于改進(jìn)蟻群算法的巡檢機器人避障路徑規(guī)劃方法設(shè)計

李 鵬，閔小翠，王建華

(廣州華立科技職業(yè)學(xué)院，廣東 廣州 511325)

0 引言

機器人的避障路徑規(guī)劃一直是機器人研發(fā)領(lǐng)域重要的研究課題。人們將人工智能與機器人研發(fā)領(lǐng)域進(jìn)行結(jié)合[1]，從而有效地解決了機器人工作時的避障規(guī)劃問題[2]。巡檢機器人作為實用性機器人的一種，在工作時準(zhǔn)確地躲避工作空間中的障礙，快速移動到目標(biāo)區(qū)域，更是該類機器人工作安全進(jìn)行的保障[3]。

封碩等[4]提出基于雙粒子群算法的礦井搜救機器人路徑規(guī)劃，該方法在計算障礙物時存在一定問題，導(dǎo)致其在規(guī)劃路徑時所需的迭代次數(shù)多。毛鵬軍等[5]提出基于Q-學(xué)習(xí)的果園機器人避障算法研究，該方法截取雷達(dá)數(shù)據(jù)時存在一定問題，所以在進(jìn)行路徑規(guī)劃時的收斂速度慢。

為解決上述方法中存在的問題，提出基于改進(jìn)蟻群算法的巡檢機器人避障路徑規(guī)劃方法。

1 環(huán)境建模

在巡檢機器人工作的二維環(huán)境空間內(nèi)，存在若干障礙物，因此要基于可視的已知信息對該空間進(jìn)行遍歷，構(gòu)建巡檢機器人工作環(huán)境的二維柵格地圖模型[6]。

1.1 環(huán)境空間劃分

設(shè)定巡檢機器人在工作區(qū)間的移動區(qū)域為A，構(gòu)建一個二維坐標(biāo)系，該移動區(qū)域的左下角設(shè)定為O點，水平向右為坐標(biāo)系X軸方向，垂直向上為坐標(biāo)系Y軸方向。若巡檢機器人的最小活動步長為δ，且在構(gòu)建的二維坐標(biāo)系X、Y方向的最大值為Xmax和Ymax，基于δ對巡檢機器人的移動區(qū)域進(jìn)行劃分處理，使每行的柵格數(shù)為Nx=Xmax/δ，每列的柵格數(shù)為Ny=Ymax/δ，由此構(gòu)建m×n的柵格矩陣，結(jié)果為

(1)

c為向上運算因子。

1.2 建立像素矩陣

假定A中存在靜態(tài)障礙物l個，經(jīng)過膨脹處理后，會在構(gòu)建的柵格地圖中占一定位置，因此要將構(gòu)建的二維柵格地圖劃分為障礙區(qū)域集O以及自由活動區(qū)域集F，且F=A-O。依據(jù)該項劃分結(jié)果，完成障礙物空間的像素矩陣的構(gòu)建，過程為

(2)

其中，構(gòu)建的像素矩陣標(biāo)記為M(i,j)形式。

1.3 識別柵格

在對巡檢機器人進(jìn)行路徑規(guī)劃時，需要對構(gòu)建的柵格地圖進(jìn)行有效識別，識別時可利用序號法以及直角坐標(biāo)法對柵格進(jìn)行識別。

a.序號法：在構(gòu)建的二維直角坐標(biāo)系中，依照從下至上、由左至右的順序?qū)鸥襁M(jìn)行排序，并對柵格進(jìn)行序號標(biāo)記。

標(biāo)記時，設(shè)定C={1,2,…,M}為柵格的序號集，坐標(biāo)系中g(shù)(1,1)為序號1，g(1,2)為序號2，直至標(biāo)記完成。

b.直角坐標(biāo)法：依據(jù)上述構(gòu)建的二維直角坐標(biāo)系，獲取每個柵格的區(qū)間邊長。首先設(shè)定g∈A為地圖中的任意柵格，A中的所有g(shù)的集合標(biāo)記為Ag，則O∈Ag。若Ag中的每一個g在坐標(biāo)系中都有屬于自己的位置(x,y)，則將該位置記為g(x,y)。

由于2種標(biāo)識方法都基于柵格地圖，所以2種方法屬于互相映射關(guān)系，結(jié)果為

(3)

舍余運算標(biāo)記為mod；求余運算標(biāo)記為int。

將上述的2種標(biāo)識方法結(jié)合，對獲取的像素矩陣進(jìn)行編碼處理，獲取序號的單元坐標(biāo)[7]。過程中需要對像素矩陣與單元序號，以及單元坐標(biāo)到單元序號之間的映射關(guān)系進(jìn)行獲取，結(jié)果為

(4)

i為x軸方向的障礙位置；j為y軸方向的障礙物位置；gx(i,j)為x軸的單元序號映射關(guān)系；gy(i,j)為y軸的單元序號映射關(guān)系；N(i,j)為像素矩陣與單元序號之間的映射關(guān)系；m為障礙物數(shù)量；δ為機器人步長。

將獲取的2個映射關(guān)系進(jìn)行整合，獲取坐標(biāo)單元與序號之間的映射關(guān)系，結(jié)果為

N(x,y)=mx(y+0.5δ-1)+x+0.5δ

(5)

N(x,y)為坐標(biāo)單元與序號之間的映射關(guān)系。

1.4 邏輯對應(yīng)

依據(jù)上述分析可知，機器人移動區(qū)域?g∈Ag，且g?O，那么g為柵格中的可行節(jié)點，將所有的可行節(jié)點進(jìn)行整合，構(gòu)建可行域記作F。

首先需要依據(jù)邏輯邊獲取判定條件，過程中設(shè)定Ni∈F，那么柵格點Ni與柵格點Nj二者間就可以生成邏輯邊，過程為

(6)

d(Ni,Nj)為獲取的邏輯邊。

由于柵格法會將連續(xù)的路徑信息進(jìn)行離散化處理，因此可將巡檢機器人的移動軌跡劃分成單個的運動信息，并將其保留在各個柵格中。再基于柵格中保存的信息，將機器人的移動方向進(jìn)行細(xì)致的劃分。

2 路徑規(guī)劃

基于上述構(gòu)建的環(huán)境模型，利用改進(jìn)的蟻群算法完成對巡檢機器人避障路徑的規(guī)劃[8]。

2.1 蟻群算法

通常情況下，螞蟻在進(jìn)行信息傳遞時，由于信息素的原因，上一代螞蟻遺留下的信息素會對下一代產(chǎn)生影響。蟻群在運動時，由于信息素的擴散，導(dǎo)致螞蟻在尋找最佳路徑時，2只螞蟻的運動軌跡發(fā)生重疊，因此要將人工勢場與蟻群算法進(jìn)行結(jié)合，實現(xiàn)機器人避障路徑規(guī)劃[9]。因此，螞蟻需要在障礙物與目標(biāo)點的勢場方向建立局部啟發(fā)信息素，提高螞蟻在尋找路徑時的預(yù)避障能力，從而蟻群能夠適應(yīng)子空間的搜索。

設(shè)定在尋找最佳路徑時遭受的障礙物斥力為f1以及f2，目標(biāo)點引力標(biāo)記為fa，機器人受力方向為θ，大小為λ，二者合力為f(λ,θ)。尋找過程中可根據(jù)機器人受力方向與相鄰柵格之間的角度差確定信息素的擴散方向。

將信息素濃度以及目標(biāo)距離設(shè)定為高斯分布，這樣就能讓信息素在擴散時朝目標(biāo)方向進(jìn)行擴散，由此構(gòu)建信息素的簡化擴散模型。設(shè)定該簡化模型為椎體形狀，高為L，頂角為γ，擴散半徑為lo，柵格中i點位置的信息素標(biāo)記為q(i)，第i個柵格點與第j個柵格點之間的距離為η。本次螞蟻搜尋路徑的信息素擴散過程，結(jié)果為

(7)

基于柵格的環(huán)境特性，人工勢場的勢場力f(λ,θ)會發(fā)生變化，所以需要依據(jù)機器人的受力方向以及受力大小將信息素進(jìn)行平滑處理[10]。

(8)

(9)

基于上述計算結(jié)果，螞蟻只需向信息素濃密的方向進(jìn)行搜索，即可快速尋找出巡檢機器人的最佳移動路徑。

2.2 算法流程

a.基于柵格法，生成巡檢機器人移動場地的環(huán)境柵格地圖模型，設(shè)定有障礙物的柵格為1，無障礙柵格為0；模型的左下角為起始點S，目標(biāo)點為E。

b.對蟻群以及人工勢場進(jìn)行初始化處理。

d.計算第k只螞蟻從第i個柵格點轉(zhuǎn)移至第j個柵格點的轉(zhuǎn)移概率，結(jié)果為

(10)

e.將第j個柵格點加入BK中。并對上述過程進(jìn)行迭代計算，直至全部螞蟻到達(dá)終點。對所有螞蟻路徑進(jìn)行保存。

f.更新信息素矩陣，更新結(jié)果為：

(11)

(12)

(13)

Q為信息素強度；ρ為揮發(fā)因子；Lk為第k只螞蟻走過的最長路徑。

g.在尋找出的路徑中找出最短路徑作為巡檢機器人避障的最短路徑，完成機器人的路徑規(guī)劃。

3 實驗分析

為了驗證基于改進(jìn)蟻群算法的巡檢機器人避障路徑規(guī)劃方法的整體有效性，需要對該方法進(jìn)行有效測試。

分別采用基于改進(jìn)蟻群算法的巡檢機器人避障路徑規(guī)劃方法(本文方法)、基于雙粒子群算法的礦井搜救機器人路徑規(guī)劃算法(文獻(xiàn)[4]方法)以及基于Q-學(xué)習(xí)的果園機器人避障算法(文獻(xiàn)[5]方法)進(jìn)行巡檢機器人避障路徑規(guī)劃測試。

a.避障路徑規(guī)劃方法的收斂速度對規(guī)劃效果產(chǎn)生的影響巨大，收斂速度越快，路徑的規(guī)劃效果就越好。在對巡檢機器人進(jìn)行避障路徑規(guī)劃時，對3種方法的收斂速度進(jìn)行測試，測試結(jié)果如圖1所示。

圖1 不同方法的收斂速度測試結(jié)果

分析圖1可知，本文方法在進(jìn)行路徑搜索時所檢測出的收斂速度要高于其他2種方法。由此可知，利用本文方法進(jìn)行巡檢機器人避障路徑規(guī)劃時的收斂速度快。

b.進(jìn)行巡檢機器人避障路徑規(guī)劃時，對3種方法規(guī)劃的路徑長度進(jìn)行對比，測試結(jié)果如圖2所示。

圖2 不同方法的路徑規(guī)劃長度檢測結(jié)果

分析圖2可知，隨著檢測次數(shù)的不斷增加，3種方法檢測出的路徑長度均有所增加，而經(jīng)過本文方法所搜尋出的巡檢機器人避障路徑是3種方法中最短的。由此可知，本文方法在進(jìn)行巡檢機器人避障路徑規(guī)劃時的規(guī)劃路徑短，規(guī)劃效果好。

c.路徑規(guī)劃過程中，迭代次數(shù)與規(guī)劃路徑的長度存在相關(guān)。基于上述檢測結(jié)果，對3種方法在進(jìn)行機器人避障路徑規(guī)劃時的迭代次數(shù)進(jìn)行測試，測試結(jié)果如圖3所示。

圖3 不同方法的迭代次數(shù)檢測結(jié)果

分析圖3可知，路徑的長度越長，巡檢機器人進(jìn)行避障路徑規(guī)劃時的所需的迭代次數(shù)就越多，而本文方法在進(jìn)行巡檢機器人避障路徑規(guī)劃時所需要的迭代次數(shù)較其他2種方法要少。

d.基于上述實驗結(jié)果，對3種方法的路徑規(guī)劃時間進(jìn)行測試，測試結(jié)果如圖4所示。

圖4 不同方法的規(guī)劃時間測試結(jié)果

分析圖4可知，隨著路徑長度的不斷增加，3種路徑規(guī)劃方法的路徑規(guī)劃時間均呈現(xiàn)不同程度的增加趨勢。本文方法的避障路徑規(guī)劃時間低于其他2種方法。

4 結(jié)束語

針對傳統(tǒng)機器人避障路徑規(guī)劃方法中存在的問題，提出基于改進(jìn)蟻群算法的巡檢機器人避障路徑規(guī)劃方法。該方法首先基于柵格法構(gòu)建環(huán)境地圖模型；再將人工勢場法與蟻群算法進(jìn)行結(jié)合，通過對路徑的搜尋，完成機器人避障路徑的規(guī)劃。實驗結(jié)果表明，該方法的避障規(guī)劃路徑距離短、規(guī)劃時間短，具有一定的有效性。