Improvement of A* Algorithm in Path Planning of Mobile Robot

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

Abstract

Abstract:

To solve the problems of excessively redundant nodes, low search efficiency, and excessive path turning angle in the path search of the traditional A* algorithm, an improved A* algorithm is proposed to plan the optimal path. First, the amount of search neighborhood of the A* algorithm is increased to 24 to obtain a more accurate and comprehensive search field. Second, the angle search algorithm is introduced, eliminating the unnecessary nodes in the path search and making the search more target-oriented. Third, the heuristic function is weighted by the exponential attenuation through the relative position of the current point and the target point, to deal with the relationship between the search speed and the path length. Finally, the obtained path is smoothed to reduce the number of path bends and the bending angle, making the robot move more smoothly. The results show that, compared with the search speed of the original A* algorithm, that of the improved one is increased by 29.16% ~ 65.82% in a complex environment and by 41.87% ~ 64.71% in a simple environment, and the number of path bends is reduced by 27.27% ~ 63.64% and 59.09% ~ 62.12%. Compared to the D* algorithm, there are significant improvements in pathfinding speed, traversing nodes, and the number of path bends. Furthermore, experiments on the improved A* algorithm are conducted in the real environment to verify its better performance and path planning ability.

Key words: A* algorithm, mobile robot, path planning, angle search, ROS (robot operating system)

CLC Number:

TP391.9

Yao Dexin, San Hongjun, Wang Yaru, Sun Haijie, Chen Jiupeng, Yang Xiaoyuan. Improvement of A* Algorithm in Path Planning of Mobile Robot[J]. Journal of System Simulation, 2024, 36(11): 2684-2698.

Figures/Tables 26

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

Fig. 14

Fig. 15

Fig. 16

Table 1

Fig. 17

Table 2

Fig. 18

Fig. 19

Fig. 20

Fig. 21

Fig. 22

Fig. 23

Fig. 24

References 21

1	Wu Lei, Huang Xiaodong, Cui Junguo, et al. Modified Adaptive Ant Colony Optimization Algorithm and Its Application for Solving Path Planning of Mobile Robot[J]. Expert Systems with Applications, 2023, 215: 119410.
2	Fragapane Giuseppe, René de Koster, Sgarbossa Fabio, et al. Planning and Control of Autonomous Mobile Robots for Intralogistics: Literature Review and Research Agenda[J]. European Journal of Operational Research, 2021, 294(2): 405-426.
3	张瑞, 周丽, 刘正洋. 融合RRT^*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
	Zhang Rui, Zhou Li, Liu Zhengyang. Dynamic Path Planning for Mobile Robot Based on RRT^* and Dynamic Window Approach[J]. Journal of System Simulation, 2024, 36(4): 957-968.
4	Jeddisaravi Kossar, Reza Javanmard Alitappeh, C A Pimenta Luciano, et al. Multi-objective Approach for Robot Motion Planning in Search Tasks[J]. Applied Intelligence, 2016, 45(2): 305-321.
5	Luo Qiang, Wang Haibao, Zheng Yan, et al. Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm[J]. Neural Computing and Applications, 2020, 32(6): 1555-1566.
6	Wang Qi, Tang Chunlei. Deep Reinforcement Learning for Transportation Network Combinatorial Optimization: A Survey[J]. Knowledge-Based Systems, 2021, 233: 107526.
7	Qu Rong, Xu Ying, Castro J P, et al. Particle Swarm Optimization for the Steiner Tree in Graph and Delay-constrained Multicast Routing Problems[J]. Journal of Heuristics, 2013, 19(2): 317-342.
8	Huynh Thi Thanh Binh, Pham Dinh Thanh, Ta Bao Thang. New Approach to Solving the Clustered Shortest-path Tree Problem Based on Reducing the Search Space of Evolutionary Algorithm[J]. Knowledge-Based Systems, 2019, 180: 12-25.
9	Tang Gang, Tang Congqiang, Claramunt Christophe, et al. Geometric A-star Algorithm: An Improved A-star Algorithm for AGV Path Planning in a Port Environment[J]. IEEE Access, 2021, 9: 59196-59210.
10	Zhao Tao, Li Haodong, Songyi Dian. Multi-robot Path Planning Based on Improved Artificial Potential Field and Fuzzy Inference System[J]. Journal of Intelligent & Fuzzy Systems, 2020, 39(5): 7621-7637.
11	Li Changgeng, Huang Xia, Ding Jun, et al. Global Path Planning Based on a Bidirectional Alternating Search A^*Algorithm for Mobile Robots[J]. Computers & Industrial Engineering, 2022, 168: 108123.
12	赵晓, 王铮, 黄程侃, 等. 基于改进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.
13	Shang Erke, Dai Bin, Nie Yiming, et al. An Improved A-star Based Path Planning Algorithm for Autonomous Land Vehicles[J]. International Journal of Advanced Robotic Systems, 2020, 17(5): 1729881420962263.
14	Liu Haoxin, Zhang Yonghui. ASL-DWA: An Improved A-star Algorithm for Indoor Cleaning Robots[J]. IEEE Access, 2022, 10: 99498-99515.
15	辛煜, 梁华为, 杜明博, 等. 一种可搜索无限个邻域的改进A^*算法[J]. 机器人, 2014, 36(5): 627-633.
	Xin Yu, Liang Huawei, Du Mingbo, et al. An Improved A^*Algorithm for Searching Infinite Neighbourhoods[J]. Robot, 2014, 36(5): 627-633.
16	Xie Lei, Xue Shuangfei, Zhang Jinfen, et al. A Path Planning Approach Based on Multi-direction A^* Algorithm for Ships Navigating Within Wind Farm Waters[J]. Ocean Engineering, 2019, 184: 311-322.
17	陈娇, 徐菱, 陈佳, 等. 改进A^*和动态窗口法的移动机器人路径规划[J]. 计算机集成制造系统, 2022, 28(6): 1650-1658.
	Chen Jiao, Xu Ling, Chen Jia, et al. Path Planning Based on Improved A^* and Dynamic Window Approach for Mobile Robot[J]. Computer Integrated Manufacturing Systems, 2022, 28(6): 1650-1658.
18	封声飞, 雷琦, 吴文烈, 等. 自适应蚁群算法的移动机器人路径规划[J]. 计算机工程与应用, 2019, 55(17): 35-43.
	Feng Shengfei, Lei Qi, Wu Wenlie, et al. Mobile Robot Path Planning Based on Adaptive Ant Colony Algorithm[J]. Computer Engineering and Applications, 2019, 55(17): 35-43.
19	徐菱, 付文浩, 江文辉, 等. 基于16方向24邻域改进蚁群算法的移动机器人路径规划[J]. 控制与决策, 2021, 36(5): 1137-1146.
	Xu Ling, Fu Wenhao, Jiang Wenhui, et al. Mobile Robots Path Planning Based on 16-directions 24-neighborhoods Improved Ant Colony Algorithm[J]. Robot, 2021, 36(5): 1137-1146.
20	王中玉, 曾国辉, 黄勃, 等. 改进A^*算法的机器人全局最优路径规划[J]. 计算机应用, 2019, 39(9): 2517-2522.
	Wang Zhongyu, Zeng Guohui, Huang Bo, et al. Global Optimal Path Planning for Robots with Improved A^* Algorithm[J]. journal of Computer Applications, 2019, 39(9): 2517-2522.
21	王雅如, 姚得鑫, 刘增力, 等. 基于角度搜索的移动机器人路径规划方法[J]. 系统仿真学报, 2024, 36(7): 1643-1654.
	Wang Yaru, Yao Dexin, Liu Zengli, et al. Path Planning for Mobile Robot Based on Angle Search[J]. Journal of System Simulation, 2024, 36(7): 1643-1654.

地图尺寸	算法	平均计算时间/s	路径长度	搜索节点数	路径折弯数
20×20	A*	0.004 58	31.556	69	10
	改进A*	0.003 24	30.603	30	6
	D*	0.041 41	28.627	313	6
50×50	A*	0.022 83	79.255	236	11
	改进A*	0.008 85	77.378	100	8
	D*	0.280 05	77.359	1 830	8
80×80	A*	0.045 14	130.468	388	11
	改进A*	0.015 43	124.936	169	4
	D*	1.239 53	129.882	4 609	12
100×100	A*	0.055 85	154.651	448	13
	改进A*	0.021 82	142.086	222	8
	D*	3.252 59	146.451	7 859	13

地图尺寸	算法	平均计算时间/s	路径长度	搜索节点数	路径折弯数
20×20	A*	0.004 32	30.384	66	11
	改进A*	0.002 55	29.973	25	5
	D*	0.037 04	29.213	267	12
50×50	A*	0.019 83	75.740	220	19
	改进A*	0.007 62	74.501	90	10
	D*	0.260 48	75.154	1735	15
80×80	A*	0.040 67	125.711	346	21
	改进A*	0.014 35	119.089	155	11
	D*	1.245 51	119.338	4 716	17
100×100	A*	0.057 49	149.380	470	19
	改进A*	0.020 77	151.063	207	13
	D*	3.010 94	149.380	7 330	21

[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]	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.
[9]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[10]	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.
[11]	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.
[12]	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.
[13]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.
[14]	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.
[15]	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.