基于改進PSO算法的移動機器人最優路徑規劃*

黨博宇,李海燕

(東北大學a.信息科學與工程學院;b.計算機科學與工程學院,沈陽 110819)

0 引言

路徑規劃作為機器人自主導航的核心技術,提出了多種算法,如A*算法[1]、蟻群優化算法[2]、改進人工勢場法[3]、遺傳算法[4]等。上述方法在環境簡單、靜態障礙物條件下,通過環境建?；蛘咚阉骺梢酝瓿陕窂揭巹澣蝿誟5-6]。然而,機器人實際運動中不僅有靜態障礙物還有動態障礙物,現實環境通常具有不確定性,隨機障礙物環境下機器人規劃安全無碰撞的最優路徑極為重要。

近年來,粒子群算法(PSO)由于搜索快速、效率高、算法易于實現,廣泛應用于機器人路徑規劃的研究[7]。TANG等[8]提出了多機器人協同粒子群優化算法,改進了粒子停滯更新問題;ZHANG等[9]利用慣性權重和加速因子提高PSO算法的收斂速度,避免粒子陷入局部極小點;TAN等[10]將蟻群算法和PSO算法相結合,規劃了點焊機器人的最優運動路徑。上述研究僅考慮了運動環境中的靜態障礙物,未能解決機器人遇到隨機障礙物的問題。

移動機器人在實際工作場景中,由于運動環境的不確定性,往往會出現隨機障礙物,嚴重影響機器人的安全運動。LI等[11]提出了A*和動態窗口(DWA)融合的軌跡規劃算法,利用改進的A*算法規劃全局路徑,再結合DWA算法實現實時避障;KOBAYASHI等[12]提出了DWA方法,對靜態和動態障礙物的位置進行預測,實現了虛擬機械手的路徑規劃;DAI等[13]提出了改進的Informed-RRT*算法并融合DWA方法,實現了機器人的自主導航。雖然上述研究利用DWA方法實現了動態障礙物的避障,然而沒有考慮避開障礙物后再次返回已經規劃的全局路徑的問題,增加了重新規劃路徑的計算成本。

針對隨機障礙物環境下移動機器人路徑規劃問題,本文利用隨機數和權函數改進了PSO優化算法,構建了機器人的全局最優運動路徑;再結合DWA方法安全避障全局路徑上的隨機障礙物,并確保機器人返回全局路徑;通過仿真和實驗研究,驗證了文中方法的有效性和優越性。

1 移動機器人運動學模型

移動機器人結構如圖1所示,其具有獨立驅動的4個防滑車輪,每個輪子均由輪轂無刷電機、變速箱和編碼器組成,可以快速適應復雜的運動環境,并實現自主移動。

圖1 移動機器人結構

機器人運動學模型描述為:

(1)

vmin≤v≤vmax

(2)

(3)

2 改進粒子群算法的最優路徑規劃

2.1 機器人的次優路徑規劃

為了構建機器人的可運動空間,利用MAKLINK線得到機器人的所有可允許運動路徑(如圖2所示),在此基礎上采用Dijkstra算法規劃機器人運動的次優路徑。

圖2 機器人的運動路徑

令d表示兩連接點間的距離,從起點S1開始,有:

d(S1,Sj)=d1j

(4)

式中:Sj表示一個連接點,d1j表示距離值,j=1,2,3,…,n,d(S1,S1)=0。將所有連接點放在兩個集合M={S1}和N={S2,…,Sn}中,并從N中逐一找到點Sk(k=2,3,…,n),使其滿足:

d(S1,Sk)=min{d(S1,Sj)}

(5)

將式(5)搜索得到的Sk放入M中,并更新d(S1,Sj),直至搜索到目標點。于是有:

d(S1,Sk)=min{d(S1,Sj),d(S1,Sk)+dkj}

(6)

利用式(6)反復搜索得到的次優運動路徑如圖3所示。

圖3 機器人運動的次優路徑

2.2 機器人的最優路徑規劃

為了得到移動機器人從起點到終點的最短運動路徑,在獲得次優路徑圖3的基礎上,設計優化性能函數為:

(7)

式中:dl(l=1,2,3,…,7)表示圖3中相鄰的兩個節點間的距離。

在PSO路徑規劃中,對于次優路徑的鏈接線Pi1Pi2(i=1,2,3,…,6),每個粒子的位置xsi(s=1,2,3,…,m)用[0,1]間的比例數表示。因此,粒子的坐標(xPi,yPi)表示為:

(8)

這樣利用式(7)和式(8)便可得到移動機器人的最短運動路徑。

(9)

(10)

式中:t0表示每個粒子達到最優停滯的步數,tg表示全部粒子達到最優停滯的步數,T0和Tg分別表示個體最優和全局最優的閾值。

為了平衡全局和局部的搜索次數,構造權函數w為:

(11)

式中:a表示迭代次數,b表示最大的迭代次數。

利用式(9)～式(11)改進傳統粒子群算法中粒子搜索的速度和位置,得到:

(12)

xsi(t+1)=xsi(t)+vsi(t+1)

(13)

式中:vsi(t)和xsi(t)分別表示粒子的速度和位置,r3、r4表示[0,1]上的隨機數,c1、c2表示加速因子,gs(t)表示粒子個體的位置最優值,gg(t)表示粒子全局的位置最優值。

為了降低區間端點對粒子運動的影響,在迭代中對粒子的運動范圍改進為:

若xsi(t+1)

低年級孩子的書面語言學習剛剛起步，識字量、詞匯量少，書面語言圖式有限，寫話時必然捉襟見肘，即使是初步理解和積累的部分，要達到能運用的水平，也還要有一個過程。所以要實現從隨意的口頭表達到有序的書面表達，是不小的一道坎。因而，教師需要選擇貼近學生生活的文本進行模仿練筆，并且教師要善于將文本掰開了、揉碎了，讓學生感受到文本的“有序”。以下是筆者在教學《我叫黑臉琵鷺》的仿寫時，幫助學生建立有序表達的片段。

xsi(t+1)=Xmin+rand*0.01

(14)

若xsi(t+1)>Xmax,則:

xsi(t+1)=Xmax+rand*0.01

(15)

式中:Xmin和Xmax分別表示粒子s運動位置區間端點的最小值和最大值。

這樣利用上述改進的粒子群算法,移動機器人從起點到終點規劃了最優的運動路徑。

2.3 局部隨機障礙物安全避障

為了使機器人躲避最優路徑上的隨機障礙物,并回到已經規劃的運動路徑向目標點移動,文中提出了動態窗口隨機避障方法,算法具體過程為:

(16)

(17)

步驟3:利用步驟2獲得的安全運動速度,計算機器人一段時間的可行運動軌跡集,并對每條軌跡進行評價,評價函數為:

(18)

這樣機器人利用體感攝像頭感知周圍的障礙物信息,采用動態窗口方法,通過航跡推算和評價函數可以實現全局路徑上隨機障礙物的安全避障。

3 仿真分析

為了驗證文中提出的改進粒子群方法和隨機障礙物避障方法的有效性,與傳統粒子群方法進行了仿真對比。仿真中粒子數n=40,迭代次數i=300,并且運行30次。改進粒子群方法和傳統粒子群方法的路徑規劃結果分別如圖4和圖5所示。

圖4 改進PSO算法規劃的路徑

為了進一步說明改進粒子群方法規劃路徑的優越性,與傳統PSO各指標對比數據如表1所示。

表1 仿真結果對比

由表1可知,成功迭代次數相同的情況下,改進后的PSO算法相比于傳統PSO算法,運行時間減少,粒子的位置和速度不斷進行更新,得到了更短的最優運動路徑。

為了進一步說明機器人避開隨機障礙物并返回全局路徑的動態窗口方法的有效性,與粒子群局部避障方法進行了仿真對比,結果如圖6和圖7所示。

圖6 機器人躲避障礙物(本文方法)

圖6給出了機器人在全局路徑上躲避隨機障礙物的仿真結果,可以看出動態窗口方法有效進行了局部路徑規劃,保證機器人避開隨機障礙物后返回全局路徑。圖7給出了動態窗口方法和粒子群方法局部路徑規劃的仿真對比結果,由圖可知,動態窗口方法可以規劃更短更光滑的局部路徑,最終到達目標點,而粒子群局部路徑規劃方法雖然躲避了隨機障礙物,但躲避障礙物后不能及時返回規劃好的全局最優路徑,不僅增加了計算成本,而且比動態窗口方法避障的運動路徑更長。

4 實驗結果

為了進一步驗證文中提出的隨機障礙物環境下最優路徑規劃方法的有效性,對移動機器人Summit-XL進行了實驗研究。Summit-XL利用攝像頭感知周圍環境信息,從起點到終點規劃全局運動路徑,并對全局路徑上出現的隨機障礙物安全避障。實驗中用紙箱代表運動環境中的靜態障礙物,并在全局路徑上設計隨機障礙物(用圈標出),當傳感器檢測到該障礙物后,機器人利用動態窗口方法局部安全路徑規劃,實驗環境如圖8所示。

圖8 機器人隨機避障實驗環境

實驗中,機器人規劃了全局運動路徑,并成功躲避隨機障礙物,同時返回全局路徑安全運動,實驗結果如圖9所示。

圖9給出了移動機器人在隨機障礙物環境下的路徑規劃結果。由圖可知,機器人從起點出發規劃全局路徑,對全局路徑上出現的隨機障礙物可安全避障,并繼續返回全局路徑向目標點移動。實驗結果表明,文中提出的改進粒子群方法可規劃全局最優運動路徑,再結合動態窗口方法可避開隨機障礙物,并保障機器人安全返回全局路徑,實現了隨機障礙物環境下的移動機器人最優安全運動。

5 結論

研究了隨機障礙物環境下的移動機器人最優路徑規劃問題,通過設計隨機數更新粒子的位置和速度并減小區間端點對粒子運動的影響,提出了改進PSO方法規劃機器人的全局運動路徑;同時對于全局路徑上出現的隨機障礙物,利用DWA方法安全避障,并使機器人返回全局路徑;通過與傳統PSO方法仿真對比,改進的PSO方法運行時間減少并且運動路徑更短,進一步實驗驗證了改進PSO算法融合DWA方法的有效性和優越性,為隨機障礙物環境下機器人安全避障并返回全局最優路徑提供了解決方法。