路径规划(十一)Batch Informed树(BIT *)

标签: 函数 工具箱 建模 算法

王昊 2023-01-05 15:41:03

11.1 原理

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

15e0d4a9b8a5fc317d98be97da04d05.png

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

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

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

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

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

        BIT*的过程总结为下图:

66e4e9608be084b83551e2fd284c8e5.png


11.2 伪码

9c0c3e53deffe94174a9176feab7066.png

08cbe9edd36f99f1363630fd673e111.png

c990b5648d16e89760ae0c9977d494e.png


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 

1818 0 0 收藏 回复

回复

回复

重置 提交