重庆理工大学学报2025，Vol.39Issue(1)：102-110,9.DOI:10.3969/j.issn.1674-8425(z).2025.01.013
强制跳点的功能性分类及JPS+算法改进
Functional classification of forced jump point and research on the improvement of JPS+algorithm
摘要
Abstract
With the growing popularity of autonomous mobile robots such as unmanned vehicles and drones,path planning algorithms have become crucial.The jump point search(JPS)algorithm proposed in 2011 has attracted keen academic attention for its far superior efficiency compared with traditional A∗algorithms.The further optimized jump point search plus(JPS+)algorithm,through map preprocessing mechanism,not only markedly improves planning efficiency,but also ensures the Manhattan distance characteristics of the path.Thus,it has become a classic algorithm for static grid map pathfinding. Despite its huge improvements and wide applications,JPS+algorithm still has to optimize path length and node count.Based on the MATLAB platform,many simulation grid maps are built and the JPS+algorithm is reproduced,and its performance characteristics and flaws are analyzed in details. On this basis,we propose a functional oriented forced jump point classification method,which subdivides forced jump points into three categories:general,adjoint,and derivative,providing a new perspective for algorithm optimization. The preprocessing and search process of JPS+algorithm have been improved,which not only enhances the efficiency of single search,but also significantly reduces the path length and number of nodes. To verify the improvement,a comparative experiment is conducted between simulated maps and real sampled maps.Our results show in the simulation,the improved algorithm reduces the maximum path length by 5.92％,the maximum number of nodes by 46.15％,and the maximum time by 25.58％.In real maps,the average path length is cut by 2.48％,the average number of nodes by 10.71％,and the average time by 17.08％. Through innovative forced jump point classification methods and improvements to the JPS+algorithm,the performance of path planning algorithms has been greatly enhanced,laying a solid foundation for efficient navigation of autonomous mobile robots in complex environments.关键词
路径规划/跳点搜索+算法/跳点分类/地图预处理/路径回溯Key words
path planning/jump point search plus algorithm/jump point classification/map preprocessing/path backtracking分类
信息技术与安全科学引用本文复制引用
吴蓓蓓,梁智文..强制跳点的功能性分类及JPS+算法改进[J].重庆理工大学学报,2025,39(1):102-110,9.基金项目
国家自然科学基金项目(11502141) （11502141）
