基于改進RRT算法的路徑規劃研究*

韓金利

(山西機電職業技術學院 數控工程系，山西 長治 046011)

0 引言

路徑規劃是機器人智能化研究的重要方向之一,多年來,學者們對路徑規劃算法進行了很多探索。其中RRT(Rapidly Exploring Random Tree,快速擴展隨機樹)算法具有搜索能力強、算法簡單等特點,但是它也有冗余多等缺點,因此許多學者對RRT算法進行了優化。欒添添等[1]提出了以生成的新節點與終點的距離來判斷自己所處的采樣區域,但距離公式計算效率較低。陳娟等[2]提出了候選點集策略,點集中的數據隨機性大。趙文龍等[3]提出了在均勻采樣得到的隨機點與目標點的連線上隨機取一個點作為新的隨機點進行樹的擴展,但沒有考慮到在障礙物附近新節點的生成問題。張恩東[4]提出了一次采樣多次擴展的方式,沒有對采樣點重復利用。董璐等[5]提出了歷史路徑緩存池概念,沒有對歷史路徑中的節點進行篩選。

針對以上問題,本文提出了基于改進RRT算法的路徑規劃。以地圖長、寬進行分區,利用新節點的坐標值判斷處于何種分區,并將首先進入最新區域的節點作為根節點,向著目標擴展,使得算法隨機性減弱,轉折點更少。

1 基本RRT算法

RRT算法的基本思想是:隨機點決定節點的擴展方向,擴展步長決定擴展速度。對問題定義如下:

假設C為探索空間,在探索空間中有自由空間qfree與障礙物空間qobs,并且qobs?C,qfree?C;探索空間中的起始點為qstart,qstart∈qfree,目標點為qgoal,qgoal∈qfree,qrand為隨機點。隨機點qrand初始路徑生長過程如圖1所示。

圖1 qrand初始路徑生長過程

2 改進RRT算法

2.1 節點擴展策略

這里采用進五取二的策略,當隨機數大于閾值時,節點擴展步長數為1,當小于閾值時,節點擴展步長數為5;在擴展過程中,若遇到障礙物,則停止擴展,否則則擴展5步。這里采用前進5步,只將其中的兩個節點加入隨機樹中,這里取第2步節點和第5步節點加入隨機樹中。

2.2 最近點分區搜索策略

根據地圖大小及目標點與開始點之間的距離劃分隨機樹擴展區域,只要一個新節點首次進入下一區域,就以進入該區域的最新點為根節點,并且在區域范圍內生成隨機樹,將最近點搜索限制在區域范圍內,縮短搜索時間,一定程度上加快了可行路徑的生成。

2.3 隨機點分區采樣

根據起點與終點位置,將地圖分為3個區域,用虛線表示分界線,這里將一區、二區隨機點采樣區域指定為整個地圖,三區采樣空間指定為二區和三區,既保證了隨機樹一定程度上可反向擴展,又保證了隨機點的選取使得隨機樹可向目標點擴展,最大程度上避免隨機樹剛剛進入新的區域時容易陷入局部震蕩。隨機采樣分區擴展示意圖如圖2所示。

圖2 隨機采樣分區擴展示意圖

2.4 節點試采樣回退策略

在分區采樣的過程中,提出了一種在擴展樹生長初期有限進入已探索區域的有限回退策略,即節點試采樣回退策略。設置一個標志位,當節點采樣生成新節點未通過碰撞檢測1次則加1,當采樣點生成新節點通過檢測,且新節點又在重復采樣分區則標志位減1,直到標志位數值達到閾值K,則允許重復采樣分區新生成的節點加入到隨機樹。

2.5 逆向剪枝與路徑平滑

改進RRT算法能夠迅速找到初始路徑,但生成了很多冗余節點,這里對初始路徑的節點集合進行剪枝操作,逆向剪枝示意圖如圖3所示。圖3中,黑色方塊為障礙物,實線為原始路徑,點劃線為碰撞檢測連線,虛線表示中間省略有很多節點。

圖3 逆向剪枝示意圖

路徑平滑采用二次貝塞爾曲線進行擬合處理。在路徑中選擇連續的3個節點qi-1,qi,qi+1,中間節點與前后兩個節點連線上選擇固定距離smooth_dis,并保證該距離不會超過兩條邊的中點。貝塞爾曲線擬合示意圖如圖4所示。其中,p0、p1、p2為擬合曲線上的3個點。

圖4 貝塞爾曲線擬合示意圖

3 實驗與分析

為了驗證本文改進算法的優良性能,將本文算法與基本RRT算法和偏置RRT算法進行對比實驗。由于RRT具有隨機性,這里設置實驗次數為20次,各種算法指標求平均值,為保證算法驗證的客觀性。三種算法原始路徑如圖5所示,三種算法實驗結果如表1所示,本文算法路徑優化效果及成本變化如圖6所示。

表1 三種算法實驗結果

圖5 三種算法原始路徑

圖6 本文算法路徑優化效果及成本變化

從表1可以看出:三種算法的路徑成本相差不大,在采樣點數、運行時間、路徑節點數等指標方面本文算法優勢十分明顯;本文算法相較于基本RRT算法采樣點數減少了67.65%,相較于偏置RRT算法采樣點數減少了51.19%;本文算法運行時間相較于基本RRT算法減少了60.34%,相較于偏置RRT算法減少了36.81%;本文算法路徑節點數相較于基本RRT算法減少了68.55%,相較于偏置RRT算法減少了52.08%。

由圖6可知:原始路徑平均長度為1 875.13 m,逆向尋優后路徑平均長度為1 424.85 m,平滑后路徑平均長度為1 398.48 m,最終路徑平均長度減少25.42%。由此看出,經過擬合處理后,擬合路徑更加適合機器人運行。

4 總結

本文提出了分區采樣RRT算法,對探索空間進行分區,僅在所在區域內尋找最近點,提高了最近點的搜索效率;以進入下一區域的首個節點為根節點,開始在區域中進行探索,最大程度地避免在已采樣區域進行重復采樣;最終路徑由各個分區的搜索樹拼接而成。本文算法尋找可行路徑速度更快、節點更少、效率更高、導向性更強。