UAV Swarm On-line Mission Planning Method Based on Dynamic Allocation Strategy

doi:10.12382/bgxb.2022.0247

Abstract

Abstract:

A distributed online mission planning method based on a dynamic alliance strategy is proposed to deal withthe complex problems of high dynamics, strong uncertainty, and multiple constraints of UAV swarm mission planning in a complex battlefield environment. Firstly, the typical scenarios of UAV swarm dynamic mission planning are described, and the mathematical model of multi-constraint distributed mission planning ofthe heterogeneous UAV swarm is established. Secondly, a task alliance formation strategy considering the dynamic topological constraints of the UAV swarm is designed, and an improved ant colony algorithm coupled with Dubins path planning is proposed to realize the online solution of dynamic mission planning with multiple constraints and strong uncertainties. Finally, typical task simulation scenarios of theheterogeneous UAV swarm is constructed, and the effectiveness of the proposed strategy and algorithm is verified by digital simulations and virtual-real semi-physical simulations.The results show that the proposed method can achieve better system performance with less loss of mission completion time in the dynamic mission planning process, which is of some significance for further research work towards engineering applications.

Key words: UAV, swarm system, mission alliance, mission planning, one-line algorithm

CLC Number:

V249

WANG Mengyang, ZHANG Dong, TANG Shuo, XU Bin, ZHAO Junmin. UAV Swarm On-line Mission Planning Method Based on Dynamic Allocation Strategy[J]. Acta Armamentarii, 2023, 44(8): 2207-2223.

Figures/Tables 18

References 29

[1]	贾永楠, 田似营, 李擎. 无人机集群研究进展综述[J]. 航空学报, 2020, 41(增刊1): 4-14.
	JIA Y N, TIAN S Y, LI Q. Recent development of unmanned aerial vehicle swarms[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S1): 4-14. (in Chinese)
[2]	NIU W, HUANG J Q, MIU L F. Research on the concept and key technologies of unmanned aerial vehicle swarm concerning naval attack[J]. Command Control & Simulation, 2018, 40(1): 20-27.
[3]	MAVROVOUNIOTIS M, LI C, YANG S. A survey of swarm intelligence for dynamic optimization: algorithms and applications[J]. Swarm and Evolutionary Computation, 2017, 33: 1-17. doi: 10.1016/j.swevo.2016.12.005 URL
[4]	甄子洋, 江驹, 孙绍山, 等. 无人机集群作战协同控制与决策[M]. 北京: 国防工业出版社, 2022: 1-35.
	ZHEN Z Y, JIANG J, SUN S S, et al. Cooperative control and decision of UAV operations[M]. Beijing: National Defense Industry Press, 2022: 1-35. (in Chinese)
[5]	贾高伟, 王建峰. 无人机集群任务规划方法研究综述[J]. 系统工程与电子技术, 2019, 43(1): 99-111.
	JIA G W, WANG J F. Research review of UAV swarm mission planning method[J]. Systems Engineering and Electronics, 2021, 43(1): 99-111. (in Chinese)
[6]	DHEIN G, NETO A F K, DE ARAÚJO O C B. The multiple traveling salesman problem with backup coverage[J]. Electronic Notes in Discrete Mathematics, 2018, 66: 135-142. doi: 10.1016/j.endm.2018.03.018 URL
[7]	MINH A N, GIANG T D, MINH H H, et al. The mincost parallel drone scheduling vehicle routing problem[J]. European Journal of Operational Research, 2021, 229(3): 910-930.
[8]	AFONSO R, MAXIMO M, GALVĀO R. Task allocation and trajectory planning for multiple agents in the presence of obstacle and connectivity constraints with mixed-integer linear programming[J]. International Journal of Robust and Nonlinear Control, 2020, 30(14): 5464-5491. doi: 10.1002/rnc.v30.14 URL
[9]	KONG X Q, LU N, LI B. Optimal scheduling for unmanned aerial vehicle networks with flow-level dynamics[J]. IEEE Transactions on Mobile Computing, 2021, 20(3): 1186-1197. doi: 10.1109/TMC.7755 URL
[10]	朱云冲, 梁彦刚, 黎克波, 等. 基于PSO和RRT的智能弹群任务分配算法[J/OL]. 航空学报, 2022.(2022-07-12) [2022-08-22]. http://kns.cnki.net/kcms/detail/11.1929.V.20220710.1634.028.html
	ZHU Y C, LIANG Y G, LI K B, et al. Algorithm to solve the task assignment problem of intelligent missile swarm based on PSO and RRT[J/OL]. Acta Aeronautica et Astronautica Sinica, 2022. (2022-07-12) [2022-08-22]. http://kns.cnki.net/kcms/detail/11.1929.V.20220710.1634.028.htmlin Chinese)
[11]	李桂亮, 毕海洋, 洪雪健, 等. 基于DE-DPSO-GT-SA算法的协同多任务分配[J]. 北京航空航天大学学报, 2021, 47(1): 90-96.
	LI G L, BI H Y, HONG X J, et al. Cooperative multi-task assignment based on DE-DPSO-GT-SA algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(1): 90-96. (in Chinese)
[12]	CHEN Y B, YANG D, YU J Q. Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm[J]. IEEE Transactions on Aerospace and Electronic Systems, 2018, 54(6): 2853-2872. doi: 10.1109/TAES.2018.2831138 URL
[13]	WANG Z, LIU L, LONG T, et al. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition based genetic algorithm with double-chromosome encoding[J]. Chinese Journal of Aeronautics, 2018, 31(2): 339-350. doi: 10.1016/j.cja.2017.09.005 URL
[14]	JIA Z Y, YU J Q, AI X L, et al. Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm[J]. Aerospace Science and Technology, 2018, 76: 112-125. doi: 10.1016/j.ast.2018.01.025 URL
[15]	XIA C, LIANG Y T, YUAN L Y, et al. Cooperative task assignment and track planning for multi-UAV attack mobile targets[J]. Journal of Intelligent & Robotic Systems, 2020, 100(3): 1383-1400.
[16]	WANG J Q, ZHANG M X, SONG H H, et al. Improvement and application of hybrid firefly algorithm[J]. IEEE Access, 2019, 7: 165458-165477. doi: 10.1109/ACCESS.2019.2952468
[17]	WANG M, MA T M, LI G L, et al. Ant colony optimization with an improved pheromone model for solving MTSP with capacity and time window constraint[J]. IEEE Access, 2020, 8: 106872-106879. doi: 10.1109/Access.6287639 URL
[18]	KIM K S, KIM H Y, CHOI H L. A bid-based grouping method for communication-efficient decentralized multi-UAV task allocation[J]. International Journal of Aeronautical and Space Sciences, 2020, 21(1): 290-302. doi: 10.1007/s42405-019-00205-1
[19]	SUJIT P, GEORGE J, BEARD R. Multiple UAV task allocation using particle swarm optimization[C]// Proceedings of AIAA Guidance, Navigation and Control Conference and Exhibit. Honolulu, HI, US:AIAA, 2008: 6837.
[20]	刘重, 高晓光, 符小卫, 等. 未知环境下异构多无人机协同搜索打击中的联盟组建[J]. 兵工学报, 2015, 36(12): 2284-2297. doi: 10.3969/j.issn.1000-1093.2015.12.011
	LIU Z, GAO X G, FU X W, et al. Coalition formation of multiple heterogeneous unmanned aerial vehicles in cooperative search and attack in unknown environment[J]. Acta Armamentarii, 2015, 36(12): 2284-2297. (in Chinese)
[21]	符小卫, 魏可, 李斌, 等. 基于联盟的无人机集群编队控制方法[J]. 系统工程与电子技术, 2019, 41(11): 2559-2572.
	FU X W, WEI K, LI B, et al. Formation control method of UAV cluster based on alliance[J]. Systems Engineering and Electronics, 2019, 41(11): 2559-2572. (in Chinese)
[22]	ZHEN Z Y, WEN L D, WANG B L, et al. Improved contract network protocol algorithm based cooperative target allocation of heterogeneous UAV swarm[J]. Aerospace Science and Technology, 2021, 119(6): 107054. doi: 10.1016/j.ast.2021.107054 URL
[23]	SUJIT P B, MANATHARA J G, GHOSE D, et al. Decentralized multi-UAV coalition formation with limited communication ranges[M]. VALAVANIS K P, VACHTSEVANOS G J. Handbook of unmanned aerial vehicles. Dordrecht, the Netherlands: Springer, 2014: 2021-2048.
[24]	陈璞, 严飞, 刘钊, 等. 通信约束下异构多无人机任务分配方法[J]. 航空学报, 2021, 42(8): 313-326.
	CHEN P, YAN F, LIU Z, et al. Heterogeneous unmanned aerial vehicles task allocation with communication constraints[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42(8): 313-326. (in Chinese)
[25]	DENG Q B, YU J Q, WANG N F. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes[J]. Chinese Journal of Aeronautics, 2013, 26(5): 1238-1250. doi: 10.1016/j.cja.2013.07.009 URL
[26]	WU W N, WANG X G, CUI N G. Fast and coupled solution for cooperative mission planning of multiple heterogeneous unmanned aerial vehicles[J]. Aerospace Science and Technology, 2018, 79: 131-144. doi: 10.1016/j.ast.2018.05.039 URL
[27]	吴钟博, 易建强. 无人机编队支撑网络的协同通信中继策略[J]. 航空学报, 2020, 41(增刊2): 187-194.
	WU Z B, YI J Q. Cooperative communication relay selection method for UAV formation support networks[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S2): 187-194. (in Chinese)
[28]	陈清阳, 辛宏博, 王玉杰, 等. 一种多机协同打击的快速航迹规划方法[J]. 北京航空航天大学学报, 2019, 48(7):1145-1153.
	CHEN Q Y, XIN H B, WANG Y J, et al. A rapid path planning method for multiple UAVs to cooperative strike[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 48(7):1145-1153. (in Chinese)
[29]	苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配[J]. 航空学报, 2008, 29(增刊): 184-191.
	SU F, CHEN Y, SHEN L C. UAV cooperative multi-task assignment based on ant colony algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2008, 29(S):184-191. (in Chinese)

UAV 编号	初始位置/m	最大航程/m	飞行速度/ (m·s^-1)	任务能力	打击载荷数量
U₁	(2200,2000,300)	18000	50	(R,S,E)	2
U₂	(4000,1900,300)	18000	50	(R,S,E)	2
U₃	(2500,5000,300)	18000	50	(R,S,E)	2
U₄	(3000,5500,300)	18000	50	(R,S,E)	2
U₅	(4000,4000,300)	18000	50	(R,S,E)	2
U₆	(5000,4500,300)	18000	50	(R,S,E)	2
U₇	(6500,3000,300)	18000	50	(R,S,E)	1
U₈	(5800,2300,300)	18000	50	(R,S,E)	1
U₉	(5200,3800,300)	18000	50	(R,S,E)	1
U₁₀	(6700,4200,300)	18000	50	(R,S,E)	1
U₁₁	(5500,2000,300)	18000	50	(R,S,E)	1
U₁₂	(5000,1000,500)	26000	60	(S)	4
U₁₃	(1000,1000,500)	26000	60	(S)	4
U₁₄	(6000,6000,500)	26000	60	(S)	4
U₁₅	(5900,6500,500)	26000	60	(S)	4
U₁₆	(2800,2000,500)	26000	60	(S)	4
U₁₇	(1600,1600,500)	26000	60	(S)	4
U₁₈	(3000,3050,500)	26000	60	(S)	4
U₁₉	(2500,2800,500)	26000	60	(S)	4
U₂₀	(5600,5800,500)	26000	60	(S)	4
U₂₁	(1800,3550,500)	26000	60	(S)	4
U₂₂	(2800,2100,500)	26000	60	(S)	4
U₂₃	(6000,2000,400)	20000	50	(R,E)	0
U₂₄	(1000,2000,400)	20000	50	(R,E)	0
U₂₅	(8000,7000,400)	20000	50	(R,E)	0
U₂₆	(1500,3800,400)	20000	50	(R,E)	0
U₂₇	(3000,4500,400)	20000	50	(R,E)	0
U₂₈	(3000,2800,400)	20000	50	(R,E)	0
U₂₉	(2800,4000,400)	20000	50	(R,E)	0
U₃₀	(3800,2100,400)	20000	50	(R,E)	0
U₃₁	(2200,2500,400)	20000	50	(R,E)	0
U₃₂	(2800,1800,400)	20000	50	(R,E)	0

UAV 编号	初始位置/m	最大航程/m	飞行速度/ (m·s^-1)	任务能力	打击载荷数量
U₁	(2200,2000,300)	18000	50	(R,S,E)	2
U₂	(4000,1900,300)	18000	50	(R,S,E)	2
U₃	(2500,5000,300)	18000	50	(R,S,E)	2
U₄	(3000,5500,300)	18000	50	(R,S,E)	2
U₅	(4000,4000,300)	18000	50	(R,S,E)	2
U₆	(5000,4500,300)	18000	50	(R,S,E)	2
U₇	(6500,3000,300)	18000	50	(R,S,E)	1
U₈	(5800,2300,300)	18000	50	(R,S,E)	1
U₉	(5200,3800,300)	18000	50	(R,S,E)	1
U₁₀	(6700,4200,300)	18000	50	(R,S,E)	1
U₁₁	(5500,2000,300)	18000	50	(R,S,E)	1
U₁₂	(5000,1000,500)	26000	60	(S)	4
U₁₃	(1000,1000,500)	26000	60	(S)	4
U₁₄	(6000,6000,500)	26000	60	(S)	4
U₁₅	(5900,6500,500)	26000	60	(S)	4
U₁₆	(2800,2000,500)	26000	60	(S)	4
U₁₇	(1600,1600,500)	26000	60	(S)	4
U₁₈	(3000,3050,500)	26000	60	(S)	4
U₁₉	(2500,2800,500)	26000	60	(S)	4
U₂₀	(5600,5800,500)	26000	60	(S)	4
U₂₁	(1800,3550,500)	26000	60	(S)	4
U₂₂	(2800,2100,500)	26000	60	(S)	4
U₂₃	(6000,2000,400)	20000	50	(R,E)	0
U₂₄	(1000,2000,400)	20000	50	(R,E)	0
U₂₅	(8000,7000,400)	20000	50	(R,E)	0
U₂₆	(1500,3800,400)	20000	50	(R,E)	0
U₂₇	(3000,4500,400)	20000	50	(R,E)	0
U₂₈	(3000,2800,400)	20000	50	(R,E)	0
U₂₉	(2800,4000,400)	20000	50	(R,E)	0
U₃₀	(3800,2100,400)	20000	50	(R,E)	0
U₃₁	(2200,2500,400)	20000	50	(R,E)	0
U₃₂	(2800,1800,400)	20000	50	(R,E)	0

目标编号	初始位置/m	待执行任务列表	侦察时间/s
1	(3500,2800,1)	(R, S, E)	20
2	(1000,500,1)	(R, S, E)	30
3	(4500,5000,1)	(R, S, E)	30

目标编号	初始位置/m	待执行任务列表	侦察时间/s
1	(3500,2800,1)	(R, S, E)	20
2	(1000,500,1)	(R, S, E)	30
3	(4500,5000,1)	(R, S, E)	30