基于采樣的運動規劃算法-RRT（Rapidly-exploring Random Trees）

RRT：一種通過隨機構建Space Filling Tree實現對非凸高維空間快速搜索的算法。該算法可以很容易的處理包含障礙物和差分運動約束的場景，被廣泛的應用在各種機器人的運動規劃場景中

• Basic RRT算法

原始的RRT算法中將搜索的起點位置作為根節點，然后通過隨機采樣增加葉子節點的方式，生成一個隨機擴展樹，當隨機樹的葉子節點進入目標區域，就得到了從起點位置到目標位置的路徑

偽代碼如下：

上述偽代碼中，M是地圖環境，是起始位置，是目標位置。路徑空間搜索的過程從起點開始，先隨機撒點；然后查找距離最近的節點；然后沿著到方向前進stepsize的距離得到；CollisionFree(M, )方法檢測Edge(,)是否與地圖環境中的障礙物有碰撞，如果沒有碰撞，則將成功完成一次空間搜索拓展。重復上述過程，直至達到目標位置。

RRT算法拓展過程

• 基于概率的RRT算法

為了加快隨機樹收斂到目標位置的速度，基于概率的RRT算法在隨機樹擴展的步驟中引入一個概率P，根據概率p的值來選擇樹的生長方向是隨機生長（xrand）還是朝向目標位置（xgoal）生長，引入像目標生長的機制可以加速路徑搜索的收斂速度。

偽代碼如下：

• RRT Connect算法

RRT Connect算法從初始狀態點和目標狀態點同時擴展隨機樹從而實現對狀態空間的快速搜索

?

• RRT*算法

RRT*算法的目標在于解決RRT算法難以求解最優的可行路徑的問題，它在路徑查找的過程中持續的優化路徑，隨著迭代次數和采樣點的增加，得到的路徑越來越優化。迭代的時間越久，就越可以得到相對滿意的規劃路徑。

偽代碼如下：

RRT*算法和RRT算法的區別主要在于兩點：

rewrite的過程。即為重新選擇父節點的過程

RRT*在找到距離xrand最近的節點xnearest并通過CollisionFree檢測之后，并不立即將Edge（xnearest,xrand）加入擴展樹中，而是以xrand為中心，r為半徑，找到所有潛在的父節點集合，并與xnearest父節點的Cost對比，看是否存在更優Cost的父節點。

?

連接xrand和xnearest

以xrand為中心，ri為半徑，在樹上搜索節點

找出潛在的父節點集合xpotential-parent，其目的是要更新xrand，看看有沒有比它更好的父節點

從某一個潛在父節點開始考慮，計算出xparent（即為xnearest）作為父節點時的代價,子節點為xchild（即為xrand）

先不進行碰撞檢測，將潛在父節點與子節點連接起來，計算該條路徑的代價

如果代價小于原路徑，則進行碰撞檢測，若代價大于原路徑，則考慮其他潛在父節點

代價小于原路徑且碰撞檢測通過，則在樹中將之前的邊刪掉，將樹中新的邊添加進去，即連接滿足要求的潛在父節點和子節點之間的邊，將潛在父節點（xpotential-parent）改為父節點（xparent），遍歷所有的父節點，得到更新以后的樹

2.隨機樹重布線的過程

?

總結

以上是生活随笔為你收集整理的RRT算法及其部分改进算法介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。