RRT 算法原理以及过程演示
RRT 適用于涉及非完整約束場合下的路徑規劃問題。
RRT 算法為一種遞增式的構造方法，在構造過程中，算法不斷在搜索空間中隨機生成狀態點，如果該點位于無碰撞位置，則尋找搜索樹中離該節點最近的結點為基準結點，由基準結點出發以一定步長朝著該隨機結點進行延伸，延伸線的終點所在的位置被當做有效結點加入搜索樹中。這個搜索樹的生長過程一直持續，直到目標結點與搜索樹的距離在一定范圍以內時終止。隨后搜索算法在搜索樹中尋找一條連接起點到終點的最短路徑。
下面用一個示例來說明RRT算法的過程。
初始化一個環境，包括地圖，起點，終點。如下圖所示,黑色物體為障礙物，藍色飛機位于起點位置，紅色五角星為目標終點位置。
從環境中隨機采樣狀態點，如下圖所示，采樣點為 Xrand。
從所構建的樹中尋找距離采樣點 Xrand最近的結點 Xnear。現在樹中只有起點一個結點，所有最近的結點就是起點。
開始樹的生長過程。首先連接 Xnear 和 Xrand連接起來，這個連接線的方向就是樹生長的方向。設置一個步長 Stepsize作為樹一次生長的步長，在樹生長的這個方向上生長一個步長，然后就會在生長的末端會產生一個新的結點 Xnew。
判斷從 Xnear 到 Xrand是否穿過障礙物，如果穿過，則放棄該新的結點，如果沒有，則將 Xnew 結點加入到樹中。
從步驟 2 開始再循環執行，從環境中隨機采樣狀態點。
從樹中尋找距離 Xrand 結點最近的結點為 Xnew。
開始書的生長過程。首在 Xnear 和 Xrand的連接方向上生長一個步長到新的一個結點 Xnew。
判斷從 Xnear 到 Xrand是否穿過障礙物，如果穿過，則放棄該新的結點，如果沒有，則將 Xnew 結點加入到樹中。如上圖所示，穿過了障礙物，所以放棄該新的結點。
重復上述樹的生長過程，直到樹新生成的結點到目標點的距離小于一個步長，則終止樹的生長。直接將該新結點與目標點相連。
整個過程圖如下（中間過程有些跳動，不必再在意）：
算法流程圖總結如下：
如果對您有幫助，記得在下方點贊喲！也歡迎在評論區留言討論！
總結
以上是生活随笔為你收集整理的RRT 算法原理以及过程演示的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 新版macbook，PPT导出PDF复制
- 下一篇： oracle 查询有字母,oracle中