RRT路徑規划算法

汽車學堂，www.auto-mooc.com

隸屬清華大學蘇州汽車研究院旗下清研車聯

專注汽車新技術人才培養

"

基於快速擴展隨機樹（RRT / rapidly exploring random tree）的路徑規划算法，通過對狀態空間中的採樣點進行碰撞檢測，避免了對空間的建模，能夠有效地解決高維空間和複雜約束的路徑規劃問題。

"

RRT方法的特點是能夠快速有效地搜索高維空間，通過狀態空間的隨機採樣點，把搜索導向空白區域，從而尋找到一條從起始點到目標點的規劃路徑，適合解決多自由度機器人在複雜環境下和動態環境中的路徑規劃。

RRT算法

快速搜索隨機樹（RRT）算法是一種增量式採樣的搜索方法，該方法在應用中不需要任何參數整定，具備良好的使用性能。它利用增量式方法構建搜索樹，以逐漸提高分辨能力，而無須設置任何解析度參數。在極限情況，該搜索樹將稠密的布滿整個空間，此時搜索樹由很多較短曲線或路經構成，以實現充滿整個空間的目的。增量式方法構建的搜索樹其導向取決於稠密採樣序列，當該序列為隨機序列時，該搜索樹稱為快速搜索隨機樹（Rapidly Exploring Random Tree，RRT），而不論該序列為隨機還是確定性序列，都被稱為快速搜索稠密樹（Rapidly Exploring Dense Trees，RDTs），這種規劃方法可處理微分等多種約束。

算法步驟

考慮二維和三維工作空間，環境中包含靜態障礙物。初始化快速隨機搜索樹T，只包括根節點，即初始狀態S。在自由空間中隨機選取一個狀態點，遍歷當前的快速隨機搜索樹T，找到T上距離最近的節點，考慮機器人的動力學約束從控制輸入集中選擇輸入，從狀態開始作用，經過一個控制周期到達新的狀態。滿足與的控制輸入為最佳控制量。將新狀態添加到快速隨機搜索樹T中。按照這樣得到方法不斷產生新狀態，直到到達目標狀態G。完成搜索樹構建後，從目標點開始，逐次找到父節點直到到達初始狀態，即搜索樹的根節點。

隨機樹構建過程

由於在搜索過程中考慮了機器人的動力學約束，因此生成的路徑的可行性很好。但是算法的隨機性導致其只具備概率完備性。

改進算法

LaValle等人的工作奠定了RRT方法的基礎。在採樣策略方面，RRTGoalBiaS方法在控制機器人隨機運動的同時，以一定概率向最終目標運動；RRTGoalZoom方法分別在整個空間和目標點周圍的空間進行採樣；RRTCon方法則通過加大隨機步長改進規劃速度。雙向規劃思想也被採用，衍生出RRTExtExt，RRTExtCon，RRTConCon等多種算法。

基本RRT算法收斂到終點位姿的速度可能比較慢。為了提高算法的效率和性能，需不斷對該算法進行改進。如為了提高搜索效率採用雙向隨機搜索樹(Bi~RRT)，從起始點和目標點並行生成兩棵RRT，直至兩棵樹相遇，算法收斂。由於這個算法相比於原始RRT有更好的收斂性，因此在目前路徑規劃中是很常見的。NikAMelchior提出的粒子RRT算法，考慮了地形的不確定性，保證了在不確定性環境下搜索樹的擴展。

Kuffner和Lavane又提出RRT-connectlv，使得節點的擴展效率大大提高。運動規劃中，距離的定義非常複雜，Pengcheng研究了在RRT生長過程中距離函數不斷學習的算法以降低距離函數對環境的敏感性。考慮到基本RRT規劃器得到的路徑長度一般是最優路徑的1.3~1.5倍，英國的J.desmithl研究了變分法技術使其達到最優。Amna A引入KD樹作為二級數據結構加速查找距離從環境中取出的隨機點最近的葉節點，降低了搜索成本。該算法在動態障礙物、高維狀態空間和存在運動學、動力學等微分約束的環境中的運動規劃已經得到廣泛的應用。