11.1 原理

        簡單來說，BIT*是結(jié)合了Informed RRT*和FMT*的優(yōu)點的一種算法。回顧一下，Informed RRT*是對RRT*的一種優(yōu)化，在RRT*生成一個初始路徑后，則以初始路徑的長度，起始點和目標(biāo)點為焦點，畫一個橢圓，Informed RRT*在后續(xù)隨機采點時，只取落在這個橢圓內(nèi)的點，一次采一個點，重復(fù)lm次。FMT*則與RRT那一套不同，它不是邊采點，邊生長樹，而是一次性提前在整個區(qū)域（不包含障礙物區(qū)域）內(nèi)采lm個點，只重復(fù)一次。

        下面我們來說說，Informed RRT*和優(yōu)缺點FMT*，然后就知道為什么要引出BIT*了。

        先說FMT*，F(xiàn)MT*的優(yōu)點是從起始位置開始構(gòu)建，沒有重布線過程，因此節(jié)約時間，適用于復(fù)雜的障礙物環(huán)境。但是FMT*的缺點是，它只有1批，F(xiàn)MT*路徑的精度完全取決于當(dāng)前批撒點的密度，當(dāng)你想要提升精度時，只能重新開始一批，重新更密集的撒點，然后重新開始規(guī)劃。

        再說Informed RRT*，Informed RRT*的優(yōu)點恰好彌補了FMT*的缺點，想要提升精度，只需撒更多的點就好了，而Informed RRT*的撒點過程時一直在進行的，它一批只撒一個點，重復(fù)很多批，開始新的批的時候之前的信息不會被拋棄，只要Informed RRT*一直撒點，就可以達到任意精度。但是Informed RRT*的缺點也顯而易見，它需要重布線，計算效率低。

        所以自然就想到，能不能利用FMT*的優(yōu)點，提前撒好點，不用重布線，提升計算效率，

又能多批進行，以不斷提升精度？當(dāng)然能，這就是BIT*算法

        BIT*的過程總結(jié)為下圖：

11.2 偽碼

11.3 參考

1、Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search

2、Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs