目的 解决传统跳点搜索算法在路径规划中存在的冗余节点多、内存占用高、路径平滑性及安全性不足的问题,提升自动导引车的运行效率与安全性。方法 首先引入双向搜索策略,从起点和终点同时执行跳点搜索并迭代寻优。其次,改进评价函数,为启发函数设置动态自适应系数。然后,采用删除冗余节点优化策略,用安全线段替代冗余转折。最后,对路径拐点进行圆弧化处理,提高路径平滑度。结果 仿真表明,与传统算法相比,改进算法在保持路径安全的前提下,路径长度减小,搜索时间有所缩短,同时转弯次数减少,行驶路径更加平滑。结论 改进算法显著提升了路径规划的平滑性、安全性和实时性,适用于复杂环境下的自动导引车导航。
Abstract
The work aims to address the issues of excessive redundant nodes, high memory consumption, and inadequate path smoothness and safety in traditional Jump Point Search (JPS) algorithms for path planning, thereby improving the operational efficiency and safety of Automated Guided Vehicles (AGVs). Firstly, a bidirectional search strategy was introduced, performing jump point searches simultaneously from the start and goal nodes with iterative optimization. Secondly, the evaluation function was improved by incorporating a dynamic adaptive coefficient into the heuristic function. Thirdly, a redundant node removal strategy was adopted, replacing unnecessary turns with safe line segments. Finally, path corners were processed with arc smoothing to enhance path smoothness. Simulation results demonstrated that, compared to the traditional algorithm, the improved algorithm reduced path length, shortened search time, decreased the number of turns, and yielded a smoother travel path, while maintaining path safety. The improved algorithm significantly enhances path smoothness, safety, and real-time performance, making it well-suited for AGV navigation in complex environments.
关键词
路径规划 /
跳点搜索 /
双向搜索 /
平滑优化
Key words
path planning /
jump point search /
bidirectional search /
smooth optimization
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 周栾, 陈尔奎, 吴梅花. 基于改进遗传算法的矿山救援机器人路径规划[J]. 煤炭技术, 2019, 38(6): 139-142.
ZHOU L, CHEN E K, WU M H.Path Planning for Mine Rescue Robot Based on Improved Genetic Algorithm[J]. Coal Technology, 2019, 38(6): 139-142.
[2] 段显丰. 基于仓储AGV的调度策略与路径规划研究[D]. 济南: 山东大学, 2021.
DUAN X F.Research on Scheduling Strategy and Path Planning Based on Warehousing AGV[D]. Jinan: Shandong University, 2021.
[3] 赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.
ZHAO X, WANG Z, HUANG C K, et al.Mobile Robot Path Planning Based on an Improved A*Algorithm[J]. Robot, 2018, 40(6): 903-910.
[4] HUA X, ZHANG T T, CAO J.Dynamic Path Planning for Vehicles Based on Causal State-Masking Deep Reinforcement Learning[J]. Algorithms, 2025, 18(3): 146.
[5] XIE T B, YAO X F, JIANG Z H, et al.AGV Path Planning with Dynamic Obstacles Based on Deep Q-Network and Distributed Training[J]. International Journal of Precision Engineering and Manufacturing-Green Technology, 2025, 12(3): 1005-1021.
[6] 何精武, 李伟东. 基于改进JPS算法的无人车路径规划[J]. 吉林大学学报(信息科学版), 2024, 42(5): 808-816.
HE J W, LI W D.Unmanned Vehicle Path Planning Based on Improved JPS Algorithm[J]. Journal of Jilin University (Information Science Edition), 2024, 42(5): 808-816.
[7] 王圣淳. 基于改进JPS与DWA算法的多无人机路径规划研究[D]. 广汉: 中国民用航空飞行学院, 2024.
WANG S C.Research on Multi-UAV Path Planning Based on Improved JPS and DWA Algorithms[D]. Guanghan: Civil Aviation Flight University of China, 2024.
[8] 金震, 黄卫华, 李传奇, 等. 基于改进JPS和A*算法的组合路径规划[J]. 高技术通讯, 2022, 32(4): 412-420.
JIN Z, HUANG W H, LI C Q, et al.Combination Path Planning Based on Improved Jump Point Search and A* Algorithm[J]. Chinese High Technology Letters, 2022, 32(4): 412-420.
[9] 刘荣华, 王欣, 吴迪, 等. 改进双向动态JPS算法的移动机器人全局路径规划[J]. 计算机应用研究, 2024, 41(4): 1117-1122.
LIU R H, WANG X, WU D, et al.Improved Bidirectional Dynamic JPS Algorithm for Global Path Planning of Mobile Robot[J]. Application Research of Computers, 2024, 41(4): 1117-1122.
[10] 柳佳. 移动机器人路径规划和避障算法研究[D]. 武汉: 武汉理工大学, 2022.
LIU J.Research on Path Planning and Obstacle Avoidance Algorithm of Mobile Robot[D]. Wuhan: Wuhan University of Technology, 2022.
[11] ZHOU K J, YU L L, LONG Z W, et al.Local Path Planning of Driverless Car Navigation Based on Jump Point Search Method under Urban Environment[J]. Future Internet, 2017, 9(3): 51.
[12] 陈奕虎, 苏珉, 闭金杰, 等. 基于改进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.
[13] 杨凤满, 张奇志, 周亚丽. 家庭服务机器人路径规划的跳点搜索算法[J]. 北京信息科技大学学报(自然科学版), 2018, 33(3): 85-89.
YANG F M, ZHANG Q Z, ZHOU Y L.Jump Point Search Algorithm for Path Planning of Home Service Robot[J]. Journal of Beijing Information Science & Technology University, 2018, 33(3): 85-89.
[14] 马小陆, 梅宏. 双向跳点搜索算法的移动机器人全局路径规划研究[J]. 机械科学与技术, 2020, 39(10): 1624-1631.
MA X L, MEI H.Research on Bidirectional Jump Point Search Algorithm of Global Path Planning for Mobile Robots[J]. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(10): 1624-1631.
[15] 秦齐, 万熠, 侯嘉瑞, 等. 基于双向动态跳点搜索算法的AGV路径规划研究[J]. 单片机与嵌入式系统应用, 2021, 21(8): 55-58.
QIN Q, WAN Y, HOU J R, et al.AGV Path Planning Based on Bidirectional Dynamic Jumping Search Algorithm[J]. Microcontrollers & Embedded Systems, 2021, 21(8): 55-58.
[16] 李航天, 黄子奇, 张安琳, 等. 基于改进A*算法的海上物资投送路径规划[J]. 火力与指挥控制, 2023, 48(8): 111-117.
LI H T, HUANG Z Q, ZHANG A L, et al.Path Planning of Goods and Materials Delivery at Sea Based on Improved A*Algorithm[J]. Fire Control & Command Control, 2023, 48(8): 111-117.
[17] 陈芹, 李燕, 樊新宇. 改进跳点搜索算法的移动机器人路径规划[J]. 组合机床与自动化加工技术, 2024(9): 81-85.
CHEN Q, LI Y, FAN X Y.Path Planning of Mobile Robot with Improved JPS[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2024(9): 81-85.
基金
国家自然科学基金（62103173）;江苏师范大学科文学院“人才项目”
PDF(736 KB)
渝公网安备 50010702501716号 渝ICP备15012534号-2
