路径规划（十一）Batch Informed树（BIT *）

11.1 原理

        简单来说，BIT*是结合了Informed RRT*和FMT*的优点的一种算法。回顾一下，Informed RRT*是对RRT*的一种优化，在RRT*生成一个初始路径后，则以初始路径的长度，起始点和目标点为焦点，画一个椭圆，Informed RRT*在后续随机采点时，只取落在这个椭圆内的点，一次采一个点，重复lm次。FMT*则与RRT那一套不同，它不是边采点，边生长树，而是一次性提前在整个区域（不包含障碍物区域）内采lm个点，只重复一次。

        下面我们来说说，Informed RRT*和优缺点FMT*，然后就知道为什么要引出BIT*了。

        先说FMT*，FMT*的优点是从起始位置开始构建，没有重布线过程，因此节约时间，适用于复杂的障碍物环境。但是FMT*的缺点是，它只有1批，FMT*路径的精度完全取决于当前批撒点的密度，当你想要提升精度时，只能重新开始一批，重新更密集的撒点，然后重新开始规划。

        再说Informed RRT*，Informed RRT*的优点恰好弥补了FMT*的缺点，想要提升精度，只需撒更多的点就好了，而Informed RRT*的撒点过程时一直在进行的，它一批只撒一个点，重复很多批，开始新的批的时候之前的信息不会被抛弃，只要Informed RRT*一直撒点，就可以达到任意精度。但是Informed RRT*的缺点也显而易见，它需要重布线，计算效率低。

        所以自然就想到，能不能利用FMT*的优点，提前撒好点，不用重布线，提升计算效率，

又能多批进行，以不断提升精度？当然能，这就是BIT*算法

        BIT*的过程总结为下图：

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