改進(jìn)RRT機(jī)器人路徑規(guī)劃技術(shù)研究

黃恒一

（三亞學(xué)院 理工學(xué)院，海南 三亞 572022）

0 引言

隨著移動(dòng)機(jī)器人技術(shù)在各個(gè)領(lǐng)域的廣泛應(yīng)用，科研人員對(duì)路徑規(guī)劃問(wèn)題的研究也更加深入透徹。至今為止，盡管RRT 路徑規(guī)劃算法已經(jīng)有了明顯的進(jìn)步與改善，但是其收斂速度慢、隨機(jī)性太強(qiáng)、穩(wěn)定性差等問(wèn)題并沒(méi)有得到有效改善。為了實(shí)現(xiàn)移動(dòng)機(jī)器人精確的路徑規(guī)劃和自主導(dǎo)航，進(jìn)一步優(yōu)化改進(jìn)RRT 算法至關(guān)重要。論文對(duì)傳統(tǒng)RRT 算法提出了多種改進(jìn)措施，并通過(guò)MATLAB 軟件在二維、三維環(huán)境中進(jìn)行模擬、論證、驗(yàn)證測(cè)試[1]。1 RRT 算法簡(jiǎn)介

RRT 算法是以起始點(diǎn)為隨機(jī)樹的根節(jié)點(diǎn)，通過(guò)在狀態(tài)空間中以增量采樣方式獲取隨機(jī)采樣點(diǎn)，并使樹向著采樣點(diǎn)位置擴(kuò)展生長(zhǎng)出與危險(xiǎn)區(qū)域無(wú)碰撞的樹節(jié)點(diǎn)，直到達(dá)到目標(biāo)點(diǎn)[2]。RRT 樹擴(kuò)展過(guò)程如圖1所示。

圖1 RRT 算法擴(kuò)展示意圖

2 RRT 算法研究

2.1 RRT 算法分析

RRT 算法具有概率完備性，當(dāng)節(jié)點(diǎn)數(shù)量趨于無(wú)窮大時(shí)，找到存在的可行路徑的概率無(wú)限接近1[3]。但由于路徑搜索是通過(guò)在空間中隨機(jī)采樣進(jìn)行的，規(guī)劃出的路徑隨機(jī)性大，且不能保證所得路徑是最優(yōu)路徑或次最優(yōu)路徑。當(dāng)空間較大、障礙物較多時(shí)，運(yùn)算量增加，導(dǎo)致搜索時(shí)間較長(zhǎng)[4]。

2.2 RRT 二維環(huán)境構(gòu)建

通過(guò)RRT 算法構(gòu)建一個(gè)面積為500 mm×500 mm 的圖像，起始點(diǎn)位置為source，目標(biāo)點(diǎn)為goal，每步步長(zhǎng)為stepsize，闕值為disTh。圖2 為在60%概率的隨機(jī)采點(diǎn)下的未改進(jìn)RRT 路徑圖像，左上角為路徑起點(diǎn)，右下角為路徑終點(diǎn)，黑色區(qū)域?yàn)檎系K物，細(xì)線為規(guī)劃路徑。圖3 為路徑探索過(guò)程。由圖2、圖3 發(fā)現(xiàn)，傳統(tǒng)RRT 算法規(guī)劃出的路徑具有隨機(jī)性強(qiáng)、穩(wěn)定性差、無(wú)導(dǎo)向性等特點(diǎn)。

圖2 未改進(jìn)RRT 路徑

圖3 RRT 路徑探索

2.3 RRT 算法二維改進(jìn)

傳統(tǒng)RRT 算法在整個(gè)空間隨機(jī)采點(diǎn)，導(dǎo)致RRT 路徑隨機(jī)樹在不合理位置采點(diǎn)，碰撞檢測(cè)機(jī)制不完善，路徑不滿足最大轉(zhuǎn)向角約束和曲率連續(xù)約束，隨機(jī)樹遍布整個(gè)空間，搜索到目標(biāo)附近卻遲遲不能結(jié)束搜索，路徑每次規(guī)劃結(jié)果不一樣且均非最優(yōu)。針對(duì)RRT 上述問(wèn)題，論文采用擴(kuò)大目標(biāo)節(jié)點(diǎn)域和偏向目標(biāo)采樣的啟發(fā)式搜索機(jī)制拉扯隨機(jī)樹向目標(biāo)點(diǎn)生長(zhǎng)，加快搜索速度，采用修剪采樣空間、剪枝函數(shù)及B 樣條平滑曲線來(lái)滿足路徑約束條件和路徑質(zhì)量[5]。

2.3.1 RRT 二維改進(jìn)措施

改進(jìn)措施RRT 原始圖、剪枝圖、B 樣條平滑曲線、改進(jìn)結(jié)果數(shù)據(jù)分別如圖4～圖7所示。

由圖4～圖7 可知，原始RRT 路徑探索空間較大，采用減枝處理、RRT 路徑舍棄了多余的節(jié)點(diǎn)，采樣點(diǎn)數(shù)減少。采用了B 樣條平滑路徑后，RRT 路徑得到平滑，路徑距離得到縮短。

圖4 RRT 原始路徑

圖5 RRT 剪枝路徑

圖6 B 樣條平滑路徑

圖7 RRT 改進(jìn)效果數(shù)據(jù)

2.3.2 RRT 二維改進(jìn)分析

由前文可知，RRT 路徑規(guī)劃算法在目標(biāo)區(qū)域點(diǎn)外的采樣范圍探索了很多不必要的節(jié)點(diǎn)，這樣的探索策略導(dǎo)致隨機(jī)樹盲目擴(kuò)展，使得搜索速度變慢。通過(guò)設(shè)置RRT 算法兩類不同的路徑，根據(jù)障礙物之間距離判斷步長(zhǎng)，檢測(cè)判斷標(biāo)準(zhǔn)；減去多余的路徑分枝，舍棄多余的路徑探索節(jié)點(diǎn)，縮短路徑。由圖6 可知，經(jīng)過(guò)平滑處理后的路徑?jīng)]有折點(diǎn)、變化緩慢。經(jīng)過(guò)上述改進(jìn)措施后，仿真結(jié)果顯示路徑更符合機(jī)器人運(yùn)行路徑測(cè)試要求[6]。

2.4 雙向RRT 算法

雙向RRT 算法具有雙向探索引導(dǎo)的策略，可以加快探索速度，減少空白區(qū)域的探索，從而節(jié)約路徑規(guī)劃時(shí)間。雙向RRT 算法的其中一棵樹以另一棵樹最后生成的節(jié)點(diǎn)作為新的拓展方向。如果拓展成功則繼續(xù)往該方向拓展，直到不能拓展為止。采用持續(xù)拓展直到不能拓展的算法可能會(huì)出現(xiàn)兩棵樹的節(jié)點(diǎn)數(shù)不平衡的狀態(tài)。因此當(dāng)一棵樹拓展完時(shí)，到下一次拓展前進(jìn)行判斷，哪棵樹的節(jié)點(diǎn)數(shù)較小就拓展哪棵樹，從而保證兩棵樹的節(jié)點(diǎn)數(shù)盡量相等。雙向RRT 算法改進(jìn)RRT 算法空間探索的盲目性，使得節(jié)點(diǎn)拓展具有記憶性[7]。

雙向RRT 算法仿真結(jié)果如圖8 和圖9所示。對(duì)比圖8、圖9 可知，通過(guò)改進(jìn)最終終點(diǎn)判斷條件，使得改進(jìn)后的雙向RRT 算法路徑距離得到優(yōu)化，路徑變得更短。

圖8 雙向RRT 算法路徑

圖9 改進(jìn)雙向RRT 算法路徑

3 RRT 三維路徑仿真

為了使改進(jìn)算法的實(shí)用性更加貼近現(xiàn)實(shí)生活，論文在三維環(huán)境下對(duì)引入優(yōu)化策略后的RRT 算法進(jìn)行MATLAB 仿真研究[8]。

3.1 RRT 三維環(huán)境建圖

將改進(jìn)RRT 算法應(yīng)用到三維空間中，只需要將二維空間中進(jìn)行偏向采樣的啟發(fā)式函數(shù)擴(kuò)展到三維空間中進(jìn)行偏向采樣點(diǎn)的位置坐標(biāo)計(jì)算。在一個(gè)充滿立體圖形的空間里，對(duì)給出的任意一些點(diǎn)進(jìn)行路徑規(guī)劃，起點(diǎn)用source 表示，目標(biāo)點(diǎn)用goal 表示，然后分別對(duì)它們用RRT 三位雙向算法進(jìn)行填充，在此基礎(chǔ)上還要進(jìn)行碰撞檢測(cè)，就可以避免對(duì)實(shí)際空間進(jìn)行建模，能夠很好地解決高維空間與復(fù)雜約束問(wèn)題，進(jìn)而得到路徑[9]。

3.2 仿真效果

圖10 和圖11 都是由兩個(gè)圓柱體與四個(gè)球體的障礙物所組成的空間，起點(diǎn)與終點(diǎn)不變，圖11 的路徑比圖10 的路徑要短一些。此外，由實(shí)驗(yàn)結(jié)果可以看出，改進(jìn) RRT 算法三維空間中規(guī)劃出的避障路徑不夠平滑，現(xiàn)實(shí)世界中機(jī)器人很難跟蹤這樣曲折陡峭的路徑。RRT 系列算法是通過(guò)在空間中增量采樣來(lái)實(shí)現(xiàn)路徑點(diǎn)的搜索與路徑擴(kuò)展的，在三維空間中這種搜索方式會(huì)導(dǎo)致路徑點(diǎn)的橫縱高三個(gè)坐標(biāo)位置變化得比較劇烈。后續(xù)研究中將嘗試加入角度約束解決此問(wèn)題。

圖10 RRT 三維雙向算法改進(jìn)前效果

圖11 RRT 雙向算法改進(jìn)后效果

4 創(chuàng)新點(diǎn)

在傳統(tǒng)RRT 單向二維算法的基礎(chǔ)上提出了修剪采樣空間、擴(kuò)大目標(biāo)節(jié)點(diǎn)域的方法來(lái)加快搜索速度，采用剪枝處理方法去掉多余的轉(zhuǎn)折點(diǎn)使得路徑滿足最大轉(zhuǎn)向角約束；采用B 樣條曲線平滑處理后路徑質(zhì)量較好，路徑變化平緩?；诓蓸铀惴ǖ碾p向搜索，其主要優(yōu)勢(shì)在于利用漸近最優(yōu)性來(lái)克服采樣的盲目性。RRT 雙向三維算法增加了貪心算法后，在起點(diǎn)、終點(diǎn)與障礙物不變的條件下，路徑比原本的路徑更加平滑、更短[10]。

5 結(jié)語(yǔ)

針對(duì)RRT 算法機(jī)器人路徑規(guī)劃應(yīng)用中存在搜索效率低、無(wú)目標(biāo)性和路徑不一定最優(yōu)等缺點(diǎn)，提出了修剪采樣空間、剪枝處理方法、B 樣條曲線平滑、雙向搜索等改進(jìn)措施，并通過(guò)MATLAB 軟件在二維、三維機(jī)器人運(yùn)行環(huán)境下進(jìn)行多次仿真驗(yàn)證測(cè)試實(shí)驗(yàn)。通過(guò)與基本RRT 算法進(jìn)行實(shí)驗(yàn)對(duì)比，結(jié)果表明算法改進(jìn)措施是可行有效的。