UAV 3D Path Planning Based on A* Algorithm with Improved Heuristic Function

doi:10.12382/bgxb.2024.0540

Abstract

Abstract:

In order to meet the real-time three-dimensional path planning requirements of unmanned aerial vehicles (UAVs) in complex environments, the heuristic function of the A^* algorithm is optimized to address the problems of low real-time performance, large amount of calculation and serious memory consumption in the traditional A^* algorithm when performing three-dimensional path planning. The weight value of heuristic function is adjusted and the heuristic function is used as the base for exponential operation, so as to achieve the purpose of improving the search efficiency. The simulated results show that the algorithm time is reduced by 51.69% and the number of searched grids is reduced by 45.5% after adjusting the weight factor of heuristic function. By optimizing the exponential size of the heuristic function, the algorithm time is reduced by 50.56% and the number of searched grids is reduced by 45.5%. This verifies that the improved A^* algorithm can reduce the path search time and path planning cost compared with the traditional A^* algorithm, and improve the path search efficiency.

Key words: three-dimensional path planning, A^* algorithm, heuristic functions, unmanned aerial vehicle

CLC Number:

TP391

HU Mingzhe, LI Xuguang, REN Zhiying, ZENG Shuai. UAV 3D Path Planning Based on A^* Algorithm with Improved Heuristic Function[J]. Acta Armamentarii, 2024, 45(S1): 302-307.

Figures/Tables 14

Fig.1 Application flowchart of traditional A* algorithm

Fig.2 3D path planning of A* algorithm

Table 1 Path search time analysis

β	1	1.2	1.5	2	5	6	6.01	10	20
时间/s	0.89	641.91	0.55	0.5	0.45	0.46	0.43	0.42	0.45

Fig.3 Path search time

Table 2 Path length analysis

β	1	1.2	1.5	2	5	6	6.01	10	20
路径长度	637.96	641.91	643.04	645.2	648.2	649.2	653.2	653.2	663.2

Fig.4 Path length

Table 3 Analysis of the total number of search grids

β	1	1.2	1.5	2	5	6	6.01	10	20
栅格数	26026	23608	18408	16458	14404	14248	14196	14196	14196

Fig.5 Total number of search grids

Table 4 Path search time analysis

m	1	1.1	1.2	1.3	1.4	1.5	1.6	2
时间/s	0.89	0.64	0.47	0.45	0.44	0.44	0.47	0.44

Fig.6 Path search time

Table 5 Path length analysis

m	1	1.1	1.2	1.3	1.4	1.5	1.6	2
路径长度	637.96	644.2	644.2	644.2	644.2	644.2	644.2	644.2

Fig.7 Path length

Table 6 Analysis of the total number of search grids

m	1	1.1	1.2	1.3	1.4	1.5	1.6	2
栅格数	26026	18226	15418	14612	14300	14196	14196	14196

Fig.8 Total number of search grids

References 20

[5]	XIAO H, ZHANG H, ZHOU W, et al. Research on UAV path planning algorithm based on improved virtual spring method[J/OL]. Advances in Aeronautical Science and Engineering, 2024, (2024-02-19)[2024-02-29]. http://kns.cnki.net/kcms/detail/61.1479.V.20240207.2158.002.html. (in Chinese)
[6]	高九州, 张焯. 基于改进A^*算法的无人机三维空间避障路径规划[J]. 计算机测量与控制, 2023, 31(12): 203-209, 223.
	GAO J Z, ZHANG C. Obstacle avoidance path planning of UAV in 3D space based on improved A^* algorithm[J]. Computer Measurement and Control, 2023, 31(12):203-209, 223. (in Chinese)
[7]	冯勇超, 万广喜, 曾鹏. 三维路径规划中改进蚁群算法搜索策略[J]. 计算机工程与设计, 2023, 44(12): 3613-3620.
	FENG Y C, WAN G X, ZENG P. Search strategy of improved ant colony algorithm in 3D path planning[J]. Computer Engineering and Design, 2023, 44(12):3613-3620. (in Chinese)
[8]	陈晨. 改进A^*算法的机器人最短路径规划研究[J]. 计算机与数字工程, 2023, 51(8):1697-1701.
	CHEN C. Research on robot shortest path planning with improved A^* algorithm[J]. Computer and Digital Engineering, 2023, 51(8): 1697-1701. (in Chinese)
[9]	LI M C, ZHANG H J. AUV 3D Path Planning Based on A^* Algorithm[C]// Proceedings of the 2020 Chinese Automation Congress. Shanghai, China: IEEE, 2020: 11-16.
[10]	胡致远, 王征, 杨洋, 等. 基于人工鱼群-蚁群算法的UUV三维全局路径规划[J]. 兵工学报, 2022, 43(7): 1676-1684. doi: 10.12382/bgxb.2021.0215
	HU Z Y, WANG Z, YANG Y, et al. Three-dimensional global path planning for UUV based on artificial fish swarm and ant colony algorithm[J]. Acta Armamentarii, 2022, 43(7):1676-1684. (in Chinese) doi: 10.12382/bgxb.2021.0215
[11]	张家闻, 房浩霖, 李家旺. 基于复杂约束条件的欠驱动AUV三维路径规划[J]. 兵工学报, 2022, 43(6): 1407-1414. doi: 10.12382/bgxb.2021.0340
[1]	陈先亮, 黄元君, 范勤勤. 基于多模态多目标进化算法的无人机三维路径规划[J]. 火力与指挥控制, 2023, 48(11): 32-39.
	CHEN X L, HUANG Y J, FAN Q Q. Three-dimensional path planning of UAV based on multimodal multi-objective evolutionary algorithm[J]. Fire Control & Command Control, 2023, 48 (11): 32-39. (in Chinese)
[2]	刘威, 储春华, 肖明伟. 一种基于时间和路径双重优化的改进A^*算法[J]. 制造业自动化, 2023, 45(12):173-177.
	LIU W, CHU M H, XIAO M W. An improved A^* algorithm based on dual optimization of time and path[J]. Manufacturing Automation, 2023, 45(12):173-177. (in Chinese)
[3]	谢高杨, 房立清, 李亚男, 等. 基于改进RRT算法的无人靶车路径规划研究[J]. 火炮发射与控制学报, 2024, 45(3):80-86.
	XIE G Y, FANG L Q, LI Y N, et al. Research on route planning of unmanned target vehicle with improved RRT[J]. Journal of Gun Launch & Control, 2024, 45(3):80-86. (in Chinese)
[4]	冯迎宾, 赵子君, 晏佳华. 改进RRT算法的四旋翼无人机路径规划方法[J]. 沈阳理工大学学报, 2024, 43(1): 9-15.
	FENG Y B, ZHAO Z J, YAN J H. An optimizing RRT algorithm for quadrotor UAV path planning[J]. Journal of Shenyang Ligong University, 2024, 43(1): 9-15. (in Chinese)
[5]	肖蘅, 张汇, 周文, 等. 基于改进虚拟弹簧模型的无人机路径规划算法研究[J/OL]. 航空工程进展, 2024, (2024-02-19)[2024-02-29]. http://kns.cnki.net/kcms/detail/61.1479.V.20240207.2158.002.html.
[11]	ZHANG J W, FANG H L, LI J W. 3D path planning of underactuated AUV based on complex constraints[J]. Acta Armamentarii, 2022, 43(6):1407-1414. (in Chinese) doi: 10.12382/bgxb.2021.0340
[12]	PACHUNG P, PANDYA K, NAGAR A. et al. Efficient 3D path planning for drone swarm using improved sine cosine algorithm[J]. SN Computer Science, 2024, 5(3):286.
[13]	SEO D, KANG J. Collision-avoided tracking control of UAV using velocity-adaptive 3D local path planning[J]. International Journal of Control, Automation and Systems, 2023, 21(1):231-243.
[14]	DU Y. W Multi-UAV search and rescue with enhanced A^* algorithm path planning in 3D environment[J]. International Journal of Aerospace Engineering, 2023(1): 8614117.
[15]	MANDLOI D, ARYA R, VERMA A K. Unmanned aerial vehicle path planning based on A^* algorithm and its variants in 3D environment[J]. International Journal of System Assurance Engineering and Management, 2021, 12(5): 990-1000.
[16]	ERKE S, BIN D, YIMING N, et al. An improved A-star based path planning algorithm for autonomous land vehicles[J]. International Journal of Advanced Robotic Systems. 2020, 17(5):591-617.
[17]	李季, 孙秀霞. 基于改进A-Star算法的无人机航迹规划算法研究[J]. 兵工学报, 2008, 29(7):788-792.
	LI J, SUN X X. A route planning’s method for unmanned aerial vehicles based on improved A-star algorithm[J]. Acta Armamentarii, 2008, 29(7):788-792. (in Chinese)
[18]	ZHANG D X, CHEN C, ZHANG G Y. AGV path planning based on improved A-star algorithm[C]// Proceedings of the 2024 IEEE 7th Advanced Information Technology, Electronic and Automation Control Conference. Chongqing, China: IEEE, 2024:1590-1595.
[19]	HA I. Improved A-star search algorithm for probabilistic air pollution detection using UAVs[J]. Sensors, 2024, 24(4): 1141.
[20]	KABIR R, WATANOBE Y, ISLAM M R, et al. Enhanced robot motion block of A-star algorithm for robotic path planning[J]. Sensors, 2024, 24(5): 1422-1452.