快速探索隨機樹

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

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

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

## 歷史
為唨做路徑規劃畀機械人過啲障礙物，好早（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 *q**init*, number of vertices in RRT *K*, incremental distance *Δq*)
     Output: RRT graph *G*
 
     *G*.init(*q**init*)
     **for** *k* = 1 **to** *K* **do**
         *q**rand* ← RAND_CONF()
         *q**near* ← NEAREST_VERTEX(*q**rand*, *G*)
         *q**new* ← NEW_CONF(*q**near*, *q**rand*, *Δq*)
         *G*.add_vertex(*q**new*)
         *G*.add_edge(*q**near*, *q**new*)
     **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 同 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 嘅擴展，對穩定閉環系統（由車輛同控制器組成嘅）嘅系統輸入進行採樣。

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

## 考
 

## 連出去

* 
* RRT 同 RRT* 嘅 Java 可視化工具，包括地圖編輯器
* 使用 Dubins 最短時間路徑嘅 RRT 嘅 C++ 實現