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

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

Abstract

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

CLC Number:

V249

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.

Figures/Tables 18

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 1

Table 2

Fig.7

Table 3

Table 4

Fig.8

Table 5

Table 6

Fig.9

Fig.10

Fig.11

Fig.12

References 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

Multiple UAV cooperative path planning based on LASSA method

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 18

References 28

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[2]	Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.
[3]	Yang YIN, Quanshun YANG, Zheng WANG, Yang LIU. USV cluster coverage search method with communication distance constraint [J]. Systems Engineering and Electronics, 2022, 44(12): 3821-3828.
[4]	Qingqing YANG, Yingying GAO, Yu GUO, Boyuan XIA, Kewei YANG. Target search path planning for naval battle field based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2022, 44(11): 3486-3495.
[5]	Weiqiang MA, Yongqi GAO, Miao ZHAO. Global-best difference-mutation brain storm optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(1): 270-278.
[6]	Lei LAI, Kun ZOU, Dewei WU, Baozhong LI. Multi-UAV cooperative path planning based on improved MOFA evolution of interactive strategy [J]. Systems Engineering and Electronics, 2021, 43(8): 2282-2289.
[7]	Zhiqiang JIAO, Jieyong ZHANG, Peiyang YAO, Xun WANG, Yichao HE. Distributed evolution method of C4ISR service deployment based on hierarchical structure [J]. Systems Engineering and Electronics, 2021, 43(6): 1572-1585.
[8]	Yi ZHANG, Guowei FANG, Xiuxia YANG. Target tracking method for UAVs formation based on graph Laplacian [J]. Systems Engineering and Electronics, 2021, 43(3): 796-805.
[9]	Wenming WANG, Jialu DU. Agent path planning based on regular hexagon grid JPS algorithm [J]. Systems Engineering and Electronics, 2021, 43(12): 3635-3642.
[10]	Yanan LI, Haibin HUANG, Liangming CHEN, Yufei ZHUANG, Xiaoli WANG. Energy-optimal three-dimensional path planning for AUV under changing ocean current environment [J]. Systems Engineering and Electronics, 2021, 43(12): 3667-3674.
[11]	Wengang LI, Liujiang WANG, Dexiang FANG, Yuwei LI, Jun Huang. Path planning algorithm combining A^* with DWA [J]. Systems Engineering and Electronics, 2021, 43(12): 3694-3702.
[12]	Yao HAN, Shaohua LI. UAV path planning based on improved artificial potential field [J]. Systems Engineering and Electronics, 2021, 43(11): 3305-3311.
[13]	Daidai CHEN, Wanyou LI. Local path planning algorithm for USV with towed cable [J]. Systems Engineering and Electronics, 2020, 42(9): 1988-1994.
[14]	Quanxian ZHANG, Bin ZENG, Houpu LI. Underway replenishment path planning method for distributed naval warfare under the influence of sea conditions [J]. Systems Engineering and Electronics, 2020, 42(10): 2312-2319.
[15]	Sheng GAO, Jianliang AI, Zhihao WANG. Mixed population RRT algorithm for UAV path planning [J]. Systems Engineering and Electronics, 2020, 42(1): 101-107.

UAV序号	航迹代价	航迹长度/km	到达时间/s	协同到达时间/s	协同代价
UAV-1	155.33	181.57	[762.90, 1 335.08]	[877.93, 1 239.70]	550.92
UAV-2	154.26	170.65	[717.03, 1 254.80]
UAV-3	155.88	175.36	[736.81, 1 289.42]