基于RS-RRT的复杂环境路径规划算法

摘要

为了满足在复杂环境下快速搜索有效路径、较短路径的要求，提出一种基于限制扩展快速搜索随机树（Restricted Search Rapidly-Exploring Random Tree Star, RS-RRT^*）的复杂环境路径规划算法。该算法先对随机树的生长方向进行引导，增加在目标区域的采样概率，减少冗余空间的搜索。再在新节点重新选择父节点时，将新节点的启发式代价考虑在内，选择更优父节点。针对初步获取的路径存在拐点较多等问题，引入道格拉斯-普克算法对路径进行简化处理，减少路径中的冗余节点。最后，在简化路径的基础上使用样条插值对于路径平滑处理。实验结果表明，相较于经典RRT^*算法，所提算法路径长度缩短9.9%,规划时间减少76.7%,迭代次数下降44.9%,显著降低了获取最优路径所需的时间和计算成本，提升了路径质量和搜索效率，在复杂环境下的适用性更强。

关键词

快速搜索随机树 / 路径规划 / 区域限制 / 启发式代价 / 三次B样条