基于EMSDBO算法的无人机三维航迹规划

doi:10.12305/j.issn.1001-506X.2024.05.28

摘要/Abstract

摘要：

针对无人机(unmanned aerial vehicle, UAV)三维航迹规划问题, 提出一种增强型多策略蜣螂算法的UAV航迹规划方法。首先, 将飞行接近率和响应时间的动态约束添加到威胁成本代价中, 并考虑UAV转弯性能的影响, 建立三维任务空间模型与航迹代价函数。其次, 在蜣螂算法中引入偏移估计策略、变螺旋搜索策略、准反向学习策略和逐维变异策略, 提高算法的全局寻优能力和收敛速度。最后, 给出了改进算法在三维环境下航迹规划的仿真结果。结果表明: 综合考虑UAV机动性能和转弯性能, 规划出的路径可以更加安全有效地避开危险源。相比其他算法, 改进算法的寻优能力更好, 规划的航迹质量更优。

关键词: 无人机, 路径规划, 飞行接近率, 蜣螂优化算法

Abstract:

In view of the unmanned aerial vehicle (UAV) three-dimensional path planning problem, an enhanced multi-strategy dung beetle algorithm of UAV path planning is proposed. Firstly, constraints on the flight proximity rate and response time are introduced and added to the threat cost, considering the influence of UAV turning performance, a three-dimensional task space model and trajectory cost function are established. Secondly, the dung beetle algorithm is enhanced by introducing offset estimation strategy, variable spiral search strategy, quasi-inverse learning strategy, and dimensional mutation strategy to improve the algorithm's global optimization capability and convergence speed. Finally, simulation results of the improved algorithm for three-dimensional trajectory planning in an environment are presented. Results demonstrate that by considering both the maneuverability and turning performance of the UAV, the planned path can safely and efficiently avoid hazards. Compared to other algorithms, the enhanced multi-strategy dung beetle algorithm shows better optimization capability and generates higher-quality trajectories.

Key words: unmanned aerial vehicle (UAV), path planning, flight proximity rate, dung beetle optimizer algorithm

中图分类号:

V249

隋东, 杨振宇, 丁松滨, 周婷婷. 基于EMSDBO算法的无人机三维航迹规划[J]. 系统工程与电子技术, 2024, 46(5): 1756-1766.

Dong SUI, Zhenyu YANG, Songbin DING, Tingting ZHOU. Three-dimensional path planning of UAV based on EMSDBO algorithm[J]. Systems Engineering and Electronics, 2024, 46(5): 1756-1766.

图/表 15

图1

图2

表1

表2

表3

图3

表4

表5

图4

表6

图5

图6

图7

表7

图8

参考文献 33

20	XUE J K , SHEN B . Dung beetle optimizer: a new meta-heuristic algorithm for global optimization[J]. The Journal of Supercomputing, 2023, 79, 7305- 7336. doi: 10.1007/s11227-022-04959-6
21	GUO J J , YUAN W C , DANG X Z , et al. Cable force optimization of a curved cable-stayed bridge with combined simulated annealing method and cubic B-Spline interpolation curves[J]. Engineering Structures, 2019, 201 (1): 109813.
22	张洪海, 邹依原, 张启钱, 等. 未来城市空中交通管理研究综述[J]. 航空学报, 2021, 42 (7): 82- 106.
	ZHANG H H , ZOU Y Y , ZHANG Q Q , et al. Future urban air mobility management: review[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42 (7): 82- 106.
23	张军峰, 蒋海行, 武晓光, 等. 基于BADA及航空器意图的四维航迹预测[J]. 西南交通大学学报, 2014, 49 (3): 553- 558. doi: 10.3969/j.issn.0258-2724.2014.03.028
	ZHANG J F , JIANG H X , WU X G , et al. 4D trajectory prediction based on BADA and aircraft intent[J]. Journal of Southwest Jiaotong University, 2014, 49 (3): 553- 558. doi: 10.3969/j.issn.0258-2724.2014.03.028
24	JIANG H , DENG J H , CHEN Q S . Olfactory sensor combined with chemometrics analysis to determine fatty acid in stored wheat[J]. Food Control, 2023, 153, 109942- 109961. doi: 10.1016/j.foodcont.2023.109942
25	WU C L , FU J C , HUANG X R , et al. Lithium-ion battery health state prediction based on VMD and DBO-SVR[J]. Energies, 2023, 16 (10): 3993- 4012. doi: 10.3390/en16103993
26	ZHU F , LI G S , TANG H , et al. Dung beetle optimization algorithm based on quantum computing and multi-strategy fusion for solving engineering problems[J]. Expert Systems with Applications, 2024, 236 (1): 121219- 121237.
27	HAUSCHILD M , PELIKAN M . An introduction and survey of estimation of distribution algorithms[J]. Swarm and evolutionary computation, 2011, 1 (3): 111- 128. doi: 10.1016/j.swevo.2011.08.003
28	MIRJALILI S , LEWIS A . The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95 (1): 51- 67.
1	CHAO D , WU Q H . Survey of layered architecture in largescale FANETs[J]. Computer Science, 2020, 47 (9): 226- 231.
2	赵畅, 刘允刚, 陈琳, 等. 面向元启发式算法的多无人机路径规划现状与展望[J]. 控制与决策, 2022, 37 (5): 1102- 1115.
	ZHAO C , LIU Y G , CHEN L , et al. Research and development trend of multi-UAV path planning based on metaheuristic algorithm[J]. Control and Decision, 2022, 37 (5): 1102- 1115.
3	杨旭, 王锐, 张涛. 面向无人机集群路径规划的智能优化算法综述[J]. 控制理论与应用, 2020, 37 (11): 2291- 2302. doi: 10.7641/CTA.2020.00105
	YANG X , WANG R , ZHANG T . Review of unmanned aerial vehicle swarm path planning based on intelligent optimization[J]. Control Theory & Applications, 2020, 37 (11): 2291- 2302. doi: 10.7641/CTA.2020.00105
4	ZENG Y , ZHANG R . Energy-efficient UAV communication with trajectory optimization[J]. IEEE Trans.on Wireless Communications, 2017, 16 (6): 3747- 3760. doi: 10.1109/TWC.2017.2688328
5	AGGARWAL S , KUMAR N . Path planning techniques for unmanned aerial vehicles: a review, solutions, and challenges[J]. Computer Communications, 2020, 149 (1): 270- 299.
6	WANG H B , YIN P H , ZHENG W , et al. Mobile robot path planning based on improved A* algorithm and dynamic window method[J]. Robot, 2020, 42 (3): 92- 99.
7	LI W M , WANG L , ZOU A W , et al. Path planning for UAV based on improved PRM[J]. Energies, 2022, 15 (19): 7267- 7283. doi: 10.3390/en15197267
8	MIN Y , LUO J J , WANG M M , et al. Coordinated path planning by integrating improved RRT* and quartic spline[J]. Chinse Journal of Mechanics, 2020, 52 (4): 1024- 1034.
9	QI B K , LI M Q , YANG Y , et al. Research on UAV path planning obstacle avoidance algorithm based on improved artificial potential field method[J]. Journal of Physics: Conference Series, 2021, 1948 (1): 012060. doi: 10.1088/1742-6596/1948/1/012060
10	JIANG C K , LI Z , PAN S B , et al. Collision-free path planning of AGVs based on improved dijkstra algorithm[J]. Computer Science, 2020, 47 (8): 272- 277.
11	WANG Y H , WANG S M . UAV path planning based on improved particle swarm optimization[J]. Computer Engineering & Science, 2020, 42 (9): 1690- 1696. doi: 10.3969/j.issn.1007-130X.2020.09.020
12	CAO Y , WEI W Y , BAI Y , et al. Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm[J]. Cluster Computing, 2019, 22 (1): 5175- 5184.
13	ZHANG X M , HU Y J , LI W G , et al. Mission planning of multi base UAV based on improved artificial bee colony algorithm[J]. Journal of Physics: Conference Series, 2020, 1550 (3): 32072- 32096. doi: 10.1088/1742-6596/1550/3/032072
14	JARRAY R , AL-DHAIFALLAH M , REZK H , et al. Parallel cooperative coevolutionary grey wolf optimizer for path planning problem of unmanned aerial vehicles[J]. Sensors, 2022, 22 (5): 1826- 1848. doi: 10.3390/s22051826
15	刘志强, 何丽, 袁亮, 等. 采用改进灰狼算法的移动机器人路径规划[J]. 西安交通大学学报, 2022, 56 (10): 49- 60. doi: 10.7652/xjtuxb202210005
	LIU Z Q , HE L , YUAN L , et al. Path planning of mobile robot based on TGWO algorithm[J]. Journal of Xi'an Jiaotong University, 2022, 56 (10): 49- 60. doi: 10.7652/xjtuxb202210005
16	LIN N , TANG J C , LI X W , et al. A novel improved bat algorithm in UAV path planning[J]. Computers, Materials & Continua, 2019, 61 (1): 323- 344.
17	YU W W , LIU J , ZHOU J . A novel sparrow particle swarm algorithm (SPSA) for unmanned aerial vehicle path planning[J]. Scientific Programming, 2021, 2021 (1): 5158304.
18	PHUNG M D , HA Q P . Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization[J]. Applied Soft Computing, 2021, 107 (1): 107376- 107395.
19	ZHAI L Z , FENG S H . A novel evacuation path planning method based on improved genetic algorithm[J]. Journal of Intelligent & Fuzzy Systems, 2022, 42 (3): 1813- 1823.
29	WANG H , WU Z J , RAHNAMAYAN S , et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181 (20): 4699- 4714. doi: 10.1016/j.ins.2011.03.016
30	ZHANG X M , WANG D D , FU Z H , et al. Novel biogeography-based optimization algorithm with hybrid migration and global-best Gaussian mutation[J]. Applied Mathematical Modelling, 2020, 86 (1): 74- 91.
31	MIRJALILI S , MIRJALILI S M , LEWIS A . Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69 (1): 46- 61.
32	DEHGHANI M , HUBALOVSKY S , TROJOVSKY P . Northern goshawk optimization: a new swarm-based algorithm for solving optimization problems[J]. IEEE Access, 2021, 9 (1): 162059- 162080.
33	LIU G Y , SHU C , LIANG Z W , et al. A modified sparrow search algorithm with application in 3D route planning for UAV[J]. Sensors, 2021, 21 (4): 1224- 1245. doi: 10.3390/s21041224

飞行模式	判断条件	速度
水平飞行	ϕ_t≤ϕ₀且ψ_t≤ψ₀	v₁
偏转转弯	ϕ_t>ϕ₀且ψ_t≤ψ₀	v₂
爬升下降	ϕ_t≤ϕ₀且ψ_t>ψ₀	v₃

函数类别	公式表达式	维度	搜索范围	最优值
单峰函数	$f_1(x)=\sum\limits_{i=1}^n x_i^2$	30	[-100, 100]	0
	$f_2(x)=\sum\limits_{i=1}^n\left(\sum\limits_{j=1}^i x_j\right)^2$	30	[-100, 100]	0
	$f_3(x)=\sum\limits_{i=1}^n\left(\left\|x_i+0.5\right\|\right)^2$	30	[-100, 100]	0
	$f_4(x)=\sum\limits_{i=1}^n i x_i^4+\operatorname{random}[0, 1)$	30	[-1.28, 1.28]	0
多峰函数	$f_5(x)=\sum\limits_{i=1}^n\left[x_i^2-10 \cos 2 {\rm{ \mathsf{ π} }} x_i+10\right]$	30	[-5.12, 5.12]	0
多峰函数	$f_6(x)=\frac{1}{4000} x_i^2-\prod\limits_{i=1}^n \cos \left(\frac{x_i}{\sqrt{i}}\right)+1$	30	[-600, 600]	0

测试函数	统计值	EMSDBO	DBO	GWO	WOA	NGO
f₁	最优值	0.00 E+00	1.12 E-142	5.76 E-30	2.75 E-82	1.43 E-89
	平均值	0.00 E+00	2.83 E-106	1.14 E-27	6.91 E-73	4.37 E-87
	标准差	0.00 E+00	1.92 E-105	2.22 E-27	2.72 E-72	1.86 E-86
f₂	最优值	0.00 E+00	2.02 E-96	9.17 E-09	7.56 E+04	4.98 E-28
	平均值	0.00 E+00	2.56 E-40	5.87 E-06	1.49 E+04	1.84 E-22
	标准差	0.00 E+00	1.29 E-39	1.40 E-05	4.79 E+04	8.18 E-22
f₃	最优值	6.67 E-12	4.80 E-06	2.49 E-01	9.34 E-02	7.17 E-07
	平均值	1.17 E-10	4.86 E-03	7.76 E-01	3.85 E-01	7.73 E-04
	标准差	1.30 E-10	2.38 E-02	3.50 E-01	2.41 E-01	3.40 E-03
f₄	最优值	3.45 E-06	9.52 E-05	3.38 E-04	5.58 E-07	1.86 E-04
	平均值	7.22 E-05	1.39 E-03	2.00 E-03	2.97 E-03	6.29 E-04
	标准差	5.66 E-05	1.04 E-03	1.09 E-03	2.94 E-03	3.16 E-04
f₅	最优值	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00
	平均值	0.00 E+00	7.96 E-01	2.87 E+00	1.14 E-15	0.00 E+00
	标准差	0.00 E+00	4.01 E+00	3.71 E+00	8.04 E-15	0.00 E+00
f₆	最优值	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00
	平均值	0.00 E+00	4.26 E-04	5.03 E-03	1.76 E-02	0.00 E+00
	标准差	0.00 E+00	3.01 E-03	1.04 E-02	6.83 E-03	0.00 E+00

函数	统计值	DBO	ODBO	SDBO	QDBO	VDBO	EMSDBO
f₁	最优值	1.12 E-142	2.24 E-148	5.82 E-155	0.00 E+00	2.11 E-213	0.00 E+00
	平均值	2.83 E-106	3.84 E-121	1.94 E-114	0.00 E+00	4.93 E-107	0.00 E+00
	标准差	1.92 E-105	1.22 E-110	1.06 E-113	0.00 E+00	3.49 E-106	0.00 E+00
f₂	最优值	2.02 E-96	1.20 E-72	2.21 E-75	0.00 E+00	1.90 E-101	0.00 E+00
	平均值	2.56 E-40	1.56 E-42	5.84 E-54	0.00 E+00	5.91 E-38	0.00 E+00
	标准差	1.29 E-39	8.93 E-39	3.81 E-53	0.00 E+00	3.95 E-40	0.00 E+00
f₃	最优值	4.80 E-06	2.82 E-07	4.22 E-06	5.76 E-07	8.94 E-10	6.67 E-12
	平均值	4.86 E-03	1.51 E-06	6.46 E-04	3.56 E-03	8.54 E-08	1.17 E-10
	标准差	2.38 E-02	8.10 E-07	5.45 E-04	1.97 E-02	2.13 E-07	1.30 E-10
f₄	最优值	9.52 E-05	2.28 E-05	2.10 E-06	1.57 E-04	3.54 E-05	3.45 E-06
	平均值	1.39 E-03	1.14 E-03	1.14 E-04	1.04 E-03	7.96 E-04	7.22 E-05
	标准差	1.04 E-03	8.27 E-04	9.01 E-05	8.05 E-04	7.11 E-04	5.66 E-05
f₅	最优值	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00
	平均值	7.96 E-01	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00
	标准差	4.01 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00
f₆	最优值	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00
	平均值	4.26 E-04	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00
	标准差	3.01 E-03	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00	0.00 E+00

参数名称	设置值	参数名称	设置值
m	15	t_min/s	3
ϕ_max/(°)	45	v₁/(m/s)	15
ψ_max/(°)	45	v₂/(m/s)	10
l_min/m	30	v₃/(m/s)	6
α₁	0.6	t_min/s	2
α₂	0.4	T	10
ϕ₀/(°)	30	w₁	0.4
ψ₀/(°)	30	w₂	0.2
h_max/m	400	w₃	0.2
h_min/m	100	w₄	0.2