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

doi:10.3778/j.issn.1002-8331.2406-0135

摘要/Abstract

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

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

Abstract: 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.

Key words: honeycomb raster, jump point search (JPS), heuristic function, path planning

赵晓东, 侯坤, 王建超, 宿景芳. 面向蜂窝栅格地图的改进跳点搜索算法研究[J]. 计算机工程与应用, 2025, 61(8): 100-107.

ZHAO Xiaodong, HOU Kun, WANG Jianchao, SU Jingfang. Research on Improved Jump Point Search Algorithm for Honeycomb Raster Map[J]. Computer Engineering and Applications, 2025, 61(8): 100-107.

参考文献

[1] HUO F, ZHU S, DONG H, et al. A new approach to smooth path planning of Ackerman mobile robot based on improved ACO algorithm and B-spline curve[J]. Robotics and Autonomous Systems, 2024, 175: 104655.
[2] MIYOMBO E M, LIU K Y, MULENGA M C, et al. Optimal path planning in a real-world radioactive environment: a comparative study of A-star and Dijkstra algorithms[J]. Nuclear Engineering and Design, 2024, 420: 113039.
[3] 沈克宇. 基于改进启发式函数的自适应路径规划算法研究[D]. 成都: 西南民族大学, 2023.
SHEN K Y. Research on adaptive path planning algorithm based on improved heuristic function[D]. Chengdu: Southwest Minzu University, 2023.
[4] 潘富强, 曾成, 马国红, 等. 一种融合改进A*算法与改进动态窗口法的AGV路径规划[J]. 传感技术学报, 2023, 36(1): 68-77.
PAN F Q, ZENG C, MA G H, et al. A novel AGV path planning algorithm based on improved A?algorithm and improved dynamic window approach[J]. Chinese Journal of Sensors and Actuators, 2023, 36(1): 68-77.
[5] 魏念巍, 姜媛媛, 刘延彬, 等. 关键节点和平滑处理的PRM路径优化方法[J]. 计算机工程与应用, 2020, 56(16): 118-123.
WEI N W, JIANG Y Y, LIU Y B, et al, Method of PRM path optimization based on key nodes and smooth processing[J]. Computer Engineering and Applications, 2020, 56(16): 118-123.
[6] WANG H, ZHOU X, LI J, et al. Improved RRT* algorithm for disinfecting robot path planning[J]. Sensors, 2024, 24(5): 1520.
[7] WANG X, KE F, LU J. Research on AGV task path planning based on improved A* algorithm[J]. Virtual Reality & Intelligent Hardware, 2023, 5(3): 249-265.
[8] 陈奕虎, 苏珉, 闭金杰, 等. 基于改进JPS的移动机器人路径规划算法[J]. 电子测量技术, 2023, 46(7): 88-93.
CHEN Y H, SU M, BI J J, et al. Path planning algorithm of mobile robot based on improved JPS algorithm[J]. Electronic Measurement Technology, 2023, 46(7): 88-93.
[9] 黄智榜, 胡立坤, 张宇, 等. 基于改进跳点搜索策略的安全路径研究[J]. 计算机工程与应用, 2021, 57(1): 56-61.
HUANG Z B, HU L K, ZHANG Y, et al. Research on security path based on improved hop search strategy[J]. Computer Engineering and Applications, 2021, 57(1): 56-61.
[10] 吴飞龙, 郭世永. 融合改进A*和动态窗口法的AGV动态路径规划[J]. 科学技术与工程, 2020, 20(30): 12452-12459.
WU F L, GUO S Y. Dynamic path planning of AGV based on fusion of improved A*and dynamic window approach algorithms[J]. Science Technology and Engineering, 2020, 20(30): 12452-12459.
[11] 王文明, 杜佳璐. 基于正六边形栅格JPS算法的智能体路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3635-3642.
WANG W M, DU J L. Agent path planning based on　regular hexagon grid JPS algorithm[J]. Systems Engineering and Electronics, 2021, 43(12): 3635-3642.
[12] 李艳生, 张静琦, 刘彦瑜, 等. 物流机器人调度系统及其双向同步跳点搜索算法设计[J]. 仪器仪表学报, 2023, 44(7): 121-132.
LI Y S, ZHANG J Q, LIU Y Q, et al. Logistics robot scheduling system and the design of bidirectional synchronous jump point search algorithm[J]. Chinese Journal of Scientific Instrument, 2023, 44(7): 121-132.
[13] 张庆, 刘旭, 彭力, 等. 融合JPS和改进A*算法的移动机器人路径规划[J]. 计算机科学与探索, 2021, 15(11): 2233-2240.
ZHANG Q, LIU X, PENG L, et al. Path planning for mobile robots based on JPS and improved A*algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2233-2240.
[14] 魏博闻, 严华. 一种面向非结构化环境的改进跳点搜索路径规划算法[J]. 科学技术与工程, 2021, 21(6): 2363-2370.
WEI B W, YAN H. An improved jump point search path-planning algorithm for unstructured environment[J]. Science Technology and Engineering, 2021, 21(6): 2363-2370.
[15] 唐嘉宁, 闫搏远, 陈云浩, 等. 改进JPS的无人机路径规划研究[J]. 重庆理工大学学报 (自然科学), 2024, 38(1): 328-337.
TANG J N, YAN B Y, CHEN Y H, et al. Improved UAV path planning study for JPS[J]. Journal of Chongqing University of Technology (Natural Science), 2024, 38(1): 328-337.
[16] ZHAOFENG S, JINFEN Z, DA W, et al. A novel path planning algorithm for ships in dynamic current environments[J]. Ocean Engineering, 2023, 288: 116091.
[17] CHEN H, CHEN S Y, WEN C Y, et al. A fast planning approach for 3D short trajectory with a parallel framework[J]. Mechatronics, 2024, 97: 103094.
[18] XU D, YANG J, ZHOU X, et al. Hybrid path planning method for USV using bidirectional A* and improved DWA considering the manoeuvrability and COLREGs[J]. Ocean Engineering, 2024, 298: 117210.
[19] 闫俊涛, 秘金钟, 蔚保国, 等. 基于改进A*算法的室内路径规划[J]. 测绘科学, 2023, 48(10): 58-67.
YAN J T, MI J Z, YU B G, et al. Indoor path planning based on improved A* algorithm[J]. Science of Surveying and Mapping, 2023, 48(10): 58-67.
[20] 姚得鑫, 伞红军, 王雅如, 等. 移动机器人路径规划中A*算法的改进研究[J]. 系统仿真学报, 2024, 36(11): 2684-2698.
YAO D X, SAN H J, WANG Y R, et al. Research on the improvement of A* algorithm in path planning of mobile robot[J]. Journal of System Simulation, 2024, 36(11): 2684-2698.
[21] HUANG T, HUANG D, QIN N, et al. Path planning and control of a quadrotor UAV based on an improved APF using parallel search[J]. International Journal of Aerospace Engineering, 2021(1): 1-14.