相关改进RRT算法的路径规划（相关改进的RRT算法+原理分析+python仿真对比分析）_rrt算法及改进

一、改进RRT算法的各个策略

        对于传统RRT算法，由于随机点在地图空间的选取过于随机，导致传统RRT算法在寻找目标点的目标引导性能较差，使算法在整个地图内搜索目标点，从而较多地探索了地图中的无用空间，加大了算法的计算量。同时，算法在得到初始路径后，路径由于是随机点引导生成的路径点，所以路径中的路径点会有曲折性较大，冗余节点较多的缺点。

        为了克服RRT算法存在的以上问题，各种改进的RRT算法被提出，本文主要介绍以下几种改进的RRT算法：

目标偏置RRT算法、双向扩展RRT算法、采样约束与自适应偏置RRT算法、逆向寻优优化路径RRT算法、三次B样条曲线优化路径RRT算法。

二、目标偏置RRT算法

        目标偏置RRT（Goal-Biased RRT）算法是一种改进的 RRT 算法，旨在增加在路径规划过程中选取目标点的概率，从而加速路径搜索并提高搜索效率。该算法在随机采样阶段引入了一定概率选择目标点作为随机点的策略，以便更快地朝向目标点搜索路径。

方法：

1. 目标偏置采样： 在每次随机采样时，以一定概率选择目标点作为随机点，而不是完全随机选择。这可以通过设定一个概率阈值来实现，例如，设定一个较高的概率值，使得选择目标点的概率更高。
2. 路径扩展： 当新节点生成后，沿着从最近节点到随机点的路径方向进行扩展。这可以通过调整节点生成的方法来实现，使得更多的节点朝着目标点方向生长。

原理：

1. 目标偏置采样： 在随机点选取阶段，引入了一定的概率p，根据上述公式，判断选择随机点，以便更频繁地选择目标点作为随机点。这样做可以加速搜索接近目标的路径。如上图点Xrand3和点Xnew3的生成。
2. 路径扩展： 在生成新节点时，沿着从最近节点到随机点的路径方向扩展。如果该方向指向目标点，那么路径搜索会更快地朝着目标方向延伸。如上图点Xrand3到点Xnew3的边所示。

优点：

1. 加速路径搜索： 目标偏置采样使得更多的采样点朝向目标点，从而加速路径搜索过程，减少搜索时间。
2. 有效解决局部最优问题： 通过增加对目标点的偏置，可以有效避免算法陷入局部最优解，提高了全局搜索能力。
3. 简单易实现： 相对于其他复杂的路径规划算法，目标偏置RRT算法相对简单，易于实现和理解。

缺点：

1. 对目标点的依赖性： 如果目标点选择不合适或者目标点与起始点之间存在较大障碍物，可能会导致路径搜索效率下降。
2. 对参数敏感： 算法中的概率阈值参数需要合适地设置，过高或者过低的值都可能影响算法的性能。
3. 无法保证最优解： 虽然目标偏置RRT算法能够加速路径搜索，但并不能保证找到最优路径，仍有可能陷入次优解。

仿真结果:

        综上所述，目标偏置RRT算法通过增加对目标点的偏置来加速路径搜索，具有简单易实现、解决局部最优问题等优点，但在目标点选择和参数设置方面仍存在一定挑战。

三、双向扩展RRT算法

        双向扩展RRT（Bidirectional Rapidly-Exploring Random Trees）算法是一种改进的RRT算法，它同时从起始点和目标点出发，在两个方向上生成两棵树，通过不断扩展这两棵树来搜索可行路径。下面是该算法的详细介绍：

方法：

1. 初始化： 将起始点和目标点分别加入两棵树的根节点。
2. 扩展节点： 从第一棵树中选择一个随机节点进行扩展，生成新节点。在第二棵树中，将该新节点作为随机点，第二棵树中新节点生成方式与标准RRT算法一样，根据一定策略在第二棵树中寻找最近的节点，并在其方向上生成新节点。接着，再以第一棵树中的新节点为随机点，在第二棵树中，获得第二个新节点。然后判断树1和树2的节点数量大小，如果树2小于树1，就将两棵树互相交换。
3. 连接检查： 检查新节点是否可以连接到另一棵树的节点。如果可以连接，则尝试连接两棵树的节点，形成一条路径。
4. 重复扩展和连接： 重复以上步骤，直到两棵树相遇或者达到最大迭代次数。

原理：

1. 双向搜索： 算法同时从起始点和目标点开始，分别生成两棵树。这样做的好处是可以在两个方向上搜索路径，从而更有效地找到起点和终点之间的路径。如上图黑色随机树和绿色随机树的扩展所示。
2. 连接策略： 在生成新节点时，每次选择离随机点最近的节点进行扩展，直到两棵树相遇或者达到最大迭代次数为止。

优点：

1. 快速收敛： 由于算法同时从两个方向搜索路径，因此可以更快地收敛到起点和目标点之间的路径。
2. 有效避免局部最优： 通过双向搜索，算法可以更有效地避免陷入局部最优解，提高了全局搜索能力。

缺点：

1. 额外计算成本： 双向扩展需要额外的计算成本来维护两棵树，并且需要进行连接检查，增加了计算复杂度。
2. 对环境要求高： 对于复杂的环境，双向扩展RRT算法可能会受到环境约束的限制，导致搜索效率降低。
3. 在两棵树相连接的过程中，可能会存在较大转向角度甚至是180度直线交叉等问题，使机器人沿路径行走困难。

仿真结果：

        总的来说，双向扩展RRT算法通过同时从起始点和目标点开始搜索，能够更快地找到可行路径，并且有效避免了局部最优问题，但也存在额外的计算成本和对环境要求较高的缺点。

四、采样约束与自适应偏置RRT算法

        这种新算法，我称之为"目标吸引约束RRT"（Target Attraction Constrained RRT），结合了对已有随机点位置的约束和目标偏置策略，以更高效地搜索可行路径。下面是该算法的详细介绍：

原理：

约束点引导原理图

目标偏置原理图 

1. 约束点引导： 算法通过对已有随机点位置的约束，使得新生成的随机点倾向于朝向目标点。这种约束方法类似于将已有随机点形成的墙体，逐渐向右压缩可采样的空间，以减少探索无用空间，从而加速搜索过程。如上图所示。
2. 目标偏置策略： 借鉴目标吸引的概念，引入一种新的权重
   声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/808614