基于改进启发函数的A*算法的无人机三维路径规划

doi:10.12382/bgxb.2024.0540

摘要/Abstract

摘要：

为满足无人机在复杂环境下的实时三维路径规划需求,针对传统A^*算法在进行三维路径规划时存在的实时性不高、计算量大以及内存消耗严重的问题,对A^*算法的启发函数进行优化处理,调整启发函数权重值,将启发函数作为底数进行指数运算,从而达到提高搜索效率的目的。仿真实验结果表明:通过调整启发函数的权重因子,使算法用时减少了51.69%,搜索的栅格数量降低了45.5%;通过优化启发函数指数大小,使算法在用时上减少了50.56%,搜索的栅格数量降低了45.5%。从而验证了改进的A^*算法相对传统A^*算法能减少路径搜索时长并降低路径规划代价,提高路径搜索效率。

关键词: 三维路径规划, A^*算法, 启发函数, 无人机

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

中图分类号:

TP391

胡明哲, 李旭光, 任智颖, 曾帅. 基于改进启发函数的A^*算法的无人机三维路径规划[J]. 兵工学报, 2024, 45(S1): 302-307.

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.

图/表 14

图1 传统A*算法的应用流程图

Fig.1 Application flowchart of traditional A* algorithm

图2 A*算法三维路径规划

Fig.2 3D path planning of A* algorithm

表1 路径搜索时间分析

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

图3 路径搜索时间

Fig.3 Path search time

表2 路径长度分析

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

图4 路径长度

Fig.4 Path length

表3 总搜索栅格数目分析

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

图5 总搜索栅格数目

Fig.5 Total number of search grids

表4 路径搜索时间分析

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

图6 路径搜索时间

Fig.6 Path search time

表5 路径长度分析

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

图7 路径长度

Fig.7 Path length

表6 总搜索栅格数目分析

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

图8 总搜索栅格数目

Fig.8 Total number of search grids

参考文献 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.