基于JPS和变半径RS曲线的Hybrid A^*路径规划算法

摘要

为解决混合A^*（Hybrid A^*）算法在高分辨率地图和复杂场景下搜索效率低、耗费时间长的问题，通过对影响传统Hybrid A^*算法搜索效率的因素进行分析，提出了J-Hybrid A^*算法。首先，在Hybrid A^*算法扩展节点前，使用跳点搜索（JPS）算法进行起点到终点的路径搜索，将该路径进行拉直处理后作为计算节点启发值的基础；其次，设计了新的启发函数，在Hybrid A^*算法扩展前就能完成所有节点启发值的计算，减少了Hybrid A^*扩展节点时计算启发值所需的时间；最后，将RS曲线由最小转弯半径搜索改为变半径RS曲线搜索，使RS曲线能够更早搜索到一条无碰撞路径，进一步提升了Hybrid A^*算法的搜索效率。仿真结果表明：所提J-Hybrid A^*算法在简单环境中比传统Hybrid A^*算法和反向Hybrid A^*算法用时分别缩短68%、21%,在复杂环境中缩短59%、27%。在不同分辨率地图场景中，随着地图分辨率的提高，规划效率显著提升。实车实验表明：所提J-Hybrid A^*算法相较于传统Hybrid A^*算法和反向Hybrid A^*算法的搜索用时分别减少88%、82%,有效提升了Hybrid A^*算法的搜索效率、缩短了路径规划所需时间。

关键词

Hybrid A^*算法 / 启发函数 / JPS算法 / RS曲线 / 路径规划