基于改進RRT算法的移動機器人路徑規劃研究

楊軍

(湖南交通工程學院,湖南 衡陽 421009)

0 引言

移動機器人是集環境感知、動態決策規劃、運動行為控制等復雜功能于一體的機械裝備,在民用和軍用領域均具有廣泛應用前景。路徑規劃是開發多功能移動機器人裝備的核心技術,算法的目標是在機器人工作的復雜環境中為其規劃出一條無碰撞的最短路徑,這是學術界的廣泛關注點[1]。楊恒等[2]對傳統A*算法存在的路徑規劃效率低、拐點多等問題提出了聯合改進A*算法和動態窗口法(Dynamic Window Approach,DWA)的路徑規劃方法,仿真試驗指出該方法能夠確保移動機器人實時避障,確保規劃路徑的安全性。楊博等[3]對傳統遺傳算法所規劃的路徑不夠平滑、易陷入局部最優的問題,設計了新的適應度函數,同時采用混合選擇策略改善算法,避免了傳統算法存在的問題,通過與傳統遺傳算法的對比,所規劃的路徑在性能上更佳。邱添等[4]針對概率路線圖法(Probabilistic Roadmap Method,PRM)進行路徑規劃存在的運行效率低、狹窄通道采樣困難等問題,提出了柵格概率路徑圖法,仿真結果表明該方法對路徑規劃的效率高,提升了路徑規劃的質量。莫海寧等[5]分析了傳統煙花算法的缺陷,將競爭學習和煙花算法相結合對機器人路徑實施規劃,得到的規劃路徑具有更高平滑度,能夠更好地適應機器人的作業環境?？焖贁U展隨機樹(Rapidly-Exploring Random Trees,RRT)是基于概率采樣的運動規劃算法,其具有采樣節點隨機、增量式增長、搜索能力強等優點,是有效解決運動機器人路徑規劃的新方法[6]。實踐表明,由于RRT算法缺乏路徑導向性,使得實際路徑規劃效率不高、轉折點多且距離長。在深入研究的基礎上對RRT算法進行改進,提出了待擴展點的選擇策略和擴展方向,降低了擴展點選擇上的盲目性,同時提出了路徑冗余點消除算法和路徑平滑處理算法,使得規劃的路徑距離短、平順性好,路徑規劃效率大大提升。最后將其應用于移動機器人路徑規劃仿真試驗和實物試驗中,驗證算法的有效性。

1 RRT算法及改進

1.1 RRT算法

RRT算法采用遞增式構造,由所搜索的空間隨機抽取樣本產生。在實際產生節點時傾向于未探測區域,不妨設qstart是路徑規劃的起始點,qrand是路徑規劃空間的隨機采樣點,qnear是最近鄰點,qnew是擴展后生成的新節點,L是擴展的步長,隨機樹擴展示意如圖1所示[7]。

圖1 隨機樹擴展示意圖

在圖1中,路徑規劃的起始點qstart為根節點,在擴展樹中尋找和隨機采樣點距離最近的點作為qnear。在隨機采樣點和最近鄰點的連線上按照拓展步長來拓展新的節點。連接最近點和新節點,如果連線遇到障礙物,那么該條路徑是不通的,舍棄擴展的新節點;如果連線沒有遇到障礙物,那么該條路徑是可行的,將該節點添加到隨機樹中,直到尋找到路徑規劃的目標點為止。

很明顯,采樣點的選擇直接影響到算法的效率。尤其是在移動機器人的工作空間比較狹窄時,RRT進行路徑規劃的效率就會大大降低,同時由于在路徑規劃的過程中缺乏導向性,這也使得算法對最佳路徑的搜索時間比較長,所規劃的路徑距離也更長。

1.2 RRT算法改進

1.2.1 待擴展節點選擇改進

RRT中待擴展節點為隨機樹中和采樣節點距離最近的點,而采樣節點是隨機的,這也使得擴展節點是隨機的。在極端情況下,當擴展隨機樹接近目標點時,因擴展節點是隨機的,從而使得隨機樹向四周等概率擴展,產生大量無效的節點?；贏*算法的思想,對待擴展節點的選擇進行改進[8],定義隨機樹中任一節點qi和采樣點qrand的距離為H(i),和目標點的距離為G(i),那么

F(i)=H(i)+G(i)。

(1)

將滿足F(i)最小的節點作為擴展節點,記為qnear。很明顯,采用這種方式來選擇待擴展節點能夠在很大程度上降低傳統RRT算法在待擴展節點選擇上的盲目性,使得路徑規劃的效率大大提升。

1.2.2 擴展方向選擇

傳統RRT的擴展方向為隨機采樣點qrand所在的位置方向,很明顯擴展方向具有很大的隨機性?；谌斯萘龅乃枷?對節點的擴展方向進行改進[9]。由于路徑規劃的目標是尋找一條從起點到目標點的最佳路線,因此當待擴展的節點確定之后,優先考慮目標方向。如果目標方向拓展成功,那么直接生成新的節點;如果目標方向存在障礙物,那么以隨機采樣點方向作為拓展方向生成新的節點,同時對失敗的待擴展節點進行標記。再次選擇失敗節點作為拓展節點時,直接按照隨機采樣點方向進行拓展。圖2為目標方向存在障礙物示意圖。

圖2 目標方向存在障礙物示意圖

1.2.3 冗余點消除

由于RRT算法在選擇擴展點時的隨機性導致所規劃的路徑中存在諸多的冗余點,這些冗余點使得移動機器人在實際運動時的波動比較大。如果兩個不相鄰的路徑之間連接沒有遇到障礙物,那么就可以將兩個路徑之間的點消除。圖3為路徑冗余點消除示意圖。

圖3 路徑冗余點消除示意圖

路徑冗余點消除就是從起始點開始逐個進行碰撞檢測,按照圖3的方式消除路徑上的冗余點。路徑冗余點的消除不僅使得所規劃的路徑長度大大縮短,同時也使得所規劃的路徑更加平順。不妨設初始路徑點序列為{q1,q2,…,qn},其中q1為起始點,qn為目標點。構建路徑冗余點消除之后的路徑點序列為φ,初始狀態φ為空集。

1)將起始點q1添加到序列集合φ中,同時令j=1,i=n;

2)檢測qj和qi之間是否有障礙物,如果有障礙物,那么繼續下一步,如果沒有障礙物,那么直接進入步驟4;

3)如果i=j+1,那么j=j+1,i=n,轉入步驟2,反之,i=i-1,轉入步驟2;

4)將點qi添加到序列集合φ中,令j=i,i=n;

5)如果j=n,那么路徑上的所有冗余點被消除,反之,繼續轉入步驟2。

1.2.4 路徑平滑處理

消除規劃路徑冗余點之后,其軌跡上依舊會存在比較多的拐點,這使得移動機器人在實際的轉向時存在角度過大的問題。采用B樣條曲線對路徑進行平滑處理,從而使得所規劃的路徑更加平滑[10]。三次樣條曲線的數學表達式為

(2)

式中Vi+j為基函數控制點,Gj,3(t)為基函數,其數學表達式為

(3)

設經過冗余點消除后的節點序列集合為{φ1,φ2,…,φm},其中φ1為起始點,φm為目標點。各點為基函數的控制點,可以得到路徑上點φi和φi+3之間的軌跡,其數學表達式為

(4)

2 仿真分析

為了更好地驗證改進RRT算法在機器人路徑規劃方面的優良性能,在MATLAB中構建簡單地圖環境和復雜地圖環境,地圖的大小為800×800,移動機器人的初始點坐標為(100,700),目標點坐標為(700,100),具體如圖4所示。

圖4 構造的簡單和復雜地圖環境

分別采用傳統RRT算法和改進RRT算法對簡單地圖環境進行路徑規劃,結果如圖5所示。

圖5 路徑規劃結果對比(簡單地圖環境)

由圖5可知,相對于RRT算法,改進RRT算法隨機樹路徑擴展分支明顯減少,這使得算法的運行效率大大提升。在距離障礙物比較遠的區域,改進RRT算法能夠更加快速地向目標區域生長,加快了路徑規劃的速度。另外,改進RRT采用B樣條函數進行路徑平滑,很明顯改進RRT算法所規劃的路徑沒有了比較明顯的拐點,而在RRT算法所規劃的路徑中存在比較多的明顯拐點。

分別采用傳統RRT算法和改進RRT算法對復雜地圖環境進行路徑規劃,結果如圖6所示。

圖6 路徑規劃結果對比(復雜地圖環境)

對比圖5和圖6可知,不論是簡單地圖環境還是復雜地圖環境,改進RRT算法隨機樹路徑擴展分支明顯減少,同時所規劃的路徑也更加平滑。

從算法規劃路徑的用時、擴展節點數、規劃路徑長度3個角度進行對比,對比結果見表1。

表1 算法路徑規劃性能對比

由表1可知,改進RRT不論是從用時、擴展節點數還是規劃路徑長度均明顯優于傳統RRT。相對于簡單地圖,改進RRT相對于RRT在移動機器人路徑規劃上表現出了更加優良的性能。移動機器人實際作業環境比較復雜,障礙物形狀多種多樣,傳統RRT所規劃的路徑平順性比較差,移動機器人在實際的移動過程中受慣性的影響,其往往無法在拐點處沿著路徑移動,很容易和鄰近的障礙物發生碰撞。改進RRT算法所規劃的路徑更加平順,避免了移動機器人在實際的移動過程中走曲折的路線,降低了在移動過程中與周邊障礙物發生碰撞的風險。

3 試驗驗證

為了驗證改進RRT算法在真實移動機器人上的可行性,選擇四輪獨立驅動的移動機器人作為試驗對象,其外形如圖7所示。

圖7 試驗所用移動機器人

在移動機器人上安裝了激光雷達、編碼器和攝像頭等,控制系統由試驗臺上的電腦和NPX控制板組成,在電腦上運行機器人操作系統,其負責機器人路徑規劃。NPX控制板通過Wi-Fi與電腦之間進行通信,獲取電腦發送的路徑規劃信息。移動機器人在運動的過程中通過激光雷達、編碼器和攝像頭等設備來獲取外界的信息。將改進RRT算法應用于圖7所示的機器人中,對不同起始點下的移動路徑進行規劃,結果如圖8所示。

圖8 移動機器人路徑規劃結果

由圖8可知,不論是移動機器人最終的目的地在何處,改進RRT算法均可以規劃出最佳路徑。

4 結論

路徑規劃是移動機器人開發的核心技術之一,針對傳統RRT算法存在的路徑規劃效率低、規劃路徑拐點多的問題,對RRT進行改進。通過引入A*算法和人工勢力場思想來選擇待擴展節點和擴展方向,同時對所規劃的路徑進行冗余點消除和平滑處理。將改進的RRT算法應用于簡單地圖環境和復雜地圖環境的仿真中,驗證了改進RRT算法在路徑規劃上的有效性,同時通過實物試驗,對改進RRT算法在真實移動機器人上的可行性進行了驗證。改進RRT算法對移動機器人的開發具有一定的參考價值。