基于搜索步优化A*算法的移动机器人路径规划

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

摘要/Abstract

摘要：

针对在大规模高分辨地图中传统A*算法机器人路径规划存在耗时较高、路径质量较差等问题，提出了一种搜索步优化A*算法。基于三次Hermite曲线构建步长匹配机器人尺寸、线形符合机器人动力学约束的搜索步(连接当前节点至后继节点的路径边)集合；利用曲线的整段弧长和最大曲率值建立更准确的代价函数。实验结果表明：相较于A*算法规划耗时平均降低51.83%、机器人执行路径的运动耗时平均降低14.07%；相较于Hybrid A*算法规划耗时平均降低67.65%，运动耗时相近，证明搜索步优化A*算法不仅提高了搜索效率，还通过提高路径质量提升了机器人的运动性能。

关键词: 移动机器人, 路径规划, A*算法, 参数曲线, 搜索步集合

Abstract:

A search-step optimized A* algorithm is proposed to address the issues with the traditional A* algorithm in robot path planning tasks, such as the high time consumption in large-scale high-resolution maps and the poor paths qualitys. Based on the cubic Hermite curve, a set of search steps (the path edges connecting the current node to its successors) is constructed, which can match the size of the robot and satisfy the dynamic constraints of the robot. More accurate cost functions are established based on the length and maximum absolute curvature value of the curve. Experimental results show that compared with the A* algorithm, the planning time is reduced by an average of 51.83% , and the movement time of the robot execution path is reduced by an average of 14.07% . Compared with the Hybrid A* algorithm, the average planning time is reduced by an average of 67.65%, while the movement time is similar. The results prove that the search-step optimized A* algorithm not only improves search efficiency, but also enhances the robot's performance by improving path quality.

Key words: mobile robot, path planning, A* algorithm, parametric curve, search-step set

中图分类号:

TP242.6

喻蝶,鲍柏仲,司言等 . 基于搜索步优化A*算法的移动机器人路径规划[J]. 系统仿真学报, 2025, 37(4): 1041-1050.

Yu Die,Bao Baizhong,Si Yan,et al . Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm[J]. Journal of System Simulation, 2025, 37(4): 1041-1050.

图/表 13

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

参考文献 33

1	中华人民共和国中央人民政府. 十五部门关于印发《"十四五"机器人产业发展规划》的通知: 工信部联规〔2021〕206号[EB/OL]. (2021-12-21) [2023-12-18]. .
2	崔炜, 朱发证. 机器人导航的路径规划算法研究综述[J]. 计算机工程与应用, 2023, 59(19): 10-20.
	Cui Wei, Zhu Fazheng. Review of Path Planning Algorithms for Robot Navigation[J]. Computer Engineering and Applications, 2023, 59(19): 10-20.
3	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.
4	Dolgov D, Thrun S, Montemerlo M, et al. Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments[J]. The International Journal of Robotics Research, 2010, 29(5): 485-501.
5	Sedighi S, Nguyen D V, Kapsalas P, et al. Implementing Voronoi-based Guided Hybrid A^* in Global Path Planning for Autonomous Vehicles[C]//2019 IEEE Intelligent Transportation Systems Conference (ITSC). Piscataway: IEEE, 2019: 3845-3852.
6	Karaman S, Frazzoli E. Sampling-based Algorithms for Optimal Motion Planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
7	Webb D J, Jur van den Berg. Kinodynamic RRT^*: Asymptotically Optimal Motion Planning for Robots with Linear Dynamics[C]//2013 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2013: 5054-5061.
8	Yavari M, Gupta K, Mehrandezh M. Lazy Steering RRT^*: An Optimal Constrained Kinodynamic Neural Network Based Planner with No In-exploration Steering[C]//2019 19th International Conference on Advanced Robotics (ICAR). Piscataway: IEEE, 2019: 400-407.
9	Wang Jiankun, Li Baopu, Meng Q H. Kinematic Constrained Bi-directional RRT with Efficient Branch Pruning for Robot Path Planning[J]. Expert Systems with Applications, 2021, 170: 114541.
10	Zheng Dongliang, Tsiotras P. Accelerating Kinodynamic RRT^* Through Dimensionality Reduction[C]//2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Piscataway: IEEE, 2021: 3674-3680.
11	Ganesan Sivasankar, Senthil Kumar Natarajan, Thondiyath Asokan. G-RRT^: Goal-oriented Sampling-based RRT^ Path Planning Algorithm for Mobile Robot Navigation with Improved Convergence Rate[C]//Proceedings of the 2021 5th International Conference on Advances in Robotics. New York: ACM, 2022: 1-6.
12	Wang Xinda, Luo Xiao, Han Baoling, et al. Collision-free Path Planning Method for Robots Based on an Improved Rapidly-exploring Random Tree Algorithm[J]. Applied Sciences, 2020, 10(4): 1381.
13	Nie Zhibin, Yang Xiaobing, Gao Shihong, et al. Research on Autonomous Moving Robot Path Planning Based on Improved Particle Swarm Optimization[C]//2016 IEEE Congress on Evolutionary Computation (CEC). Piscataway: IEEE, 2016: 2532-2536.
14	Rashid Razif, Perumal N, Elamvazuthi I, et al. Mobile Robot Path Planning Using Ant Colony Optimization[C]//2016 2nd IEEE International Symposium on Robotics and Manufacturing Automation (ROMA). Piscataway: IEEE, 2016: 1-6.
15	Hashim Fatma A, Hussien Abdelazim G. Snake Optimizer: A Novel Meta-heuristic Optimization Algorithm[J]. Knowledge-Based Systems, 2022, 242: 108320.
16	李涛, 赵宏生. 基于进化蚁群算法的移动机器人路径优化[J]. 控制与决策, 2023, 38(3): 612-620.
	Li Tao, Zhao Hongsheng. Path Optimization for Mobile Robot Based on Evolutionary Ant Colony Algorithm[J]. Control and Decision, 2023, 38(3): 612-620.
17	陆顺意, 何庆, 王艺蒙, 等. 用于移动机器人路径规划的增强型蛇优化算法[J]. 传感器与微系统, 2023, 42(12): 127-129, 133.
	Lu Shunyi, He Qing, Wang Yimeng, et al. Enhanced Snake Optimization Algorithm for Mobile Robot Path Planning[J]. Transducer and Microsystem Technologies, 2023, 42(12): 127-129, 133.
18	Zhang Tianrui, Xu Jianan, Wu Baoku. Hybrid Path Planning Model for Multiple Robots Considering Obstacle Avoidance[J]. IEEE Access, 2022, 10: 71914-71935.
19	Watkins C J C H, Dayan Peter. Q-learning[J]. Machine Learning, 1992, 8(3): 279-292.
20	Kontoudis G P, Vamvoudakis K G. Kinodynamic Motion Planning with Continuous-time Q-learning: An Online, Model-free, and Safe Navigation Framework[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 30(12): 3803-3817.
21	沈克宇, 游志宇, 刘永鑫, 等. 基于改进A^*算法的移动机器人路径规划[J]. 计算机应用研究, 2023, 40(1): 75-79.
	Shen Keyu, You Zhiyu, Liu Yongxin, et al. Mobile Robot Planning Based on Improved A^* Algorithm[J]. Application Research of Computers, 2023, 40(1): 75-79.
22	潘富强, 曾成, 马国红, 等. 一种融合改进A^*算法与改进动态窗口法的AGV路径规划[J]. 传感技术学报, 2023, 36(1): 68-77.
	Pan Fuqiang, Zeng Cheng, Ma Guohong, 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.
23	郭大林, 王淑营, 曾文驱, 等. 改进A^*算法的路径规划在列检环境中的应用[J]. 计算机工程与设计, 2023, 44(1): 299-306.
	Guo Dalin, Wang Shuying, Zeng Wenqu, et al. Application of Path Planning Based on Improved A^* Algorithm in Train Inspection Environment[J]. Computer Engineering and Design, 2023, 44(1): 299-306.
24	姚得鑫, 伞红军, 王雅如, 等. 移动机器人路径规划中A^*算法的改进研究[J]. 系统仿真学报, 2024, 36(11): 2684-2698.
	Yao Dexin, Hongjun San, Wang Yaru, et al. Improvement of A^*Algorithm in Path Planning of Mobile Robot[J]. Journal of System Simulation, 2024, 36(11): 2684-2698.
25	孙军艳, 吴焕钦, 王子豪. 基于改进A^*算法的多AGV路径规划及避障研究[J]. 西安理工大学学报, 2024, 40(2): 242-252.
	Sun Junyan, Wu Huanqin, Wang zi Hao. Multi-AGV Based on Improved A^* Algorithm Path Planning and Obstacle Avoidance Research[J]. Journal of Xi'an University of Technology, 2024, 40(2): 242-252.
26	Zhou Boyu, Gao Fei, Wang Luqi, et al. Robust and Efficient Quadrotor Trajectory Generation for Fast Autonomous Flight[J]. IEEE Robotics and Automation Letters, 2019, 4(4): 3529-3536.
27	Zhao Yu, Zhu Yongqiang, Zhang Pingxia, et al. A Hybrid A^* Path Planning Algorithm Based on Multi-objective Constraints[C]//2022 Asia Conference on Advanced Robotics, Automation, and Control Engineering (ARACE). Piscataway: IEEE, 2022: 1-6.
28	张浩杰, 张玉东, 梁荣敏, 等. 改进A^*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45(2): 513-520.
	Zhang Haojie, Zhang Yudong, Liang Rongmin, et al. Energy-efficient Path Planning Method for Robots Based on Improved A^* Algorithm[J]. Systems Engineering and Electronics, 2023, 45(2): 513-520.
29	Zhao Lin, Zhang Xinghui, Ren Weiyan. A Lévy-inspired Kinodynamic A^* Algorithm for Quadrotor Fast Path Searching[C]//2021 IEEE 7th International Conference on Cloud Computing and Intelligent Systems (CCIS). Piscataway: IEEE, 2021: 350-355.
30	Roesmann C, Feiten W, Woesch T, et al. Trajectory Modification Considering Dynamic Constraints of Autonomous Robots[C]//ROBOTIK 2012; 7th German Conference on Robotics. Piscataway: IEEE, 2012: 1-6.
31	Yu Jingjin. Average Case Constant Factor Time and Distance Optimal Multi-robot Path Planning in Well-connected Environments[J]. Autonomous Robots, 2020, 44(3): 469-483.
32	Han Ruihua, Chen Shengduo, Wang Shuaijun, et al. Reinforcement Learned Distributed Multi-robot Navigation with Reciprocal Velocity Obstacle Shaped Rewards[J]. IEEE Robotics and Automation Letters, 2022, 7(3): 5896-5903.
33	Chandra R, Manocha D. GamePlan: Game-theoretic Multi-agent Planning with Human Drivers at Intersections, Roundabouts, and Merging[J]. IEEE Robotics and Automation Letters, 2022, 7(2): 2676-2683.

[1]	杨超, 郑瑞群, 李圳, 张鸿薇, 唐燕群, 李东泽. 面向无人机辅助车联网的并行任务传输与处理优化策略[J]. 系统仿真学报, 2025, 37(3): 635-645.
[2]	林桂娟, 李子涵, 王宇. 基于全局关键点提取的改进A*算法全局路径规划研究[J]. 系统仿真学报, 2025, 37(3): 667-678.
[3]	白宇鑫, 陈振亚, 石瑞涛, 苏蔚涛, 马卓强, 杨尚进. 基于改进哈里斯鹰算法的机器人路径规划研究[J]. 系统仿真学报, 2025, 37(3): 742-752.
[4]	金煦, 莫愿斌. 多策略混合山地瞪羚优化器在机器人路径规划问题中的应用[J]. 系统仿真学报, 2025, 37(3): 803-821.
[5]	李炯逸, 李强, 张新闻, Htet Zin Myo, 蔡永斌. 移动机器人用改进的双向A*二次路径规划算法[J]. 系统仿真学报, 2025, 37(2): 498-507.
[6]	齐本胜, 李岩, 苗红霞, 陈家林, 李成林. 基于改进启发式RRT的AUV路径规划[J]. 系统仿真学报, 2025, 37(1): 245-256.
[7]	许建民, 宋雷, 邓冬冬, 陈尧箬, 杨炜. 基于多尺度A*与优化DWA算法融合的移动机器人路径规划[J]. 系统仿真学报, 2025, 37(1): 257-270.
[8]	王琪玮, 张琪, 杨硕, 彭勇. 动态任务环境下智能体健壮行为树控制架构设计[J]. 系统仿真学报, 2025, 37(1): 54-65.
[9]	尹安琳, 张著洪. 复杂环境下无人机路径规划及其改进型人工兔优化[J]. 系统仿真学报, 2025, 37(1): 79-94.
[10]	姚万业, 庞泽伟, 孙沛杰, 王祝. 基于窗口化匹配估计的ORB-SLAM算法研究[J]. 系统仿真学报, 2024, 36(9): 2032-2042.
[11]	王越龙, 王松艳, 晁涛. 基于多步信息辅助的Q-learning路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2137-2148.
[12]	霍韩淋, 邹湘军, 陈燕, 周馨曌, 陈明猷, 李承恩, 潘耀强, 唐昀超. 基于视觉机器人障碍点云映射避障规划及仿真[J]. 系统仿真学报, 2024, 36(9): 2149-2158.
[13]	姬鹏, 张新元, 高帅轩, 魏铄让. 融合改进A*算法与动态窗口法的路径规划研究[J]. 系统仿真学报, 2024, 36(9): 2171-2180.
[14]	孙海杰, 伞红军, 肖乐, 姚得鑫, 陈久朋, 杨晓园. 一种改进的移动机器人路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2193-2207.
[15]	刘佳仑, 杨帆, 谢玲利, 李诗杰, 王腾飞. 面向智能航行避碰决策与规划的虚拟仿真测试技术研究[J]. 系统仿真学报, 2024, 36(8): 1780-1789.