幾種RRT對(duì)比如下：

幾種RRT對(duì)比視圖mp4

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

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

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

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

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

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

參考

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