Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm

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

Abstract

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

CLC Number:

TP242.6

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

Figures/Tables 13

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

References 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]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Zhang Kaixiang, Mao Jianlin, Wang Niya, Xu Zhihao. Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference [J]. Journal of System Simulation, 2025, 37(8): 2074-2088.
[4]	Wan Yuhang, Zhu Zilu, Zhong Chunfu, Liu Yongkui, Lin Tingyu, Zhang Lin. Dynamic Path Planning for Robotic Arms Based on an Improved PPO Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1462-1473.
[5]	Ye Chen, Shao Peng, Zhang Shaoping, Li Wenting, Zhou Tengming. Enhanced Artificial Gorilla Algorithm for Mobile Robot Path Planning [J]. Journal of System Simulation, 2025, 37(6): 1474-1485.
[6]	Zhang Yan, Li Binghua, Huo Tao, Liu Rong. Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1555-1564.
[7]	Zhou Xiaohui, Li Yanqiang, Wang Yong, Zhao Decai, Yang Xiaoyao. Robot Path Planning Based on Ant Colony Algorithm with Dual Heuristic Information [J]. Journal of System Simulation, 2025, 37(5): 1280-1289.
[8]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[9]	He Zhigang, Li Dayan, Wang Niya, Mao Jianlin, Wang Ning. A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode [J]. Journal of System Simulation, 2025, 37(4): 953-967.
[10]	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.
[11]	Bai Yuxin, Chen Zhenya, Shi Ruitao, Su Weitao, Ma Zhuoqiang, Yang Shangjin. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2025, 37(3): 742-752.
[12]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.
[13]	Li Jiongyi, Li Qiang, Zhang Xinwen, Htet Zin Myo, Cai Yongbin. Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2025, 37(2): 498-507.
[14]	Peng Yi, Lei Yunkui, Yang Qingqing, Li Hui, Wang Jianming. Improved PID Search Algorithm for UAV Path Planning in Mountainous Environments [J]. Journal of System Simulation, 2025, 37(12): 3075-3086.
[15]	Xing Lijing, Li Min, Zeng Xiangguang, Zhang Ping, Peng Bei. AUV Path Planning Based on Behavior Cloning and Improved DQN in Partially Unknown Environments [J]. Journal of System Simulation, 2025, 37(11): 2754-2767.