计算机科学与探索

作者：张庆，刘旭，彭力，朱凤增

单位：物联网技术应用教育部工程研究中心（江南大学 物联网工程学院），江苏 无锡 214122

关键词：移动机器人,路径规划,A*算法,跳点搜索（JPS）,切比雪夫距离

针对传统A*算法在场景较大的栅格地图路径规划时，很多冗余节点的遍历导致寻路算法内存消耗大、计算速度慢等问题，提出了一种对A*算法的改进策略。首先，改进启发函数的具体计算方式，利用切比雪夫距离替代欧氏距离使启发式函数精确地等于实际最佳路径，减少A*节点的拓展数量；其次，使用跳点搜索（JPS）策略筛选出跳点添加到OpenList和ClosedList代替A*算法中大量不必要的邻节点，通过跳点实现较长距离的跳跃，从而减少内存占用以及对节点的评估，直到生成最终路径。为了验证A*算法改进后的效果，在五种尺寸的二维栅格地图中进行仿真测试，结果表明，改进后的A*算法减少了大量寻路过程评估的节点，提高了寻路速度，并且随着地图尺寸的增加，改进后的A*算法能将寻路速度提高一个数量级以上。最后，将改进后的算法应用在移动机器人路径规划器上进行实验，在同一规划任务下，JPS策略下改进的A*算法较传统A*算法，路径搜索耗费时间减少了92.2%，拓展的节点减少了97.37%，能够满足大场景下移动机器人快速路径规划的要求。

来源：2021年第11期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2021年第11期