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]	Yao Wanye, Pang Zewei, Sun Peijie, Wang Zhu. Research on ORB-SLAM Algorithm Based on Windowed Matching Estimation [J]. Journal of System Simulation, 2024, 36(9): 2032-2042.
[2]	Wang Yuelong, Wang Songyan, Chao Tao. Multi-step Information Aided Q-learning Path Planning Algorithm [J]. Journal of System Simulation, 2024, 36(9): 2137-2148.
[3]	Huo Hanlin, Zou Xiangjun, Chen Yan, Zhou Xinzhao, Chen Mingyou, Li Chengen, Pan Yaoqiang, Tang Yunchao. Visual Robot Obstacle Avoidance Planning and Simulation Using Mapped Point Clouds [J]. Journal of System Simulation, 2024, 36(9): 2149-2158.
[4]	Ji Peng, Zhang Xinyuan, Gao Shuaixuan, Wei Shuorang. Path Planning Based on Improved A* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(9): 2171-2180.
[5]	Sun Haijie, San Hongjun, Xiao Le, Yao Dexin, Chen Jiupeng, Yang Xiaoyuan. An Improved Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2024, 36(9): 2193-2207.
[6]	Liu Jialun, Yang Fan, Xie Lingli, Li Shijie, Wang Tengfei. Research on Virtual Simulation Testing Technology for Intelligent Navigation Collision Avoidance Decision-making and Planning [J]. Journal of System Simulation, 2024, 36(8): 1780-1789.
[7]	Liu Bin, Lan Ying, Huang Wentao, Fan Qinqin. UAV Dynamic Path Planning Algorithm Combined with Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(8): 1843-1853.
[8]	Lai Rongshen, Dou Lei, Wu Zhiyong, Sun Shuai. Fusion of Improved A* and Dynamic Window Approach for Mobile Robot Path Planning [J]. Journal of System Simulation, 2024, 36(8): 1884-1894.
[9]	Kang Liang, Du Yi, Yin Lihua. An Improved Cat Swarm Optimization for Heterogeneous Multiple Mobile Robots [J]. Journal of System Simulation, 2024, 36(8): 1958-1968.
[10]	Huang Zhifeng, Liu Yuanhua. UAV Path Planning Based on Improved Harris Hawk Algorithm and B-spline Curve [J]. Journal of System Simulation, 2024, 36(7): 1509-1524.
[11]	Wang Yaru, Yao Dexin, Liu Zengli, Peng Yi. Path Planning for Mobile Robot Based on Angle Search [J]. Journal of System Simulation, 2024, 36(7): 1643-1654.
[12]	Liu Jinhui, Chen Mengyuan, Han Pengpeng, Chen Hebao, Zhang Yukun. A Graph Neural Network Visual SLAM Algorithm for Large-angle View Motion [J]. Journal of System Simulation, 2024, 36(5): 1043-1060.
[13]	Lei Xu, Chen Jingyi, Chen Xiaoyang. Research on Path Planning of Warehouse Robot with Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1081-1092.
[14]	Xiao Peng, Xie Feng, Ni Haihong, Zhang Min, Tang Zhili, Li Ni. Research on Collaborative Optimization Method of Multi-UAV Task Allocation and Path Planning [J]. Journal of System Simulation, 2024, 36(5): 1141-1151.
[15]	Liu Zesen, Bi Sheng, Guo Chuanhong, Wang Yankui, Dong Min. Deep Learning Based Local Path Planning Method for Moving Robots [J]. Journal of System Simulation, 2024, 36(5): 1199-1210.