快速遍歷隨機樹

Ran Con o-dyn

快速遍歷隨機樹(Rapidly-exploring Random Tree，RRT)是一種樹形數據存儲結構和算法，通過遞增的方法建立，並快速減小隨機選擇點同樹的距離，用於有效地搜尋非凸的(Non Convex)高維度的空間，特別適用於包含障礙物和非完整(Non-Holonomic)系統或反向動力學(Kino-dynamic)微分約束條件下的動作規劃。
RRT 的特點是算法建構簡單，並且可以快速遍歷空間的未探索區域，而通過手動設定找到實現這種效果的函式卻是很難的。同時RRT 可以在基本算法基礎上，對空間的搜尋加入帶有輸入參數的控制函式，使算法可以適用於不同約束條件下的路徑搜尋。