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

Research on Improved Jump Point Search Algorithm for Honeycomb Raster Map

作　　者：赵晓东[1] 侯坤 王建超 宿景芳[1] ZHAO Xiaodong;HOU Kun;WANG Jianchao;SU Jingfang(College of Information Science and Engineering,Hebei University of Science and Technology,Shijiazhuang 050018,China)

机构地区：[1]河北科技大学信息科学与工程学院,石家庄050018

出　　处：《计算机工程与应用》2025年第8期100-107,共8页Computer Engineering and Applications

基　　金：河北省高等学校科学技术研究项目(QN2023185)。

摘　　要：针对跳点搜索算法(jump point search,JPS)在路径规划过程中出现的穿越墙角的不安全行为,提出了一种基于蜂窝栅格地图的跳点搜索算法(honeycomb raster map-JPS,H-JPS)。构建蜂窝栅格地图代替传统栅格地图,在JPS算法的基础上结合蜂窝栅格修改了剪枝规则与跳点判断规则,再利用蜂窝栅格特点设计了新的启发式函数来提高搜索效率,通过找寻最远节点的节点更新规则来优化生成的轨迹。利用Matlab仿真平台验证算法的搜索效率和安全性,结果表明,相较于传统JPS算法,采用H-JPS算法进行路径规划能够完全消除危险节点,路径规划时间和长度分别缩短了41.9%和11.1%,显著提高了搜索效率。Aiming at the unsafe behaviour of jump point search(JPS)in the path planning process of crossing the corners,a honeycomb raster map-JPS(H-JPS)algorithm based on honeycomb raster map is proposed.Firstly,the honeycomb raster map is constructed instead of the traditional raster map,then the pruning rule and the jump point judgement rule are modified based on the JPS algorithm combined with the honeycomb raster,then a new heuristic function is designed to improve the searching efficiency by using the characteristics of the honeycomb raster,and finally the generated trajectory is optimized by the node updating rule of finding the farthest node.Matlab simulation platform is used to verify the search efficiency and safety of the algorithm,and the results show that compared with the traditional JPS algorithm,the path planning using the H-JPS algorithm can completely eliminate the dangerous nodes,and the path planning time and length are shortened by 41.9%and 11.1%respectively,which significantly improves the search efficiency.

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

分 类 号：TP242.6[自动化与计算机技术—检测技术与自动化装置]