11.1 原理

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

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

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

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

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

又能多批進(jìn)行，以不斷提升精度？當(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