汽車
學堂
，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樹作為二級資料結構加速查詢距離從環境中取出的隨機點最近的葉節點，降低了搜尋成本。該演算法在動態障礙物、高維狀態空間和存在運動學、動力學等微分約束的環境中的運動規劃已經得到廣泛的應用。
