面向蜂窝栅格地图的改进跳点搜索算法研究

来源：计算机工程与应用杂志2025年第8期北京时间：

作者：赵晓东, 侯坤, 王建超, 宿景芳

单位：河北科技大学 信息科学与工程学院，石家庄 050018

摘要：针对跳点搜索算法（jump point search，JPS）在路径规划过程中出现的穿越墙角的不安全行为，提出了一种基于蜂窝栅格地图的跳点搜索算法（honeycomb raster map-JPS，H-JPS）。构建蜂窝栅格地图代替传统栅格地图，在JPS算法的基础上结合蜂窝栅格修改了剪枝规则与跳点判断规则，再利用蜂窝栅格特点设计了新的启发式函数来提高搜索效率，通过找寻最远节点的节点更新规则来优化生成的轨迹。利用Matlab仿真平台验证算法的搜索效率和安全性，结果表明，相较于传统JPS算法，采用H-JPS算法进行路径规划能够完全消除危险节点，路径规划时间和长度分别缩短了41.9%和11.1%，显著提高了搜索效率。

关键词：蜂窝栅格,跳点搜索,启发式函数,路径规划