基于全局关键点提取的改进A*算法全局路径规划研究

doi:10.16182/j.issn1004731x.joss.23-1375

摘要/Abstract

摘要：

为了解决在较大且复杂场景下，传统A*算法寻路会遍历大量节点、计算时间长、易陷入U型陷阱等问题，结合跳点搜索（jump point search，JPS），提出一种改进A*算法，利用图像处理技术对全局地图进行关键点提取。对全局地图进行前处理，获取与障碍物对角相距1格的角点，构建关键点列表，提出全局关键点代替A*算法所需要遍历的节点，大量减少计算量；提出布雷森汉姆直线算法重新定义邻居点，使其能够类似于A*算法探寻邻居点获取路径。在MATLAB中进行仿真验证，并在实际场景中测试，结果表明：改进A*算法在更快获取路径的基础上，路径长度更短，折点数更少，有效解决U型陷阱问题。

关键词: 路径规划, 改进A*算法, 关键点提取, 移动机器人

Abstract:

To address the limitations of the traditional A* algorithm in large and complex scenes, including traversing a large number of nodes, long computation times, and susceptibility to U-shaped traps, this paper proposes an improved A* algorithm incorporating the jump point search (JPS) concept and image processing techniques to extract key points from the global map. The proposed method preprocesses the global map to identify corner points located one grid diagonally from obstacles, constructs a key point list, and replaces the nodes traditionally traversed by the A* algorithm with these global key points, significantly reducing computational overhead. The neighbor nodes are redefined using the Bresenham line algorithm, enabling the algorithm to search for paths efficiently while avoiding unnecessary nodes. The improved A* algorithm was validated through simulations and obstacle scenarios in MATLAB. The results demonstrate that the proposed method achieves faster pathfinding, shorter path lengths, fewer turning points, and effectively addresses the U-shaped trap problem.

Key words: path planning, improved A* algorithm, key point extraction, mobile robot

中图分类号:

TP391.9

林桂娟,李子涵,王宇 . 基于全局关键点提取的改进A*算法全局路径规划研究[J]. 系统仿真学报, 2025, 37(3): 667-678.

Lin Guijuan,Li Zihan,Wang Yu . Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction[J]. Journal of System Simulation, 2025, 37(3): 667-678.

图/表 24

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

表1

图17

图18

图19

图20

图21

图22

图23

参考文献 18

1	唐旭晖, 辛绍杰. 改进蚁群算法的移动机器人路径规划[J]. 计算机工程与应用, 2022, 58(5): 287-295.
	Tang Xuhui, Xin Shaojie. Improved Ant Colony Algorithm for Mobile Robot Path Planning[J]. Computer Engineering and Applications, 2022, 58(5): 287-295.
2	赵迪, 何克勤, 赵祖高. 基于改进粒子群优化算法的移动机器人路径规划[J]. 传感器与微系统, 2023, 42(6): 150-153.
	Zhao Di, He Keqin, Zhao Zugao. Path Planning for Mobile Robot Based on Improved PSO Algorithm[J]. Transducer and Microsystem Technologies, 2023, 42(6): 150-153.
3	Li Jinyang, Zhou Xingchen, Gu Long, et al. The Cutting Path Planning of Main Components in China Initiative Accelerator Driven Subcritical System Based on the Quantum Evolutionary Algorithm[J]. Nuclear Engineering and Design, 2023, 408: 112332.
4	李杰. 基于改进A_Star算法的移动机器人动态路径规划[J]. 黑龙江科学, 2023, 14(16): 47-52, 56.
	Li Jie. Dynamic Path Planning for Mobile Robots Based on Improved A_Star Algorithm[J]. Heilongjiang Science, 2023, 14(16): 47-52, 56.
5	何心, 李志恒, 李冰, 等. 一种改进蚁群算法的移动机器人路径规划研究[J]. 现代制造工程, 2023(2): 36-43.
	He Xin, Li Zhiheng, Li Bing, et al. Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm[J]. Modern Manufacturing Engineering, 2023(2): 36-43.
6	Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
7	Dijkstra E W. A Note on Two Problems in Connexion with Graphs[M]//Krzysztof R Apt, Hoare T. Edsger Wybe Dijkstra: His Life, Work, and Legacy. New York: ACM, 2022: 287-290.
8	Stentz A. Optimal and Efficient Path Planning for Partially-known Environments[C]//Proceedings of the 1994 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 1994: 3310-3317.
9	陈骏, 沈琦琦. 自动导引车路径规划算法的研究综述[J]. 自动化与仪器仪表, 2023(9): 8-15.
	Chen Jun, Shen Qiqi. Review of Path Planning Algorithms for Automated Guided Vehicles[J]. Automation & Instrumentation, 2023(9): 8-15.
10	赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.
	Zhao Xiao, Wang Zheng, Huang Chengkan, et al. Mobile Robot Path Planning Based on an Improved A* Algorithm[J]. Robot, 2018, 40(6): 903-910.
11	Bu Zhaoxing, Korf R E. A*+BFHS: A Hybrid Heuristic Search Algorithm[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2022: 10138-10145.
12	Wang Huanwei, Lou Shangjie, Jing Jing, et al. The EBS-a* Algorithm: AN Improved A* Algorithm for Path Planning[J]. PLoS One, 2022, 17(2): e0263841.
13	Yangqi Ou, Fan Yuexin, Zhang Xinglan, et al. Improved A* Path Planning Method Based on the Grid Map[J]. Sensors, 2022, 22(16): 6198.
14	Harabor Daniel, Grastien Alban. Improving Jump Point Search[C]//Proceedings of the International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2014: 128-135.
15	Hu Yue, Harabor Daniel, Qin Long, et al. Regarding Goal Bounding and Jump Point Search[J]. Journal of Artificial Intelligence Research, 2021, 70: 631-681.
16	马小陆, 梅宏. 基于改进势场蚁群算法的移动机器人全局路径规划[J]. 机械工程学报, 2021, 57(1): 19-27.
	Ma Xiaolu, Mei Hong. Mobile Robot Global Path Planning Based on Improved Ant Colony System Algorithm with Potential Field[J]. Journal of Mechanical Engineering, 2021, 57(1): 19-27.
17	万方, 周风余, 尹磊, 等. 基于电势场法的移动机器人全局路径规划算法[J]. 机器人, 2019, 41(6): 742-750.
	Wan Fang, Zhou Fengyu, Yin Lei, et al. Global Path Planning Algorithm of Mobile Robot Based on Electric Potential Field[J]. Robot, 2019, 41(6): 742-750.
18	徐微, 汤俊伟, 张驰. 改进A*与动态窗口算法的移动机器人路径规划[J]. 计算机仿真, 2023, 40(3): 447-452.
	Xu Wei, Tang Junwei, Zhang Chi. Path Planning of Mobile Robot Based on Improved A* and Dynamic Window Algorithm[J]. Computer Simulation, 2023, 40(3): 447-452.

序号	坐标点		传统A*算法			结合模拟退火的A*算法			本文算法
序号	起点	终点	路径/m	时间/s	折点数量	路径/m	时间/s	折点数量	路径/m	时间/s	折点数量
1	(10, 10)	(50, 24)	45.79	0.269	4	45.44	0.078	3	43.30	0.066	1
2	(4, 56)	(56, 4)	84.54	0.519	12	84.08	0.106	9	80.25	0.082	4
3	(4, 4)	(58, 58)	89.69	1.137	7	88.66	0.418	4	83.55	0.085	4
4	(50, 52)	(4, 42)	55.77	1.824	7	55.14	1.096	7	53.36	0.082	4
5	(12, 26)	(10, 14)	28.61	16.695	6	28.14	10.31	7	27.90	0.065	3
6	(40, 14)	(12, 26)	37.11	7.562	5	36.40	3.808	5	35.83	0.071	2
7	(38, 14)	(10, 24)	37.94	91.402	5	37.58	31.62	5	36.98	0.078	2

[1]	杨超, 郑瑞群, 李圳, 张鸿薇, 唐燕群, 李东泽. 面向无人机辅助车联网的并行任务传输与处理优化策略[J]. 系统仿真学报, 2025, 37(3): 635-645.
[2]	李炯逸, 李强, 张新闻, Htet Zin Myo, 蔡永斌. 移动机器人用改进的双向A*二次路径规划算法[J]. 系统仿真学报, 2025, 37(2): 498-507.
[3]	齐本胜, 李岩, 苗红霞, 陈家林, 李成林. 基于改进启发式RRT的AUV路径规划[J]. 系统仿真学报, 2025, 37(1): 245-256.
[4]	许建民, 宋雷, 邓冬冬, 陈尧箬, 杨炜. 基于多尺度A*与优化DWA算法融合的移动机器人路径规划[J]. 系统仿真学报, 2025, 37(1): 257-270.
[5]	王琪玮, 张琪, 杨硕, 彭勇. 动态任务环境下智能体健壮行为树控制架构设计[J]. 系统仿真学报, 2025, 37(1): 54-65.
[6]	尹安琳, 张著洪. 复杂环境下无人机路径规划及其改进型人工兔优化[J]. 系统仿真学报, 2025, 37(1): 79-94.
[7]	姚万业, 庞泽伟, 孙沛杰, 王祝. 基于窗口化匹配估计的ORB-SLAM算法研究[J]. 系统仿真学报, 2024, 36(9): 2032-2042.
[8]	王越龙, 王松艳, 晁涛. 基于多步信息辅助的Q-learning路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2137-2148.
[9]	霍韩淋, 邹湘军, 陈燕, 周馨曌, 陈明猷, 李承恩, 潘耀强, 唐昀超. 基于视觉机器人障碍点云映射避障规划及仿真[J]. 系统仿真学报, 2024, 36(9): 2149-2158.
[10]	姬鹏, 张新元, 高帅轩, 魏铄让. 融合改进A*算法与动态窗口法的路径规划研究[J]. 系统仿真学报, 2024, 36(9): 2171-2180.
[11]	孙海杰, 伞红军, 肖乐, 姚得鑫, 陈久朋, 杨晓园. 一种改进的移动机器人路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2193-2207.
[12]	刘佳仑, 杨帆, 谢玲利, 李诗杰, 王腾飞. 面向智能航行避碰决策与规划的虚拟仿真测试技术研究[J]. 系统仿真学报, 2024, 36(8): 1780-1789.
[13]	刘斌, 兰莹, 黄文焘, 范勤勤. 融合动态窗口法的无人机动态路径规划算法[J]. 系统仿真学报, 2024, 36(8): 1843-1853.
[14]	赖荣燊, 窦磊, 巫志勇, 孙帅. 融合改进A*算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36(8): 1884-1894.
[15]	康亮, 杜奕, 尹丽华. 一种面向异质多移动机器人的改进猫群算法[J]. 系统仿真学报, 2024, 36(8): 1958-1968.