快速探索隨機樹

Question

http://msl.cs.uiuc.edu/rrt/

誰能解釋RRT是如何使用簡單的措辭，很容易理解嗎？ 我閱讀了網站和維基百科的描述。

我想看到的，是一個短期實施RRT或以下的事情徹底解釋的：

爲什麼RRT增長的向外而不是僅僅增長非常密集圍繞中心？ 它與樸素隨機樹有什麼不同？

我們試圖達到的下一個新頂點如何挑選？

我知道有一個運動戰略圖書館，我可以下載，但我更願意理解的想法之前，我深入到代碼，而不是周圍的其他方式。

Answer 1

最簡單的RRT算法非常成功，因爲它很容易實現。事情往往會變得複雜，當你：

• 需要可視化的規劃理念在二維以上
• 不熟悉與規劃相關的術語，以及;
• 在文獻中已經描述了大量的RRT變體。

僞代碼

的基本算法看起來是這樣的：

1. 開始與空搜索樹

2. 添加您的初始位置（配置）到搜索樹

3. 而你的搜索樹還沒有達到目標（你還沒有用完時間）

   3.1。選取一個位置（配置），q_r（採用一些取樣策略）

   3.2。在搜索樹中找到最接近該隨機點的頂點，q_n

   3.3。嘗試在q_n和q_r之間的樹中添加邊（路徑），如果可以鏈接它們而不發生衝突。

雖然這樣的描述是足夠的，在這個空間裏工作了一段時間後，我確實在史蒂芬拉瓦列的著作「規劃算法」喜歡pseudocode of figure 5.16 on RRT/RDT。

樹結構

那棵樹最終覆蓋整個搜索空間（在大多數情況下）的原因是因爲取樣策略的組合，並一直在尋找從最近的點連接樹。這種效應被描述爲減少Voronoi bias。

採樣策略

的地方放置一個頂點，你會嘗試連接到選擇是採樣問題。在簡單的情況下，在搜索維數較低的情況下，統一的隨機佈局（或者統一的隨機佈局偏向於目標）可以充分發揮作用。在高維問題或運動非常複雜（關節具有位置，速度和加速度）或配置難以控制時，RRT的取樣策略仍然是一個開放的研究領域。

庫

的MSL library是，如果你真的被困在實施是一個很好的起點，但它並沒有被積極維護自2003年以來更先進最新的圖書館是Open Motion Planning Library (OMPL)。你還需要一個好的碰撞檢測庫。

規劃術語&諮詢

從一個術語一點，硬一點是要認識到，雖然很多你在（早年）出版物RRT看到圖的是在兩個維度（樹鏈接2d點），這是最簡單的情況下的絕對。

通常，需要用數學方法描述複雜的物理情況。一個很好的例子就是規劃一個帶有n-連桿的機器人手臂。描述這種手臂的末端需要最少的關節角度。描述位置的這組最小參數是配置（或一些出版物狀態）。單個配置經常表示q

能夠實現所有可能的配置（或其子集）的組合構成了一個配置空間（或狀態空間）。這可以像平面上一個點的無界二維平面一樣簡單，或者其他參數範圍的複雜組合非常複雜。