快速探索隨機樹

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

RRT 係由Steven M. LaValle同James J. Kuffner Jr. 開發嘅。啲演算法輕鬆噉處理得到啲問題場景係有障礙物同有微分約束嘅，並已廣泛噉用於自主機械人運動規劃。

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

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

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

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

描述

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

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

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

演算法 
對於通用配置空間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 當中抽一個隨機狀態點 qrand 。個函數攞函數「RAND_FREE_CONF」代替都得，個函數使用Cfree 入便嘅樣本，同時使埋某啲碰撞檢測演算法嚟排除Cobs 度嘅樣本。

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

喺qrand嘅方向上，「 NEW_CONF」從qnear𨂾出增量距離Δq來揀新狀態點qnew 。下，RRT 中最佳路徑嘅成本幾乎實會收斂到非最佳值，所以要搵到啲收斂到最佳值嘅 RRT 變體，譬如 RRT*。下低係基於 RRT* 嘅方法列表。但係，並非所有派生方法本身都收斂到最佳狀態點。
 快速探索隨機圖 (RRG) 同 RRT*：收斂於最佳解嘅 RRT 變體。
 RRT*-Smart：一種加速 RRT* 收斂速度嘅方法，使用到路徑最佳化同智能採樣
 A*-RRT同A*-RRT*：一種兩段式運動規劃方法，第一動：使用圖檢索演算法喺一個低維空間入便檢索啲初始行得嘅路徑，避開啲危險區域並優先揀啲低風險嘅路線，第二動：運用低維方法捉 RRT* 集中喺連續嘅高維空間入便檢索
 RRT*FN：   RRT* 節點數固定，每次迭代親都隨機剪走蔸樹入便一粒葉綟
 RRT*-AR：基於抽樣嘅備用路線規劃
 Informed RRT*： 提高 RRT* 嘅收斂速度，透過引入啟發式嘅方法、類似A*改進迪卡斯特拉演算法噉嘅
 實時 RRT* (RT-RRT*)： RRT* 同Informed RRT*嘅變體，使用online重佈線畀樹嘅策略，允許樹嘅根蔃隨個智能體移動而唔會棄丟先前採樣過嘅路徑，嚟喺動態環境當中攞到實時嘅路徑規劃
 RRT 同 RRT ：針對動態環境最佳化嘅 RRT*
 Theta*-RRT：一種類似於 A*-RRT* 嘅兩段式運動規劃法，任何角度檢索同 RRT 運動規劃嘅分層組合，喺具有復雜非完整約束嘅環境裏頭快速生成啲軌跡
 RRT* FND：對動態環境嘅 RRT* 擴展
 RRT-GPU：利用硬件加速嘅三維 RRT 實現
 APF-RRT：RRT 規劃器戥人工勢場方法嘅組合，可以簡化個重規劃任務
 CERRT：一個 RRT 規劃器，幫唔確定性建模，並利用啲接觸減少佢。
 MVRRT*，最細違規 RRT*：一種搵到最短路線嘅演算法，最大限度噉降低得到個唔安全程度
 RRT-Blossom：適用於非常之受限環境嘅 RRT 規劃器。
 TB-RRT：基於時間嘅 RRT 演算法，攞來幫兩個動態系統做交會規劃。
 RRdT*：一種基於 RRT* 嘅規劃器，使用幾蔸局部樹，透過執行局部採樣來主動找平探索空間同埋利用空間兩件事。

其他變體 

Parti-game direct RRTs (PDRRTs)：一種捉 RRT 戥 parti-game 方法結合埋嘅方法，嚟喺需要嘅埞細化檢索，嚟更加快噉規劃並解決得到更加多嘅運動規劃問題相較於傳統 RRT。
 閉環RRT (CL-RRT)：RRT 嘅擴展，對穩定閉環系統嘅系統輸入進行採樣。

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

考

RRT 同 RRT* 嘅 Java 可視化工具，包括地圖編輯器
 使用 Dubins 最短時間路徑嘅 RRT 嘅 C++ 實現
運動規劃
演算法
搵路