快速探索隨機樹

RRT動畫，從0疊代到10000

快速探索隨機樹（英文：Rapidly-exploring random tree，RRT）係一種演算法，旨意透過隨機構建空間填充樹來有效噉檢索啲非凸、高維空間嘅。呢種樹係根據啲樣本、啲從檢索空間當中隨機抽取嘅，嚟逐步構建到嘅；樹本身有向啲大幅未檢索區域生嘅固有傾向。

RRT 係由Steven M. LaValle同James J. Kuffner Jr. 開發嘅。啲演算法輕鬆噉處理得到啲問題場景係有障礙物同有微分約束（differential constraints，意指非完整同埋涉及運動動力學）嘅，並已廣泛噉用於自主機械人運動規劃。

RRT 可以睇作一種技術，生成啲開環（open-loop）路軌畀具有狀態約束嘅非線性系統嘅。RRT 亦都可以着認為係一種蒙地卡羅方法，喺一幅構形空間（configuration space）當中攞來幫檢索行爲偏笡（bias）到一隻圖形嘅最大 Voronoi 區域。一啲RRT 變體甚至可以着認為係啲隨機分形（stochastic fractals）。

歷史

為唨做路徑規劃畀機械人㘢gwaang6過啲障礙物，好早（20世紀60年代）電腦科學領域就發展唨A*演算法，個演算法係喺圖入便搜索啲最短路徑從 A 到 B 嘅。RRT 擴展A*算法係喺兩方面：首先，使用Voronoi 偏笡捉問題空間劃分成均勻區域；其次，圖形可以喺任何隨機點透過新節點進行擴展。Voronoi 偏笡主要攞來解決幾何路徑嘅規劃問題。目標係䠋展（expand）個圖形到啲空間裏便未探得咁好嘅埞。噉樣即做得到規劃到啲路徑，啲又縮得到好幼蜎得過啲細通路、又可以䠋開嘅，用喺譬如幫啲複雜嘅迷宮做規劃陣時。噉嘅話，就需要到喺任意地方都添加得到啲新節點嘅能力。

RRT 着認為係喺啲迷宮裏頭規劃路徑、並考慮埋啲障礙物嘅最有效方法之一。

除開原始嘅RRT演算法之外，仲有好多擴展方法着開發到，其中RRTConnect 最出名。RRT 雖然好多時效率好高，但喺噻啲情況下，佢個性能甚至仲勩過用經典嘅迪卡斯特拉演算法。

描述

生長過程

RRT 透過使用來自個檢索空間（search space）嘅隨機樣本，來生成以起始配置為根嘅樹。喺繪製每隻樣本陣時，會嘗試連埋隻樣本同埋蔸樹當中最近嘅狀態點（「綟」）。如果條連接係得嘅（完全噉通過自由空間並遵守到任何約束），噉就加埋隻新樣本到蔸樹度。透過對檢索空間嘅均勻採樣，擴展現有綟嘅概率正比於隻綟個Voronoi 區域嘅大細。由於最大嘅Voronoi 區域屬於檢索範圍邊沿啲綟，噉即係話蔸樹識優先向啲大幅嘅未檢索區域䠋展（expand）。

生長控制

樹戥新綟之間嘅連接長度經常捱生長因子限制。如果隨機樣本離樹上最近嘅綟遠過允許嘅限制，噉就唔去使隨機樣本本身，而係使用一粒新綟，粒綟會設得啱啱喺𠍁𠍁最大距離處，而且喺條直線上、從蔸樹直接到隨機樣本上嘅。種情況下啲隨機樣本可以睇作係攞來控制蔸樹嘅生長方向嘅，而生長因子（最大距離）決定唨佢生長嘅速率。噉就保持到 RRT 嘅空間填充偏笡（bias），同時限制到增量生長嘅規模。

RRT 生長都可以加偏笡（biased），透過增加從特定區域採樣狀態點嘅概率。RRT 嘅大多數實際實現都係利用嗰點來指導對規劃問題目標嘅檢索。噉樣係透過捉目標採樣嘅細概率引入到狀態採樣過程來實現嘅。個概率越高，樹生長得越貪婪（greedily）往目標去。

演算法

對於通用配置空間C ，攞虛擬碼寫嘅演算法如下：

    Input: Initial configuration qinit, number of vertices in RRT K, incremental distance Δq)
    Output: RRT graph G

    G.init(qinit)
    for k = 1 to K do
        qrand ← RAND_CONF()
        qnear ← NEAREST_VERTEX(qrand, G)
        qnew ← NEW_CONF(qnear, qrand, Δq)
        G.add_vertex(qnew)
        G.add_edge(qnear, qnew)
    return G

喺上面嘅演算法當中，「 RAND_CONF」喺C 當中抽一個隨機狀態點 q_rand 。個函數攞函數「RAND_FREE_CONF」代替都得，個函數使用C_free 入便嘅樣本，同時使埋某啲碰撞檢測演算法嚟排除C_obs 度嘅樣本。

「 NEAREST_VERTEX」係一個函數，遍歷齊圖G 入便嘅所有頂點 v ，使用一啲測量函數計到q_rand戥v之間嘅距離，嚟返到最近嘅頂點。

喺q_rand嘅方向上，「 NEW_CONF」從q_near𨂾出增量距離Δq來揀新狀態點q_new 。（有啲人覺得應該省略丟並使用q_rand而唔係q_new )

變體同改進

RRT* 家族

有表明，喺「溫和嘅技術條件」（mild technical conditions）下，RRT 中最佳路徑嘅成本幾乎實會收斂到非最佳值，所以要搵到啲收斂到最佳值嘅 RRT 變體，譬如 RRT*。下低係基於 RRT* 嘅方法列表（從 RRT* 本身開始）。但係，並非所有派生方法本身都收斂到最佳狀態點。

• 快速探索隨機圖 (RRG) 同 RRT*：收斂於最佳解嘅 RRT 變體。
• RRT*-Smart：一種加速 RRT* 收斂速度嘅方法，使用到路徑最佳化（戥Theta*類似嘅方式）同智能採樣（偏笡個採樣去面向啲路徑頂點，路徑最佳化後好可能會好靠近啲障礙物）
• A*-RRT同A*-RRT*：一種兩段式運動規劃方法，第一動：使用圖檢索演算法喺一個低維空間（唔考慮完整狀態空間）入便檢索啲初始行得嘅路徑，避開啲危險區域並優先揀啲低風險嘅路線，第二動：運用低維方法捉 RRT* 集中喺連續嘅高維空間入便檢索
• RRT*FN： RRT* 節點數固定，每次迭代親都隨機剪走蔸樹入便一粒葉綟
• RRT*-AR：基於抽樣嘅備用路線規劃（alternate routes planning）
• Informed RRT*： 提高 RRT* 嘅收斂速度，透過引入啟發式嘅方法、類似A*改進迪卡斯特拉演算法噉嘅
• 實時 RRT* (RT-RRT*)： RRT* 同Informed RRT*嘅變體，使用online重佈線畀樹嘅策略，允許樹嘅根蔃隨個智能體移動而唔會棄丟先前採樣過嘅路徑，嚟喺動態環境（似電腦遊戲）當中攞到實時嘅路徑規劃
• RRT ^X同 RRT ^#：針對動態環境最佳化嘅 RRT*
• Theta*-RRT：一種類似於 A*-RRT* 嘅兩段式運動規劃法，任何角度檢索同 RRT 運動規劃嘅分層組合，喺具有復雜非完整約束（nonholonomic）嘅環境裏頭快速生成啲軌跡
• RRT* FND：對動態環境嘅 RRT* 擴展
• RRT-GPU：利用硬件加速嘅三維 RRT 實現
• APF-RRT：RRT 規劃器戥人工勢場方法（Artificial Potential Fields method）嘅組合，可以簡化個重規劃任務
• CERRT：一個 RRT 規劃器，幫唔確定性建模，並利用啲接觸（contacts）減少佢。
• MVRRT*，最細違規 RRT*：一種搵到最短路線嘅演算法，最大限度噉降低得到個唔安全程度（似違反環境規則嘅「成本」，例如交通法規）
• RRT-Blossom：適用於非常之受限（highly constrained）環境嘅 RRT 規劃器。
• TB-RRT：基於時間嘅 RRT 演算法，攞來幫兩個動態系統做交會規劃。
• RRdT*：一種基於 RRT* 嘅規劃器，使用幾蔸局部樹，透過執行局部採樣來主動找平探索空間同埋利用空間兩件事。

其他變體

• Parti-game direct RRTs (PDRRTs)：一種捉 RRT 戥 parti-game 方法結合埋嘅方法，嚟喺需要嘅埞（例如障礙物四周圍）細化檢索，嚟更加快噉規劃並解決得到更加多嘅運動規劃問題相較於傳統 RRT。
• 閉環RRT (CL-RRT)：RRT 嘅擴展，對穩定閉環系統（由車輛同控制器組成嘅）嘅系統輸入進行採樣。

睇埋

• 任何角度路線計劃
• 概率路線圖
• 空間填充樹
• 運動規劃
• 隨機演算法

 

連出去

• 維基同享中有關Rapidly exploring random tree嘅資源類</img>
• RRT 同 RRT* 嘅 Java 可視化工具，包括地圖編輯器
• 使用 Dubins 最短時間路徑嘅 RRT 嘅 C++ 實現