幾種RRT對比如下：

幾種RRT對比視圖mp4

        RRT及其變種都是依托于采樣+在樹結構上加減枝的形式進行路徑規(guī)劃的，具有全局收斂特性，但是效率穩(wěn)定性不高。不過可以針對性地對其主要函數(shù)進行優(yōu)化進行效率的改進：優(yōu)化采樣，優(yōu)化樹結構等。一種加速RRT的思路就是，從起始點和目標節(jié)點同時生長RRT樹，這就是connected_RRT。此外，針對變化的環(huán)境，還有extend_RRT和Dynamic_RRT。
        RRT*是一種趨近于最優(yōu)路徑的方案，它通過重布線來實現(xiàn)這一目的，它在理論上能達到最優(yōu)解，但它全局隨機撒點的特性導致它在遠離目標路徑的地方做了過多的生長。

        為了集中優(yōu)化資源，RRT*-smart應運而生，它比較在乎路徑和障礙物的拐點的附近的優(yōu)化，它通過路徑優(yōu)化步驟判斷出路徑和障礙物的拐點，并在拐點的鄰域內投入更多的資源（即撒更多的點），以實現(xiàn)集中優(yōu)化資源。

        但RRT*-smart依然浪費了太多的隨機點在遠離目標路徑的區(qū)域，那什么才叫不遠離目標路徑的區(qū)域呢？informed RRT*則解決了這一問題，它利用初始路徑的長度，起始點和目標點，畫出了一個橢圓，informed RRT*認為，這個橢圓區(qū)域就是不遠離目標路徑的區(qū)域，生成這個橢圓后，后續(xù)的隨機撒點只灑在這個橢圓區(qū)域內，當更優(yōu)的路徑被發(fā)現(xiàn)，則根據(jù)這個新路徑的長度，縮小橢圓，進一步在有效區(qū)域集中撒點資源，以實現(xiàn)加速。

        然而，RRT*類的算法是總會面臨一個問題，那就是重布線，這個令RRT*能夠逼近最優(yōu)解的創(chuàng)新恰恰成為了它慢的原因。

        于是，另一種思路被提出，那就是提前給定隨機點，然后通過啟發(fā)式函數(shù)來連接這些點以生長路徑，這就是FMT*，F(xiàn)MT*專門針對解決高維構型空間中的復雜運動規(guī)劃問題，在預先確定的采樣點數(shù)量上執(zhí)行前向動態(tài)規(guī)劃遞歸，并相應地通過在代價到達空間中穩(wěn)步向外移動生成路徑樹。FMT*能很快的找到一條路徑，但是當我們想對這條路徑進行優(yōu)化時，只有通過加密隨機采樣點的方式，然而，F(xiàn)MT*是一種單批算法，面對新的采樣點分布時，它只能重新開始計算。

        為了融合informed RRT*在有效區(qū)域集中隨機點的特點和FMT*快速生長的特點，就誕生了BIT*。它能夠在橢圓區(qū)域內分批撒點，實現(xiàn)快速生長的同時，還能自我優(yōu)化。

參考

https://www.youtube.com/watch?v=TQIoCC48gp4