路径规划（十二）基于采样的算法的总结

几种RRT对比如下：

几种RRT对比视图mp4

        RRT及其变种都是依托于采样+在树结构上加减枝的形式进行路径规划的，具有全局收敛特性，但是效率稳定性不高。不过可以针对性地对其主要函数进行优化进行效率的改进：优化采样，优化树结构等。一种加速RRT的思路就是，从起始点和目标节点同时生长RRT树，这就是connected_RRT。此外，针对变化的环境，还有extend_RRT和Dynamic_RRT。
        RRT*是一种趋近于最优路径的方案，它通过重布线来实现这一目的，它在理论上能达到最优解，但它全局随机撒点的特性导致它在远离目标路径的地方做了过多的生长。

        为了集中优化资源，RRT*-smart应运而生，它比较在乎路径和障碍物的拐点的附近的优化，它通过路径优化步骤判断出路径和障碍物的拐点，并在拐点的邻域内投入更多的资源（即撒更多的点），以实现集中优化资源。

        但RRT*-smart依然浪费了太多的随机点在远离目标路径的区域，那什么才叫不远离目标路径的区域呢？informed RRT*则解决了这一问题，它利用初始路径的长度，起始点和目标点，画出了一个椭圆，informed RRT*认为，这个椭圆区域就是不远离目标路径的区域，生成这个椭圆后，后续的随机撒点只洒在这个椭圆区域内，当更优的路径被发现，则根据这个新路径的长度，缩小椭圆，进一步在有效区域集中撒点资源，以实现加速。

        然而，RRT*类的算法是总会面临一个问题，那就是重布线，这个令RRT*能够逼近最优解的创新恰恰成为了它慢的原因。

        于是，另一种思路被提出，那就是提前给定随机点，然后通过启发式函数来连接这些点以生长路径，这就是FMT*，FMT*专门针对解决高维构型空间中的复杂运动规划问题，在预先确定的采样点数量上执行前向动态规划递归，并相应地通过在代价到达空间中稳步向外移动生成路径树。FMT*能很快的找到一条路径，但是当我们想对这条路径进行优化时，只有通过加密随机采样点的方式，然而，FMT*是一种单批算法，面对新的采样点分布时，它只能重新开始计算。

        为了融合informed RRT*在有效区域集中随机点的特点和FMT*快速生长的特点，就诞生了BIT*。它能够在椭圆区域内分批撒点，实现快速生长的同时，还能自我优化。

参考

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