基于LASSA算法的多无人机协同航迹规划方法

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

摘要/Abstract

摘要：

针对基本麻雀搜索算法(sparrow search algorithm, SSA)在求解多无人机(unmanned aerial vehicle, UAV)协同航迹规划问题时收敛精度不高, 易于陷入局部最优等问题, 提出了一种使用对数螺旋策略和自适应步长策略的SSA(logarithmic spiral strategy and adaptive step size strategy of the SSA, LASSA)多UAV协同航迹规划方法。首先利用分层规划思想, 先建立单UAV航迹规划模型, 然后再建立时间协同多UAV航迹规划模型, 将航迹规划问题转化为函数优化问题。其次, 采用对数螺旋策略, 扩大对周围空间的搜索, 增强种群个体多样, 并利用自适应步长策略, 更好地控制开发和探索行为。最后，利用LASSA对提出的航迹规划模型进行求解。仿真结果表明, 本文提出的LASSA能够在满足时间协同的条件下, 规划出代价近似最优、符合约束的协同飞行航迹, 证明了本文提出的基于LASSA的多UAV协同航迹规划方法的有效性和改进算法的优越性。

关键词: 多无人机, 麻雀搜索算法, 对数螺旋策略, 航迹规划, 时间协同

Abstract:

In order to address the problems of low convergence accuracy and easy to fall into local optimum of the basic sparrow search algorithm (SSA) in solving the multiple unmanned aerial vehicle (UAV) cooperative path planning problem, a multiple UAV cooperative path planning method based on the logarithmic spiral strategy and adaptive step size strategy of the SSA (LASSA) is proposed. Firstly, a single UAV path planning model is built using hierarchical planning ideas. Then, a time coordinative multiple UAV path planning model is built to transform the problem into a functional optimization problem. Secondly, a logarithmic spiral strategy is used to expand the search of the surrounding space and enhance the diversity of individuals in the population. And an adaptive step strategy is used to better control exploitation and exploration behaviors. Finally, the proposed path planning model is solved by using LASSA. Simulation results show that the proposed LASSA can find near optimum, constraint-satisfying flight paths while satisfying the time cooperative condition, which proves the effectiveness of the proposed multiple UAV cooperative path planning model and the superiority of the improved algorithm in this paper.

Key words: multiple unmanned aerial vehicle (UAV), sparrow search algorithm (SSA), logarithmic spiral strategy, path planning, time cooperative

中图分类号:

V249

韩统, 汤安迪, 周欢, 徐登武, 谢磊. 基于LASSA算法的多无人机协同航迹规划方法[J]. 系统工程与电子技术, 2022, 44(1): 233-241.

Tong HAN, Andi TANG, Huan ZHOU, Dengwu XU, Lei XIE. Multiple UAV cooperative path planning based on LASSA method[J]. Systems Engineering and Electronics, 2022, 44(1): 233-241.

图/表 18

图1

图2

图3

图4

图5

图6

表1

表2

图7

表3

表4

图8

表5

表6

图9

图10

图11

图12

参考文献 28

1	ZHAO Y , ZHENG Z , LIU Y . Survey on computational-intelligence-based UAV path planning[J]. Knowledge-Based Systems, 2018, 158, 54- 64. doi: 10.1016/j.knosys.2018.05.033
2	沈林成, 陈璟, 王楠. 飞行器任务规划技术综述[J]. 航空学报, 2014, 35 (3): 593- 606.
	SHEN L C , CHEN J , WANG N . A review of mission planning techniques for aircraft[J]. Journal of Aeronautics, 2014, 35 (3): 593- 606.
3	胡中华, 赵敏, 姚敏, 等. 无人机航迹规划技术研究及发展趋势[J]. 航空电子技术, 2009, 40 (2): 24- 29, 36. doi: 10.3969/j.issn.1006-141X.2009.02.006
	HU Z H , ZHAO M , YAO M , et al. Research and development trend of unmanned aircraft trajectory planning technology[J]. Avionics, 2009, 40 (2): 24- 29, 36. doi: 10.3969/j.issn.1006-141X.2009.02.006
4	WU X L , XU L , ZHEN R , et al. Bi-directional adaptive A^* algorithm toward optimal path planning for large-scale UAV under multi-constraints[J]. IEEE Access, 2020, 8, 85431- 85440. doi: 10.1109/ACCESS.2020.2990153
5	MIAO Y F , LUO Z , XIA L S . Application of improved sparse A^* algorithm in UAV path planning[J]. Information Technology Journal, 2013, 12 (17): 4058- 4062. doi: 10.3923/itj.2013.4058.4062
6	程凝怡, 刘志乾, 李昱奇. 一种基于Dijkstra的多约束条件下智能飞行器航迹规划算法[J]. 西北工业大学学报, 2020, 38 (6): 1284- 1290. doi: 10.3969/j.issn.1000-2758.2020.06.018
	CHENG N Y , LIU Z Q , LI Y Q . A Dijkstra-based algorithm for intelligent vehicle trajectory planning under multiple constraints[J]. Journal of Northwestern Polytechnical University, 2020, 38 (6): 1284- 1290. doi: 10.3969/j.issn.1000-2758.2020.06.018
7	KARVE D , KAPADIA F . Multi-UAV path planning using modified Dijkstra's algorithm[J]. International Journal of Computer Applications, 2020, 175 (28): 26- 33. doi: 10.5120/ijca2020920816
8	王伟, 王华. 基于约束人工势场法的弹载飞行器实时避障航迹规划[J]. 航空动力学报, 2014, 29 (7): 1738- 1743.
	WANG W , WANG H . Real-time obstacle avoidance trajectory planning for ballistic vehicles based on constrained artificial potential field method[J]. Journal of Aerodynamics, 2014, 29 (7): 1738- 1743.
9	CHEN Y B , LUO G C , MEI Y S , et al. UAV path planning using artificial potential field method updated by optimal control theory[J]. International Journal of Systems Science, 2016, 47 (6): 1407- 1420. doi: 10.1080/00207721.2014.929191
10	SUN J Y , TANG J , LAO S Y . Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm[J]. IEEE Access, 2017, 5, 18382- 18390. doi: 10.1109/ACCESS.2017.2746752
11	KOTHARI M , POSTLETHWAITE I . A probabilistically robust path planning algorithm for UAVs using rapidly-exploring random trees[J]. Journal of Intelligent and Robotic Systems, 2013, 71 (2): 231- 253. doi: 10.1007/s10846-012-9776-4
12	WU X J , XU L , ZHEN R , et al. Biased sampling potentially guided intelligent bidirectional RRT algorithm for UAV path planning in 3D environment[J]. Mathematical Problems in Engineering, 2019, 2019 (8): 5157403.
13	李文广, 胡永江, 庞强伟, 等. 基于改进遗传算法的多无人机协同侦察航迹规划[J]. 中国惯性技术学报, 2020, 28 (2): 248- 255.
	LI W G , HU Y J , PANG Q W , et al. Cooperative reconnaissance track planning for multiple UAVs based on improved genetic algorithm[J]. Chinese Journal of Inertial Technology, 2020, 28 (2): 248- 255.
14	LIN C E , SYU Y M . GA/DP hybrid solution for UAV multi-target path planning[J]. Journal of Aeronautics Astronautics & Aviation, 2016, 48 (3): 203- 220.
15	PAN J S , LIU N X , CHU S C , et al. A hybrid differential evolution algorithm and its application in unmanned combat aerial vehicle path planning[J]. IEEE Access, 2020, 8, 17691- 17712. doi: 10.1109/ACCESS.2020.2968119
16	YU X , LI C , ZHOU J F . A constrained differential evolution algorithm to solve UAV path planning in disaster scenarios[J]. Knowledge-Based Systems, 2020, 204, 106209. doi: 10.1016/j.knosys.2020.106209
17	XU C F , DUAN H B , LIU F , et al. Chaotic artificial bee colony approach to uninhabited combat air vehicle (UCAV) path planning[J]. Aerospace Science and Technology, 2010, 14 (8): 535- 541. doi: 10.1016/j.ast.2010.04.008
18	DING L , WU H , YAO Y , et al. UAV path planning by probability-scaling adaptive chaotic artificial bee colony algorithm[J]. Journal of Computational Information Systems, 2015, 11 (11): 4135- 4143.
19	黄长强, 赵克新. 基于改进蚁狮算法的无人机三维航迹规划[J]. 电子与信息学报, 2018, 40 (7): 1532- 1538.
	HUANG C Q , ZHAO K X . Improved ant-lion algorithm-based 3D trajectory planning for UAVs[J]. Journal of Electronics and Information, 2018, 40 (7): 1532- 1538.
20	YAO P , WANG H L . Dynamic adaptive ant lion optimizer applied to route planning for unmanned aerial vehicle[J]. Soft Computing: a Fusion of Foundations, Methodologies and Applications, 2017, 21 (18): 5475- 5488.
21	DEWANGAN R K , SHUKLA A , GODFREY W W . Three-dimensional path planning using Grey wolf optimizer for UAVs[J]. Applied Intelligence, 2019, 49 (6): 2201. doi: 10.1007/s10489-018-1384-y
22	单文昭, 崔乃刚, 黄蓓, 等. 基于PSO-HJ算法的多无人机协同航迹规划方法[J]. 中国惯性技术学报, 2020, 28 (1): 122- 128.
	SHAN W Z , CUI N G , HUANG B , et al. Multiple UAV cooperative path planning based on PSO-HJ method[J]. Journal of Chinese Inertial Technology, 2020, 28 (1): 122- 128.
23	徐瑞莲, 周新志, 宁芊. 基于改进差分进化算法的多无人机航迹规划[J]. 火力与指挥控制, 2020, 45 (1): 169- 173, 179. doi: 10.3969/j.issn.1002-0640.2020.01.034
	XU R L , ZHOU X Z , YU Q . Multi-UAV trajectory planning based on improved differential evolutionary algorithm[J]. Firepower and Command Control, 2020, 45 (1): 169- 173, 179. doi: 10.3969/j.issn.1002-0640.2020.01.034
24	MIAO H . Dynamic robot path planning using an enhanced simulated annealing approach[J]. Applied Mathematics & Computation, 2013, 222 (5): 420- 437.
25	XUE J , SHEN B . A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science & Control Engineering: an Open Access Journal, 2020, 8 (1): 22- 34.
26	汤安迪, 韩统, 徐登武, 等. 基于混沌麻雀搜索算法的无人机航迹规划方法[EB/OL]. [2021-01-16]. http://kns.cnki.net/kcms/detail/51.1307.TP.20201124.1519.002.html.
	TANG A D, HAN T, XU D W, et al. An approach to UAV trajectory planning based on chaotic sparrow search algorithm[EB/OL]. [2021-01-16]. http://kns.cnki.net/kcms/detail/51.1307.TP.20201124.1519.002.html.
27	MIRJALILI S , LEWIS A . The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95, 51- 67. doi: 10.1016/j.advengsoft.2016.01.008
28	ZHAO W G , ZHANG Z X , WANG L Y . Manta ray foraging optimization: an effective bio-inspired optimizer for engineering applications[J]. Engineering Applications of Artificial Intelligence, 2020, 87 (1): 103300.

威胁源	威胁类型	位置/km	作用半径/km	高度/km
威胁1	探测雷达	(35, 20)	13	2.8
威胁2	地空导弹	(35, 52)	8	2.9
威胁3	防空高炮	(52, 72)	8	3.0
威胁4	地空导弹	(63, 45)	10.7	2.9
威胁5	探侧雷达	(78, 78)	9	3.1
威胁6	防空高炮	(87, 45)	7	3.0

算法	平均值	最优值	最差值	标准差	平均耗时/s
SSA	3 726.887	206.985 1	30 320.39	7 484.872	34.870 64
CSSA	218.318 3	188.713 0	224.171 0	5.939 384	31.713 61
LASSA	201.291 5	185.788 6	221.981 2	12.883 96	16.587 74

UAV序号	平均值	最优值	最差值	标准差
UAV-1	1.48E+02	1.47E+02	1.54E+02	1.40E+00
UAV-2	1.54E+02	1.53E+02	1.55E+02	5.86E-01
UAV-3	1.54E+02	1.52E+02	1.64E+02	2.75E+00

UAV序号	航迹代价	航迹长度/km	到达时间/s	协同到达时间/s	协同代价
UAV-1	147.74	163.54	[687.16, 1 202.52]	[725.93, 1 202.52]	546.50
UAV-2	153.90	168.30	[707.13, 1 237.47]
UAV-3	152.96	172.77	[725.93, 1 270.38]

UAV序号	平均值	最优值	最差值	标准差
UAV-1	1.65E+02	1.48E+02	1.83E+02	1.64E+01
UAV-2	1.63E+02	1.54E+02	1.94E+02	1.43E+01
UAV-3	1.70E+02	1.55E+02	1.94E+02	1.50E+01