A hybrid evolutionary algorithm integrated with specific neighborhood search for collaborative task planning of heterogeneous multi-UAVs under SEAD scenarios
Restricted accessResearch articleFirst published online April, 2025
A hybrid evolutionary algorithm integrated with specific neighborhood search for collaborative task planning of heterogeneous multi-UAVs under SEAD scenarios
To overcome the challenges posed by diversified task combinations and strict temporal constraints in the Suppression of Enemy Air Defenses (SEAD), this paper investigates the task planning problem. The task correlation in SEAD evolves from chained correlations within individual units to a web of interdependencies across all UAVs, making the task planning problem significantly more complex than traditional vehicle routing problems. This complexity ensures that any alteration to a single task will produce a cascading effect on the overall plan. To address this issue, the paper designs a matrix-based task dependency analysis method that quantitatively evaluates the logical interdependencies between tasks. Additionally, the concept of dynamic time windows is introduced to precisely measure the temporal impact of task adjustments on the overall plan. On the basis of these analyses, an adaptive hybrid evolutionary algorithm is designed, which employs a neighborhood search strategy to precisely adjust task assignments and execution sequences based on task dependencies and dynamic time windows. Finally, simulation results suggest that the algorithm proposed in this paper consistently produces task plans with a high number of completed tasks and short completion time across scenarios involving varying task quantities, task combinations, time windows, regional distributions, and UAV configurations.
Jialong ZhangKHZhangPUHouZ, et al.A survey on joint-operation application for unmanned swarm formations under a complex confrontation environment. J Syst Eng Electron2023; 34(6): 1432–1446.
2.
WuYLiangTGouJ, et al.Heterogeneous mission planning for multiple UAV formations via metaheuristic algorithms. IEEE Trans Aero Electron Syst2023; 59: 1–16.
DuYHWLingXingLN. Intelligent planning technologies for unmanned aerospace system: a literature review. J Syst Eng2020; 35(3): 416–432.
5.
TangJChenXZhuX, et al.Dynamic reallocation model of multiple unmanned aerial vehicle tasks in emergent adjustment scenarios. IEEE Trans Aero Electron Syst2023; 59(2): 1139–1155.
6.
WangYRuZYWangK, et al.Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing. IEEE Trans Cybern2020; 50(9): 3984–3997.
7.
YeFChenJTianY, et al.Cooperative multiple task assignment of heterogeneous UAVs using a modified genetic algorithm with multi-type-gene chromosome encoding strategy. J Intell Rob Syst2020; 100(2): 615–627.
8.
XiaCLiuYYinL, et al.Cooperative task assignment and track planning for multi-UAV attack mobile targets. J Intell Rob Syst2020; 100(3): 1383–1400.
9.
LiDSuHXuX, et al.Cooperative task scheduling and planning considering resource conflicts and precedence constraints. Int J Precis Eng Manuf2023; 24(9): 1503–1516.
10.
ZhangLZhaoJLamonE, et al. Energy efficient multi-robot task allocation constrained by time window and precedence. IEEE Trans Autom Sci Eng. 2023; 9: 1–12.
11.
NunesEMannerMMiticheH, et al.A taxonomy for task allocation problems with temporal and ordering constraints. Robot Autonom Syst2017; 90: 55–70.
12.
XuGLongTWangZ, et al.Target-bundled genetic algorithm for multi-unmanned aerial vehicle cooperative task assignment considering precedence constraints. Proc Inst Mech Eng G J Aerosp Eng2020; 234(3): 760–773.
13.
ZhangRFengYYangY, et al.A deadlock-free hybrid estimation of distribution algorithm for cooperative multi-UAV task assignment with temporally coupled constraints. IEEE Trans Aero Electron Syst2022: 1–17.
14.
LinJCJiaGWHouZX. Research on task assignment of heterogeneous UAV formation in the anti-radar combat. Syst Eng Electron2018; 40(9): 1986–1992.
15.
WangASubramanyamAGounarisCE. Robust vehicle routing under uncertainty via branch-price-and-cut. Optim Eng2021; 23: 1895–1948.
16.
KimYGuDWPostlethwaitI. Real-time optimal mission scheduling and flight path selection. IEEE Trans Automat Control2007; 52: 1119–1123.
17.
PeiZFangTWengK, et al.Urban on-demand delivery via autonomous aerial mobility: formulation and exact algorithm. IEEE Trans Autom Sci Eng2023; 20: 1675–1689.
18.
NguyenMPKGunawanAYuVF, et al.An adaptive large neighborhood search for heterogeneous vehicle routing problem with time windows[C]. In: 2023 IEEE 19th international conference on automation science and engineering (CASE), Auckland, New Zealand, 26-30 August 2023, 2023, pp. 1–6.
19.
HuCLuJLiuX, et al.Robust vehicle routing problem with hard time windows under demand and travel time uncertainty. Comput Oper Res2018; 94: 139–153.
20.
ZengFShirafujiSFanC, et al.Stepwise large-scale multi-agent task planning using neighborhood search. IEEE Rob Autom Lett2024; 9(1): 111–118.
21.
TangJDuanHLaoS. Swarm intelligence algorithms for multiple unmanned aerial vehicles collaboration: a comprehensive review. Artif Intell Rev2023; 56(5): 4295–4327.
ZhenZZhuPXueY, et al.Distributed intelligent self-organized mission planning of multi-UAV for dynamic targets cooperative search-attack. Chin J Aeronaut2019; 32(12): 2706–2716.
24.
KoçÇBektaşTJabaliO, et al.A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows. Comput Oper Res2015; 64: 11–27.
25.
ChenYYangDYuJ. Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-Part Wolf pack search algorithm. IEEE Trans Aero Electron Syst2018; 54(6): 2853–2872.
26.
DuanHZhaoJDengY, et al.Dynamic discrete pigeon-inspired optimization for multi-UAV cooperative search-attack mission planning. IEEE Trans Aero Electron Syst2021; 57(1): 706–720.
27.
ZhangAYangMBiWH, et al.Task allocation of heterogeneous multi-UAV in uncertain environment based on multiple strategies GWO[J]. Acta Aeronautica Astronautica Sinica, 2022; 44: 327115.
28.
WangXWangHZhangH, et al.A mini review on UAV mission planning. J Ind Manag Optim2022; 19.
29.
YaoWQiNWanN, et al.An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles. Aero Sci Technol2019; 86: 455–464.
30.
YanFZhuXPZhouZ, et al.Real-time task allocation for a heterogeneous multi-UAV simultaneous attack. Sci Sin Inform2019; 49(5): 555–569.
31.
WuWXuJSunY. Integrate assignment of multiple heterogeneous unmanned aerial vehicles performing dynamic disaster inspection and validation task with Dubins path. IEEE Trans Aero Electron Syst2023; 59: 1–20.
32.
SchwarzrockJZacariasIBazzanALC, et al.Solving task allocation problem in multi Unmanned Aerial Vehicles systems using Swarm intelligence. Eng Appl Artif Intell2018; 72: 10–20.
33.
GengNMengQGongD, et al.How good are distributed allocation algorithms for solving urban search and rescue problems? A comparative study with centralized algorithms. IEEE Trans Autom Sci Eng2019; 16(1): 478–485.
34.
GaoKYangFZhouM, et al.Flexible job-shop rescheduling for new job insertion by using discrete jaya algorithm. IEEE Trans Cybern2019; 49(5): 1944–1955.
35.
JiaZYuJAiX, et al.Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm. Aero Sci Technol2018; 76: 112–125.
36.
LiuJWangQXuY, et al.A novel distributed method for time-critical task allocation problems in multi-UAV system[C]. In: IEEE International Conference on Communications, Montreal, QC, Canada, 14-23 June 2021: 1–6.
37.
CampuzanoGObrequeCAguayoMM. Accelerating the Miller–Tucker–Zemlin model for the asymmetric traveling salesman problem. Expert Syst Appl2020; 148: 113229.
38.
MunariPMorenoAVegaJDL, et al.The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method. Transport Sci2019; 53(4): 1043–1066.
ChenZAlonso-MoraJBaiX, et al.Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Rob Autom Lett2021; 6(3): 5816–5823.
41.
LiXLiPZhaoY, et al.A hybrid large neighborhood search algorithm for solving the multi depot UAV swarm routing problem. IEEE Access2021; 9: 104115–104126.
42.
ZhangJMLiuZShiJ, et al.Weapon configuration,allocation and route planning with time windows for multiple unmanned combat air vehicles. J Syst Eng Electron2018; 29(5): 953–968.
