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

张博强; 张成龙; 冯天培; 高向川

doi:10.13705/j.issn.1671-6833.2025.02.022

郑州大学学报（工学版） ›› 2025, Vol. 46 ›› Issue (02) : 19 -25. DOI: 10.13705/j.issn.1671-6833.2025.02.022

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

张博强, 张成龙, 冯天培, 高向川

作者信息 +

Author information +

文章历史 +

摘要

为解决混合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^*算法的搜索效率、缩短了路径规划所需时间。