强制跳点的功能性分类及JPS+算法改进

摘要

随着无人车、无人机等自主移动机器人的井喷式发展，寻路算法的重要性也一再提升。跳点搜索+(jump point search plus, JPS+)算法因其显著的高搜索效率而成为了经典的静态栅格化地图寻路算法。对JPS+算法的改进策略和应用场景层出不穷，但对路径长度与路径节点数量的优化方法仍有待研究。提出了一种对于强制跳点按功能性的分类方式，并基于这一分类对JPS+算法的预处理和搜索流程进行改进，在提高单次搜索扩展效率的同时，减少路径的长度与节点数。通过仿真地图实验与真实采样地图实验，验证了改进算法的有效性。对比发现：改进JPS+算法在仿真地图中，所求路径长度最大减少5.92%,路径节点数最大减少46.15%,算法用时最大减少25.58%;在真实采样地图中，所求路径长度平均减少2.48%,路径节点数平均减少10.71%,算法用时平均减少17.08%。

关键词

路径规划 / 跳点搜索+算法 / 跳点分类 / 地图预处理 / 路径回溯