Robust Optimization for Cooperative Task Assignment of Heterogeneous Unmanned Aerial Vehicles with Time Window Constraints

Abstract

The cooperative task assignment problem with time windows for heterogeneous multiple unmanned aerial vehicles is an attractive complex combinatorial optimization problem. In reality, unmanned aerial vehicles’ fuel consumption exhibits uncertainty due to environmental factors or operational maneuvers, and accurately determining the probability distributions for these uncertainties remains challenging. This paper investigates the heterogeneous multiple unmanned aerial vehicle cooperative task assignment model that incorporates time window constraints under uncertain environments. To model the time window constraints, we employ the big-M method. To address the uncertainty in fuel consumption, we apply an adjustable robust optimization approach combined with duality theory, which allows us to derive the robust equivalent form and transform the model into a deterministic mixed-integer linear programming problem. We conduct a series of numerical experiments to compare the optimization results across different objectives, including maximizing task profit, minimizing total distance, minimizing makespan, and incorporating three different time window constraints. The numerical results demonstrate that the robust optimization-based heterogeneous multiple unmanned aerial vehicle cooperative task assignment model effectively mitigates the impact of parameter uncertainty, while achieving a balanced trade-off between robustness and the optimality of task assignment objectives.

1. Introduction

1.1. Background and Motivation

Unmanned aerial vehicles (UAVs) are increasingly vital for missions such as suppression of enemy air defenses (SEAD) due to their flexibility, low cost, and operational efficiency. As the number and complexity of missions increases, teams of heterogeneous UAVs, each with specialized capabilities, offer significant advantages over single UAVs. UAV teams can efficiently perform tasks in hazardous environments, reducing operational costs, thereby significantly improving overall mission success rates. As UAVs have wide applications, task assignment for UAVs in complex environments becomes crucial. UAV task assignment research has evolved significantly since the late 1990s, expanding from single-UAV mission planning to multi-UAV cooperative task allocation. Key research areas include task assignment models [1], algorithms, uncertainty handling [2], constraints, and application scenarios.

The cooperative task assignment problem (CTAP) for UAVs is a critical aspect of modern military operations, particularly in scenarios involving complex electromagnetic environments and advanced weapon systems [3,4]. Effective cooperative task assignment involves making mission decisions for multi-UAVs in order to achieve a certain optimization objective under the condition of meeting the operational requirements [5]. Despite the computational challenges it presents, the CTAP has garnered significant attention from both academic researchers and industry practitioners due to its practical importance [6,7].

Sometimes it is necessary to consider additional constraints in the CTAP: UAVs must arrive at the target within a specified time interval, known as the time window, to perform the corresponding task. Specifically, if a UAV arrives before the start of the time window, the task cannot be performed until the time window opens. Moreover, any arrival after the time window closes or the deadline passes is not permitted. Furthermore, the CTAP for multi-UAVs is typically formulated with respect to specific constraints or objectives that reflect the real-world task scenarios [8]. For instance, tasks should be executed in a specific sequence, which is not easy to characterize. In a deterministic setting, Schumacher et al. [9] established the first mixed-integer linear programming (MILP) formulation for the cooperative task assignment problem with time windows (CTAPTW), in which a fleet of UAVs is assigned to complete three tasks for each target while satisfying task sequence requirements and time window constraints. These constraints are influenced not only by the limited resources but also by the diversity of task requirements and the complexity of the operational environment. In the former problem, a fleet of homogenenous UAVs setting off from the base perform task assignment and path optimization to achieve combat missions. However, in real-world combat environments, the cooperation of heterogeneity of UAVs, that is, different types of UAVs perform different types of tasks, brings more constraints to the CTAPTW [10].

In the multi-UAV CTAPTWs, the existence of uncertain parameters is a major challenge due to unknown environments or incomplete information. From a modeling perspective, ignoring these uncertainties in practical applications results in solutions that are either infeasible or sub-optimal, which may undermine combat effectiveness and result in mission failure. Therefore, methods to eliminate uncertainty in the multi-UAV CTAPTW are essential. Since the CTAPTW is already NP-hard, introducing uncertainty would further increase the computational complexity of solving the problem. Most of the existing research on the multi-UAV CTAP focuses on the deterministic conditions [11] without considering the reliability of the assignment results. Therefore, it is necessary to study the robustness of assignment results to achieve reliable task assignment.

1.2. Literature Review

The multi-UAV CTAP involves the global coordination of the environment, task requirements, and UAV resources. A well-designed method for the multi-UAV CTAP can significantly enhance the efficiency of task completion. Currently, the deterministic CTAP has been extensively studied in academic research. Shima et al. [12] proposed a genetic algorithm for the multi-agent task assignment problem, effectively addressing its NP-hard nature by incorporating scenario-specific requirements such as task precedence, coordination, timing constraints, and feasible trajectories, which are challenging for traditional combinatorial optimization methods. Compared with the literature [12], which studied the CTAP for homogeneous UAVs, this paper and some other literature focus on assigning heterogeneous UAVs to perform different kinds of tasks. Ye et al. [13] aimed to study the CTAP problem, in which multi-heterogeneous fixed-wing UAVs were assigned to several stationary ground targets to perform a suppression of enemy air defense mission, which was solved by an adaptive genetic algorithm under the premise of considering the heterogeneity of UAVs and mission coupling constraints. Zhao et al. [14] proposed a CTAP with target precedence constraints model, which considers not only the kinematic, resource, and task precedence constraints of UAVs but also target precedence, and develops a modified genetic algorithm integrating a graph-based method and the waitable path coordination algorithm to solve the resulting problem. Most of the studies [15,16,17] were aimed at the algorithm design under a deterministic decision environment addressing the issue of solving scale and efficiency, while uncertainty research is lacking.

This paper addresses the problem of the multi-UAV CTAP under uncertain conditions. The uncertainty in the UAV reconnaissance environment is multifaceted, with a primary focus on fuel consumption, which can be influenced by environmental factors such as air pressure, temperature, atmospheric density, wind direction, rain, snow, and lightning, as well as by UAV maneuvers such as speed, altitude, dive, jump, and turn. In comparison, Naderi et al. [18] developed a hybrid algorithm oriented to a shuffled frogleaping algorithm and particle swarm optimization to solve multi-objective optimal power flow, taking into account multi-fuel constraints without considering uncertainty. However, these uncertainties can significantly affect the mission planning of the entire multi-UAVs system. If such uncertainties are not considered, the quality of mission completion may deteriorate. Therefore, incorporating the uncertainty of UAV fuel consumption due to environmental factors or maneuvering is crucial for accurately evaluating and optimizing the performance of the multi-UAV CTAP. Common approaches to handle uncertainty include stochastic programming, fuzzy programming, and robust optimization [19]. Stochastic programming and fuzzy programming rely on the assumption that the estimated probability distributions of uncertain parameters must closely match the actual ones, which treats the uncertain variable as a random variable. Various models and algorithms have been proposed in the literature to address the uncertainty of parameters in the CTAP. In [20], the cross-entropy method, a versatile stochastic optimization technique, was applied to solve the CTAP, and the branch and bound algorithm, a classical global optimization method, was used to evaluate the quality of the cross-entropy approach. Hu et al. [21] proposed a novel task assignment approach based on the stochastic multicriteria acceptability analysis method to address the fact that many criteria values are random or fuzzy and their weights are imprecisely known. A simheuristic approach combining a genetic algorithm with Monte Carlo simulation was proposed in [22], considering the randomness of both travel and service times at each node, as commonly encountered in real-life applications. Jia et al. [23] proposed a two-stage stochastic programming model for heterogeneous UAVs with random velocity and time windows, solving it with a new meta-heuristic algorithm based on an improved genetic algorithm for efficiency. In contrast, He et al. [24] developed a similar model with recourse costs, using a fixed-sample Monte Carlo simulation and a variable neighborhood search algorithm to handle uncertainty. As another powerful tool to deal with uncertainty, fuzzy programming also has a wide range of applications. Huang et al. [25] constructed the fuzzy multiconstraint programming model for heterogeneous multi-UAV dynamic task assignment based on binary interval theory, taking into account the effects of uncertain factors. Meanwhile, in [26], the use of comprehensive learning particle swarm optimization and differential evolution as a hybrid configuration in a fuzzy framework, called hybrid fuzzy-based improved comprehensive learning particle swarm optimization-differential evolution, was explored to address an optimal active power dispatch problem.

However, the stochastic programming method and fuzzy programming method both rely on a crucial assumption: the true distribution of uncertain parameters must be known or estimated. If this assumption holds true and the reformulation of the uncertain optimization problem is computationally feasible, the stochastic programming or fuzzy programming method can be applied to solve the optimization problem. Meanwhile, two key issues must be considered to address the challenges in accurately determining UAV fuel consumption probability distributions: limited historical data and the impact of disturbances. The scarcity of flight data under varied conditions hinders the creation of accurate models, while disturbances like weather changes and mechanical variations introduce further uncertainty, complicating the estimation process. These factors make it difficult to establish reliable and stable probability distributions for fuel consumption. Meanwhile, some scholars [27] found that the robust optimization model is capable of producing a near-optimal solution, similar to that of the stochastic programming model, by appropriately adjusting a parameter that governs the degree of conservatism in decision-making. Furthermore, the robust optimization model is significantly easier to solve compared to the stochastic programming model and offers the advantage of minimizing the worst-case scenario of the decision outcomes. In contrast to the existing literature, our study is based on the premise of unknown probability distribution information [28], thereby avoiding the need to make the strong assumption of a fixed distribution.

In combat scenarios, the optimization problem requirements must always adhere to strict constraints, as solutions that violate these constraints are unacceptable. Robust optimization is suitable for such contexts, as it focuses on determining the optimal solution under the worst-case scenario, ensuring that all constraints are satisfied under all possible scenarios. Therefore, our main goal is to find solutions that perform well across all potential uncertain inputs, offering better control over the feasibility and optimality of the solution. The concept of a robust optimization method as a promising approach to handle such models with uncertainty was first introduced by Soyster in [29], and later, Ben-Tal [30] developed a comprehensive framework for the robust counterpart. The application of robust optimization to the CTAP has become a popular research area. One of the key advantages of the robust optimization method is that it does not require precise knowledge of the distribution function for the uncertain parameters, but instead relies on the construction of a well-defined uncertainty set. Over time, researchers have proposed various forms of uncertainty sets, expanding the theory and applications of robust optimization, where uncertain parameters are assumed to vary within a predefined uncertainty set, such as a box set, ellipsoid set, or polyhedron set. Typically, for linear programming models with uncertain parameters, the robust counterpart can be solved in polynomial time, leveraging these uncertainty sets. There are several papers on the robust optimization of UAVs for the CTAP, as outlined below. Sun et al. [31] improved the robustness of the UAV CTAP by proposing the adaptive sampling-based task rationality review algorithm, which introduced a mathematical model incorporating task path decision variables and collaborative action constraints. Liu et al. [32] proposed a new robust task assignment formulation that reduces the calculation of robust scores by introducing a Markov model to describe the impact of uncertain parameters on task rewards and reformulating the expected score function as the utility function of the states in the Markov model. Chen et al. [33] modeled the failure rate as an uncertain variable, transforming the CTAP into an optimization problem with uncertain objective function coefficients, adapting a modified two-part wolf pack search algorithm to find the solution. However, a limitation of the robust optimization method is that it may lead to overly conservative solutions, as it does not capture the frequency distribution or the probabilistic characteristics of the uncertain parameters. In contrast, this paper, addressing the CTAPTW under uncertainty, is inspired by Bertsimas and Sim in [34], who proposed a new robust optimization framework that can be applied to solve the CTAP under the uncertainty of fuel consumption within the constraints. Additionally, acknowledging the limitations of heuristics in providing optimal solutions, which cannot be guaranteed or evaluated in most cases, we utilize the CPLEX solver based on the branch-and-price-and-cut algorithm to obtain the exact solution of the model. Some typical literature on the cooperative task assignment problem for UAVs is summarized in Table 1, highlighting the distinctiveness of our study.

1.3. Proposed Approaches

Building upon the work discussed above, we focus on a new uncertainty parameter and propose a novel solution approach to address the uncertain CTAPTW. For clarity and simplicity, we specifically examine the CTAPTW in the context of uncertain fuel consumption. The goal is to determine the task assignments and route planning for heterogeneous UAVs within a budget constraint, ensuring the tasks are completed at their designated targets within the stipulated time windows. The proposed approach can be extended to handle the CTAPTW under uncertainty in other factors, such as uncertain travel time and costs. In this paper, we propose an approach to address uncertainty for discrete optimization, which offers full control on the degree of model conservatism. The main contributions of this paper are summarized as the following three points:

• The multi-UAV CTAP model we propose introduces time window constraints, ensuring that tasks are executed within specific time interval and in a prescribed sequence, which is different from traditional CTAP models that often ignore temporal constraints. Our analysis demonstrates that these hard time window constraints significantly influence both the objective value and the optimal solution, offering a more realistic and applicable approach to task assignment in dynamic, time-sensitive environments.

• We introduce an adjustable robust optimization model that addresses the challenges of heterogeneous UAVs in the CTAP under uncertain fuel consumption. We model the flight fuel consumption as an uncertain parameter with an unknown distribution, represented by a box uncertainty set. This approach is a significant improvement over traditional methods that assume deterministic fuel parameters. Furthermore, we introduce a robustness adjustment parameter, enabling flexibility in the model’s conservatism based on the level of uncertainty. This parameter allows us to adapt the model’s robustness to varying conditions, transforming the original problem with uncertain parameters into a tractable MILP, which can be efficiently solved.

• To enhance the practical applicability of the model, we propose a novel method to convert the multi-dimensional conservatism of the multi-UAV problem into a one-dimensional conservative degree. This innovation allows us to clearly quantify and manage the trade-off between optimality and robustness. We demonstrate the effectiveness of the model by comparing performance across three distinct objectives and showing that the proposed optimization method derives robust cooperative assignment strategies that significantly mitigate the impact of fuel consumption uncertainties. Notably, the cost of achieving tunable robustness is minimal, further improving the practicality of the model for real-world applications. Our correlation analysis reveals that increasing robustness under uncertain fuel consumption leads to an equilibrium across objectives, considering UAV-specific characteristics such as initial fuel levels and flight speed, which ultimately results in optimal decision-making.

The structure of this paper is as follows. In Section 2, we present the CTAP for heterogeneous multi-UAVs with uncertain parameters, including its description, analysis, and the formulation of a rigorous mathematical model. Section 3 focuses on deriving a computationally tractable robust equivalence by applying an adjustable robust optimization approach, and then transforming the resulting robust optimization model with uncertain parameters into a mixed-integer linear programming model using duality theory. Section 4 presents a case study that includes performance evaluation, time window analysis, robust verification, and sensitivity analysis, illustrating the feasibility and effectiveness of our robust optimization models. Finally, Section 5 offers the conclusions of the study.

2. Problem Description and Formulation

2.1. Description of the UAV Cooperative Task Assignment Problem

This paper addresses the problem of assigning $N_v$ heterogeneous UAVs to complete a series of tasks on $N_t$ targets. For each target, three distinct tasks must be executed in a specific sequence: reconnaissance, followed by attack, and finally, verification to assess the outcome of the attack. The UAVs are categorized into three types: reconnaissance UAVs, attack UAVs, and integrated UAVs. Different types of UAV can perform distinct tasks, and the specialties of the three types of UAV are shown in Table 2, where C, A, and V represent the reconnaissance, attack, and verification tasks, respectively. The integrated UAVs can perform all tasks, while the reconnaissance UAVs cannot be assigned attack tasks, and the attack UAVs can only perform attack tasks.

The challenge is to efficiently allocate these heterogeneous UAVs to complete the tasks on all targets while satisfying the constraints of each UAV type. To simplify the multi-UAV CTAP, the following assumptions were made:

(1) The locations of the targets are known, which can be represented by two-dimensional coordinates.

(2) UAVs have limited range and resource on board. The attack task is performed by the ammunition unit carried by the UAV. UAVs fly at different altitudes to ensure they have collision-free flight paths.

(3) The tasks should be executed in a specific sequence and in predetermined time windows.

(4) The flight energy consumption between each pair of targets, whose range is given, is uncertain.

2.2. Formulation of the UAV Cooperative Task Assignment Problem

(1) Modeling of target and task

There are $N_t$ stationary ground targets considered in the problem. The target set is defined as:

$\mathit{T}=\left\{T_1,T_2,\cdots ,T_{N_t}\right\}.$

In addition to the $N_t$ target, there is an aircraft base, called $T_0$. For each of the $N_t$ targets, there are three distinct tasks to be executed: reconnaissance, attack, and verification. These tasks must be carried out in a specific sequence, with reconnaissance preceding the attack, which in turn must be followed by verification to assess the outcome of the attack on the target. The task set is:

${\mathit{M}}_{\mathit{T}}=\left\{\mathrm{C},\mathrm{A},\mathrm{V}\right\}.$

That is to say, the number of executed tasks on each target is $|M_T|=3$, and the total number of tasks is $N_M=N_t\left|M_T\right|=3N_t$.

(2) Modeling of heterogeneous UAVs

The distinguishing features among heterogeneous UAVs are primarily attributed to their different operational capabilities. Assume that $N_v$ heterogeneous UAVs include $N_{v_1}$ reconnaissance UAVs, $N_{v_2}$ attack UAVs, and $N_{v_3}$ integrated UAVs, where $N_v=N_{v_1}+N_{v_2}+N_{v_3}$. Let $\mathit{U}$ be the set of heterogeneous UAVs, that is,

$\mathit{U}=\left\{U_k\mid k=1,\dots ,N_{v_1},N_{v_1}+1,\dots ,N_{v_1}+N_{v_2},N_{v_1}+N_{v_2}+1,\dots ,N_v\right\}.$

2.3. Objective Function and Constraints

In the CTAPTW, different cost functions can be employed, each offering distinct benefits and drawbacks. The objective function investigated in this paper is the profit in the UAV CTAP. Therefore, the objective function of the maximum task profit can be represented as follows:

(1)$\max \mathrm{Task}\mathrm{Profit}=\sum _{i=1}^{N_t}\sum _{j=1}^{N_t}\sum _{k=1}^{N_v}\sum _{m=1}^3{\omega }_{j,k,m}{x}_{i,j}^{k,m},$

where ${\omega }_{j,k,m}$ represents the task profit gained by the k-th UAV performing the m-th task of the j-th target, $k=1,2,\cdots ,N_v$, $i,j=1,2,\cdots ,N_t$ and $m=1,2,3$, and $x_{i,j}^{k,m}$ is the binary decision variable describing the relationship between UAVs and tasks, defined as follows:

$x_{i,j}^{k,m}=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}k-\mathrm{th}\mathrm{UAV}\mathrm{flying}\mathrm{from}i-\mathrm{th}\mathrm{target}\mathrm{to}j-\mathrm{th}\mathrm{target}\mathrm{to}\mathrm{perform}m-\mathrm{th}\mathrm{task},\hfill \\ 0,\hfill & \mathrm{others}.\hfill \end{array}\right.$

Next, there are five constraints that should be satisfied in the CTAPTW.

(1) Constraints on the limited functions of the heterogeneous UAVs

The first constraint of the model is that if UAV $U_k$ is assigned the m-th task of the j-th target, corresponding to its capability defined in Table 2, then $x_{i,j}^{k,m}$ should satisfy the following constraints:

(2)$\begin{array}{cc}\hfill x_{i,j}^{k,2}& =0,k=1,2,\cdots ,N_{v_1},\hfill \end{array}$

(3)$\begin{array}{cc}\hfill x_{i,j}^{k,1}& =0,k=N_{v_1}+1,\cdots ,N_{v_1}+N_{v_2},\hfill \end{array}$

(4)$\begin{array}{cc}\hfill x_{i,j}^{k,3}& =0,k=N_{v_1}+1,\cdots ,N_{v_1}+N_{v_2}.\hfill \end{array}$

(2) Constraints on the task execution procedure

To ensure that each task is performed once, the following constraints should be satisfied:

(5)$\sum _{i=0}^{N_t}\sum _{k=1}^{N_v}{x}_{i,j}^{k,m}=1,m=1,2,3,j=1,2,\cdots ,N_t.$

Taking into account the actual combat situation to ensure that the UAV cannot perform consecutive tasks at the same target, the following constraints should be satisfied:

(6)$\sum _{i=1}^{N_t}{x}_{i,i}^{k,m}=0,m=1,2,3,k=1,2,\cdots ,N_v.$

To ensure that each UAV starts from the base, the following constraint should be satisfied:

(7)$\sum _{j=1}^{N_t}\sum _{m=1}^3{x}_{0,j}^{k,m}=1,k=1,2,\cdots ,N_v.$

To ensure that the UAV enters a target from other targets and then exits from the same target, the following constraint should be satisfied:

(8)$\sum _{i=0}^{N_t}{x}_{i,j}^{k,m_1}-\sum _{l=1}^{N_t}{x}_{j,l}^{k,m_2}=0,m_1,m_2=1,2,3,k=1,2,\cdots ,N_v,j=1,2,\cdots ,N_t.$

To ensure that the UAV returns to the base after completing all assigned tasks or without another task, the following constraint should be satisfied:

(9)$\sum _{j=1}^{N_t}\sum _{m=1}^3{x}_{i,0}^{k,m}=1,k=1,2,\cdots ,N_v.$

(3) Constraints on the consumption of fuel

We define ${\tilde{\xi }}_{i,j}^k$ to denote the uncertain fuel consumption from target i to target j. Since the fuel consumption of the UAV cannot exceed its maximum fuel load, the following constraints must be satisfied:

(10)$\sum _{i=0}^{N_t}\sum _{j=1}^{N_t}\sum _{m=1}^3{\tilde{\xi }}_{i,j}^k{x}_{i,j}^{k,m}\le F^k,k=1,2,\cdots ,N_v,$

where $F^k$ denotes the maximum fuel load of the k-th UAV.

(4) Constraints on the time coordination

First, define the real variable $t_{j,k}^m$ to represent the cumulative time of the m-th task of target j from the start if it is allocated to the k-th UAV. These tasks must be carried out in a specific sequence, with an attack after reconnaissance and a verification after the attack is over. Additionally, there should be a time interval ${\Delta }_t$ between three tasks of the same target. That is, after executing the reconnaissance task, we need to wait for a time interval ${\Delta }_{t_1}$ before executing the attack task of the same target. After the attack task is completed, we also need to wait for an interval ${\Delta }_{t_2}$ before performing the target verification task. Let $p_j^m$ denote the duration of the m-th task at the j-th target. Specifically, $p_j^1$ represents the duration of the reconnaissance task, $p_j^2$ represents the duration of the attack task, and $p_j^3$ represents the duration of the verification task. Thus, the time coordination constraints can be formulated as follows:

(11)$\sum _{k=1}^{N_v}{t}_{j,k}^1+p_j^1+{\Delta }_{t_1}\le \sum _{k=1}^{N_v}{t}_{j,k}^2,$

(12)$\sum _{k=1}^{N_v}{t}_{j,k}^2+p_j^2+{\Delta }_{t_2}\le \sum _{k=1}^{N_v}{t}_{j,k}^3,j=1,2,\cdots ,N_t.$

(5) Constraints on the time window

Since each task must be completed within a predetermined time window, we define $s_{j,k}^m$ and $f_{j,k}^m$ to represent the start and end times of the m-th task of target j if it is allocated to the k-th UAV, respectively. Hence, the time window constraints can be formulated as follows:

(13)$s_{j,k}^m{x}_{i,j}^{k,m}\le t_{j,k}^m,i,j=1,2,\cdots ,N_t,k=1,2,\cdots ,N_v,m=1,2,3,$

(14)$(f_{j,k}^m-p_j^m)x_{i,j}^{k,m}\ge t_{j,k}^m,i,j=1,2,\cdots ,N_t,k=1,2,\cdots ,N_v,m=1,2,3.$

When $x_{i,j}^{k,m}=1$, constraint (13) ensures that the execution time cannot be earlier than the earliest start time, and constraint (14) ensures that the finish time of task execution $t_{j,k}^m+p_j^m$ cannot be later than the latest end time $f_{j,k}^m$. That is to say, for each time window $[s_{j,k}^m,f_{j,k}^m]$, if $x_{i,j}^{k,m}=1$, the execution time of the the m-th task of j-th target has to be placed between $s_{j,k}^m$ and $f_{j,k}^m$; otherwise, the execution time is set as $t_{j,k}^m=0$.

Since, for UAVs performing two tasks at targets i and j, the task execution time at target j should not precede the sum of the task completion time at target i and the travel time $t_{i,j}$ between the two targets, we have the following constraint to ensure that the UAVs can continuously perform tasks:

(15)$t_{i,k}^{m_1}+p_i^{m_1}+t_{i,j}\le t_{j,k}^{m_2},\mathrm{if}{x}_{i,j}^{k,m_2}=1,i,j=1,2,\cdots ,N_t,k=1,2,\cdots ,N_v,m_1,m_2=1,2,3.$

Then, we apply the big-M method to reformulate (15) as:

(16)$t_{i,k}^{m_1}+p_i^{m_1}+t_{i,j}\le t_{j,k}^{m_2}+K(1-x_{i,j}^{k,m_2}),i,j=1,2,\cdots ,N_t,k=1,2,\cdots ,N_v,m_1,m_2=1,2,3.$

These constraints are expressed as loose inequalities that do not affect the assignments when $x_{i,j}^{k,m}=0$, where the big-M parameter K is set as $max\{f_{j,k}^m+p_j^m\}$. However, for assignments that do take place, i.e., when $x_{i,j}^{k,m}=1$, these inequalities effectively become strict equality constraints (15). By employing the big-M method to model the time window constraints in the UAV CTAP, the model is simplified into a mixed-integer linear programming (MILP) form, enabling an efficient solution by existing optimization solvers. Additionally, the big-M method provides a clear logical structure and strong interpretability, making the model more comprehensible and easier to implement. It also enhances computational efficiency, as adjusting the value of M appropriately allows for an optimal trade-off between solution accuracy and computational speed.

Based on the objective function and constraints analysed above, the robust programming model of the CTAPTW is established.

(17)$\begin{array}{cc}\hfill max& \sum _{j=1}^{N_t}\sum _{k=1}^{N_v}\sum _{m=1}^3{\omega }_{j,k,m}{x}_{i,j}^{k,m}\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& x_{i,j}^{k,2}=0,k=1,2,\cdots ,N_{v_1},\hfill \\ \hfill & x_{i,j}^{k,1}=0,k=N_{v_1}+1,\cdots ,N_{v_1}+N_{v_2},\hfill \\ \hfill & x_{i,j}^{k,3}=0,k=N_{v_1}+1,\cdots ,N_{v_1}+N_{v_2},\hfill \\ \hfill & \sum _{i=0}^{N_t}\sum _{k=1}^{N_v}{x}_{i,j}^{k,m}=1,m=1,2,3,j=1,2,\cdots ,N_t,\hfill \\ \hfill & x_{i,i}^{k,m}=0,m=1,2,3,k=1,2,\cdots ,N_v,\hfill \\ \hfill & \sum _{j=1}^{N_t}\sum _{m=1}^3{x}_{0,j}^{k,m}=1,k=1,2,\cdots ,N_v,\hfill \\ \hfill & \sum _{i=0}^{N_t}{x}_{i,j}^{k,m_1}-\sum _{l=1}^{N_t}{x}_{j,l}^{k,m_2}=0,m_1,m_2=1,2,3,k=1,2,\cdots ,N_v,j=1,2,\cdots ,N_t,\hfill \\ \hfill & \sum _{i=0}^{N_t}\sum _{j=1}^{N_t}\sum _{m=1}^3{\tilde{\xi }}_{i,j}^k{x}_{i,j}^{k,m}\le F^k,k=1,2,\cdots ,N_v,\hfill \\ \hfill & \sum _{k=1}^{N_v}{t}_{j,k}^1+P_j^1+{\Delta }_{t_1}\le \sum _{k=1}^{N_v}{t}_{j,k}^2,\sum _{k=1}^{N_v}{t}_{j,k}^2+P_j^2+{\Delta }_{t_2}\le \sum _{k=1}^{N_v}{t}_j^3,j=1,2,\cdots ,N_t,\hfill \\ \hfill & s_{j,k}^m{x}_{i,j}^{k,m}\le t_{j,k}^m,i,j=1,2,\cdots ,N_t,k=1,2,\cdots ,N_v,m=1,2,3,\hfill \\ \hfill & (f_{j,k}^m-p_j^m)x_{i,j}^{k,m}\le t_{j,k}^m,i,j=1,2,\cdots ,N_t,k=1,2,\cdots ,N_v,m=1,2,3,\hfill \\ \hfill & t_{i,k}^{m_1}+p_i^{m_1}+t_{i,j}\le t_{j,k}^{m_2}+K(1-x_{i,j}^{k,m_2}),i,j=1,2,\cdots ,N_t,k=1,2,\cdots ,N_v,m_1,m_2=1,2,3.\hfill \end{array}$

3. Robust Optimization Method for the UAV Cooperative Task Assignment Problem

Robust optimization is a proactive method that considers the uncertainty of parameters a priori from the start. Since it is difficult to obtain the probability distribution of UAV flight fuel consumption, we adopt robust optimization to model the CTAPTW. The range of the fuel consumption ${\tilde{\xi }}_{i,j}^k$ is $[{\xi }_{i,j}^k-{\widehat{\xi }}_{i,j}^k,{\xi }_{i,j}^k+{\widehat{\xi }}_{i,j}^k]$, also known as a box uncertainty set, where ${\xi }_{i,j}^k$ represents the nominal value, the fuel consumption required for the k-th UAV to fly from the i-th target to the j-th target, and ${\widehat{\xi }}_{i,j}^k$ represents the maximum deviation of fuel consumption from the mean due to environmental influences or maneuvering operations.

For discrete optimization problems, when the constraint coefficient data in an integer programming problem are affected by uncertainty, Bertsimas and Sim proposed a large-scale robust integer programming problem [34], which can control the conservative degree of the solution. Obviously, the CTAPTW established in this paper is in good agreement with the robust optimization framework proposed by Bertsimas and Sim [34].

Let

(18)$J_k=\left\{(i,j)\mid {\widehat{\xi }}_{i,j}^k>0,i,j=1,2,\cdots ,N_t\right\}.$

Considering the independence of the uncertain parameters in the constraint, the randomness of the parameters is not affected by other parameters; we introduce a number ${\mathsf{\Gamma }}_k$, $k=1,2,\cdots ,N_v$ that takes values in the interval $[0,|J_k\left|\right]$ to handle the fuel consumption constraints for each UAV. The role of parameter ${\mathsf{\Gamma }}_k$ in the constraints is to adjust the robustness of the proposed method against the level of conservatism of the solution. Consider the k-th UAV’s fuel consumption constraint of the problem. Speaking intuitively, it is unlikely that all of the ${\tilde{\xi }}_{i,j}^k$ will change. Our goal is to be protected against all cases in which up to $\lfloor {\mathsf{\Gamma }}_k\rfloor$ of these coefficients are allowed to change, and one coefficient ${\tilde{f}}_{i,j}^k$ changes by, at most, $\left({\mathsf{\Gamma }}_k-\lfloor {\mathsf{\Gamma }}_k\rfloor \right){\widehat{\xi }}_{i,j}^k$. Hence, we call ${\mathsf{\Gamma }}_k$ the protection level for the k-th UAV’s fuel consumption constraint.

We first denote the vector $\left\{x_{i,j}^{k,m}\right\},(i,j)\in J_k,m=1,2,3$ by ${\mathit{x}}^{\mathit{k}}$. In order to ensure that the resulting solution is feasible, the following protection functions are defined:

(19)$\begin{array}{cc}\hfill \beta \left({\mathit{x}}^{\mathit{k}},{\mathsf{\Gamma }}_k\right)=& \underset{\{S_k\cup \{(i_k,j_k)\}|S_k\subseteq J_k,\left|S_k\right|\le \lfloor {\mathsf{\Gamma }}_k\rfloor ,(i_k,j_k)\in J_k\setminus S_k\}}{max}\left\{\sum _{(i,j)\in S_k}\sum _{m=1}^3{\widehat{\xi }}_{i,j}^k{x}_{i,j}^{k,m}+\sum _{m=1}^3\left({\mathsf{\Gamma }}_k-\lfloor {\mathsf{\Gamma }}_k\rfloor \right){\widehat{\xi }}_{i_k,j_k}^k{x}_{i_k,j_k}^{k,m}\right\},\hfill \\ \hfill & k=1,2,\cdots ,N_v.\hfill \end{array}$

Therefore, constraint (10) can be converted to

(20)$\sum _{(i,j)\in J_k}\sum _{m=1}^3{\xi }_{i,j}^k{x}_{i,j}^{k,m}+\beta \left({\mathit{x}}^{\mathit{k}},{\mathsf{\Gamma }}_k\right)\le F^k,k=1,2,\cdots ,N_v.$

The protection function $\beta \left({\mathit{x}}^{\mathit{k}},{\mathsf{\Gamma }}_k\right)$ ensures that the solution is feasible within the allowable range of fuel consumption.

The maximization problem on the right-hand side of (19) can be equivalently transformed into a linear programming problem by introducing auxiliary variable $z_{i,j}^k$.

$\begin{array}{ccc}(\mathrm{P}1)\hfill & max& {\displaystyle \sum _{(i,j)\in J_k}}{\displaystyle \sum _{m=1}^3}{\widehat{\xi }}_{i,j}^k{x}_{i,j}^{k,m}{z}_{i,j}^k\\ \hfill & \mathrm{s}.\mathrm{t}.& {\displaystyle \sum _{(i,j)\in J_k}}{z}_{i,j}^k\le {\mathsf{\Gamma }}_k,\\ \hfill & & 0\le z_{i,j}^k\le 1,(i,j)\in J_k.\end{array}$

For problem (P1), consider the following two extreme cases.

(1) When ${\mathsf{\Gamma }}_k=0$, no fuel consumption parameters deviate from the nominal value, that is, all ${\tilde{\xi }}_{i,j}^k$ are taken as the nominal value ${\xi }_{i,j}^k$. It can be seen from problem (P1) that $z_{i,j}^k=0,\forall (i,j)\in J_k$, which leads to $\beta \left({\mathit{x}}^{\mathit{k}},{\mathsf{\Gamma }}_k\right)=0$. Under this case, the resulting robust optimization problem is a deterministic optimization problem.

(2) When ${\mathsf{\Gamma }}_k=\left|J_k\right|$, there are, at most, $|J_k|$ fuel consumption parameters that deviate from the nominal value at the same time. As shown by problem (P1), $z_{i,j}^k=1,\forall (i,j)\in J_k$, i.e., $\beta \left({\mathit{x}}^{\mathit{k}},{\mathsf{\Gamma }}_k\right)={\displaystyle \sum _{(i,j)\in J_k}}{\displaystyle \sum _{m=1}^3}{\widehat{\xi }}_{i,j}^k{x}_{i,j}^{k,m}$. At this time, the solution obtained is feasible under any change of flight fuel consumption in the given interval, but it will have a great impact on the value of the objective function. Obviously, the solution obtained in this case is too conservative. Therefore, by using the method proposed in this paper, we regulate the robustness of the solution by controlling the value of ${\mathsf{\Gamma }}_k$, so as to avoid causing a large influence on the value of the objective function.

In what follows, we transform (P1) by duality theory.

(21)$\begin{array}{cc}\hfill & L\left({\mathit{x}}^{\mathit{k}},z^k,{\lambda }^k,{\mu }^k,{\nu }^k\right)\hfill \\ \hfill =& \sum _{(i,j)\in J_k}\sum _{m=1}^3\{{\widehat{\xi }}_{i,j}^k{x}_{i,j}^{k,m}{z}_{i,j}^k\}+{\lambda }^k({\mathsf{\Gamma }}_k-\sum _{(i,j)\in J_k}{z}_{i,j}^k)+\sum _{(i,j)\in J_k}{\mu }_{i,j}^k{z}_{i,j}^k+\sum _{(i,j)\in J_k}{\nu }_{i,j}^k(1-z_{i,j}^k),\hfill \end{array}$

where ${\lambda }^k\ge 0$, ${\mu }_{i,j}^k\ge 0$, ${\nu }_{i,j}^k\ge 0$ are the Lagrange multipliers. The Lagrange dual function of (P1) is

(22)$\begin{array}{cc}& g\left({\lambda }^k,{\mu }^k,{\nu }^k\right)\hfill \\ \hfill =& \underset{z_{i,j}^k}{max}L\left({\mathit{x}}^{\mathit{k}},z^k,{\lambda }^k,{\mu }^k,{\nu }^k\right)=\underset{z_{i,j}^k}{max}\sum _{(i,j)\in J_k}(\sum _{m=1}^3{\widehat{\xi }}_{i,j}^k{x}_{i,j}^{k,m}-{\lambda }^k+{\mu }_{i,j}^k-{\nu }_{i,j}^k)z_{i,j}^k+{\lambda }^k{\mathsf{\Gamma }}_k+\sum _{(i,j)\in J_k}{\nu }_{i,j}^k.\hfill \end{array}$

(22) can be rewritten as

(23)$g\left({\lambda }^k,{\mu }^k,{\nu }^k\right)=\left\{\begin{array}{c}{\lambda }^k{\mathsf{\Gamma }}_k+{\displaystyle \sum _{(i,j)\in J_k}}{\nu }_{i,j}^k,\mathrm{if}-{\displaystyle \sum _{m=1}^3}{\widehat{\xi }}_{i,j}^k{x}_{i,j}^{k,m}+{\lambda }^k-{\mu }_{i,j}^k+{\nu }_{i,j}^k=0,\forall (i,j)\in J_k,\hfill \\ -\infty ,\mathrm{otherwise}.\hfill \end{array}\right.$

Then, we obtain the Lagrange dual problem of (P1):

(24)$min\{{\lambda }^k{\mathsf{\Gamma }}_k+\sum _{(i,j)\in J_k}{\nu }_{i,j}^k:-\sum _{m=1}^3{\widehat{\xi }}_{i,j}^k{x}_{i,j}^{k,m}+{\lambda }^k+{\nu }_{i,j}^k\ge 0,{\lambda }^k\ge 0,{\nu }_{i,j}^k\ge 0\}.$

Assume that (P1) is strictly feasible. Then, strong duality holds, that is, the optimal value of (P1), $\beta \left(x^k,{\mathsf{\Gamma }}_k\right)$, is equal to the optimal value of (24). Thus, constraint (20) can be converted into the following linear constraint:

(25)$\sum _{(i,j)\in J_k}\sum _{m=1}^3{\xi }_{i,j}^k{x}_{i,j}^{k,m}+{\lambda }^k{\mathsf{\Gamma }}_k+\sum _{(i,j)\in J_k}{\nu }_{i,j}^k\le F^k,k=1,2,\cdots ,N_v,$

(26)$-\sum _{m=1}^3{\widehat{\xi }}_{i,j}^k{x}_{i,j}^{k,m}+{\lambda }^k+{\nu }_{i,j}^k\ge 0,k=1,2,\cdots ,N_v,(i,j)\in J_k,$

(27)${\lambda }^k\ge 0,k=1,2,\cdots ,N_v,$

(28)${\nu }_{i,j}^k\ge 0,k=1,2,\cdots ,N_v,(i,j)\in J_k.$

Then, problem (17) is reformulated as:

(29)$\begin{array}{cc}\max \hfill & {\displaystyle \sum _{j=1}^{N_t}}{\displaystyle \sum _{k=1}^{N_v}}{\displaystyle \sum _{m=1}^3}{\omega }_{j,k,m}{x}_{i,j}^{k,m}\hfill \\ \mathrm{s}.\mathrm{t}.\hfill & (4)–(9),(11)–(15),(25)–(28),\hfill \end{array}$

which is an MILP. After introducing robust optimization, the computational complexity further increases due to the following reasons:

• Additional Variables: The introduction of the robustness parameter ${\lambda }^k$ and the dual variable ${\nu }_{i,j}^k$ increases variable dimensions, thereby increasing the problem’s dimensionality.

• Additional Constraints: The constraints derived from the dual problem, particularly the linearized constraints, contribute to the increased complexity of the problem.

As a result, the computational complexity of the improved problem increases. However, this challenge can be effectively addressed by employing advanced solution methods such as the branch and bound algorithm. Specifically, the branch and bound method, implemented in optimization solvers like CPLEX, is utilized to compute solutions efficiently.

In summary, the improved problem significantly increases the number of variables and constraints, primarily due to the introduction of dual and auxiliary variables. However, the use of sophisticated optimization techniques ensures that the problem remains tractable for practical applications.

4. Simulation of the UAV Cooperative Task Assignment Problem

In this section, in order to verify the effectiveness and feasibility of this robust model, the following three objectives, maximum task profit, shortest path, and minimize the time required to complete all tasks, are considered for comparative experiments. In addition, the correlation between optimality and robustness among different targets is analyzed. The objective functions for these criteria are as follows:

(30)$\max \mathrm{Task}\mathrm{Profit}=\sum _{i=1}^{N_t}\sum _{j=1}^{N_t}\sum _{k=1}^{N_v}\sum _{m=1}^3{\omega }_{j,k,m}{x}_{i,j}^{k,m},$

(31)$\min \mathrm{Total}\mathrm{Distance}=\sum _{i=0}^{N_t}\sum _{j=0}^{N_t}\sum _{k=1}^{N_v}\sum _{m=1}^3{c}_{i,j}{x}_{i,j}^{k,m},$

where $c_{i,j}$ represents the distance from i-th target to the j-th target. In particular, when $i=0$ or $j=0$ represent the distance the aircraft left or returned to the base.

(32)$\min \mathrm{Makespan}=\max \left\{t_{j,k}^m\right\}.$

The makespan, as another decision variable, needs to satisfy the following constraints:

(33)$\mathrm{makespan}\ge t_{j,k}^m.$

We know that the total distance of path can be easily converted into travel time given the speed of UAVs. Hence, at first glance, Equations (31) and (32) appear to be just different ways of obtaining the same measurement. However, the optimal solution of (31) is not the same as that of (32). This is because the total travel time does not take into accout the wait time and task execution time. Since the wait time can only be calculated after all routes have been selected, this increases the computation time required to perform MILP. Minimizing the total distance is computationally efficient but lacks precision and is not robust enough. Minimizing the makespan takes into account total completion time, including travel time, wait time, and task execution time, but could be more difficult to address.

Additionally, the task profit maximization objective evaluates the model’s ability to optimize resource allocation and mission prioritization, ensuring that UAVs complete high-value tasks efficiently. Unlike distance-based and time-based objectives, maximizing task profit provides an economic and mission-centric perspective, making it particularly relevant for applications where task prioritization is crucial.

Each objective provides a different angle for assessing the model’s robustness and suitability for real-world UAV operations, as they emphasize cost, time, and task prioritization. By comparing these three objectives, the experiments help determine how well the model balances these competing factors and adapts to different operational priorities, thus providing a comprehensive evaluation of the model’s effectiveness in various practical scenarios.

4.1. Performance Evaluation

In order to evaluate the performance and applicability of the CTAPTW developed in this paper, this section intends to conduct simulation experiments solved by MATLAB, called CPLEX.

The task setting and parameter setting of the simulation experiment are as follows: Four heterogeneous UAVs, including two reconnaissance UAVs, one attack UAV, and one integrated UAV, complete the reconnaissance, attack, and verification tasks on eight targets. The fuel capacity, flight speed, and the coordinates of the UAVs’ base, $T_0$, as well as targets $T_1–T_8$ are presented in Table 3.

The simulation experiments were carried out under the optimization objectives of maximum task profit, minimum total distance, and minimum makespan, respectively, and the simulation results, including each objective value and running time, are displayed in Table 4.

As shown in Figure 1a, the model that aims for maximum task profit only considers task profit and relaxes the constraints on path and time, that is, the model is more inclined to sacrifice a certain shortest path or time to achieve the completion of high-profit tasks, resulting in a more complex task assignment scheme and a longer total path and task completion time.

According to MILP restrictions, every UAV must be utilized. When the optimization objective is to minimize makespan, it is inevitable that as many UAVs as possible are used. However, when targeting the minimum total distance, this is not necessarily the case, as the total distance generally increases with higher UAV utilization.

In general, minimizing the total distance involves assigning all tasks to as few UAVs as possible, with the number of UAVs required depending on the number of target missions and the endurance of the UAVs. As is shown in Figure 1b, when considering the minimum total distance as the goal, it can be seen that the resource assignment of UAVs is more inclined to the geographical distribution among task points rather than to the task profit, resulting in low resource utilization efficiency. That is to say, the UAVs should be dispatched as little as possible under the condition of satisfying fuel consumption, so that the load of some UAVs is too heavy and unbalanced.

As illustrated in Figure 1c, when the objective is to minimize makespan, load balancing among UAVs becomes a critical factor in task assignment. To minimize the time difference for task completion across UAVs, the total path distance is sacrificed. Additionally, to achieve the smallest possible completion time, priority is given to assigning as many missions as possible to the faster integrated UAVs. Consequently, the UAV task loads are more balanced, but the overall path distance increases.

4.2. Time Window Analysis

For the setting of the time window, this paper considers the urgency, priority, and flexibility of the task and divides the time window into three types: no time window, relatively loose time window, and relatively tight time window. Of course, different types of time window can also be set according to the actual situation of the mission, so as to better adapt to the CTAP under different operational requirements. Next, the influence of the three time windows on the model is analyzed with the objective function of maximum task profit without considering the robustness. The result is shown in Table 5.

As can be seen from Figure 2, task assignment paths are distinct under different time windows. When there is no time window, the constraint degree is weak, the target value is the best, and the running time is short, but the maximum task completion time is the largest. This is because the target value of the looser time window is worse than that of the condition without a time window, and the running time is longer. The target value of the tight time window is the worst and the running time is obviously the longest, which is obviously caused by the strong time window constraint, but the value of its maximum task completion time is the smallest due to the time window constraint. According to the results of task assignment, the model is effective.

4.3. Robust Verification

According to the previous robust equivalence derivation process, the value of conservative degree is the maximum number of uncertain paths that deviate from the mean flight fuel consumption between each pair of targets. Let ${\mathsf{\Gamma }}_k$ be a non-negative integer, representing the number of uncertain edges. Since the number of targets is 8, it can be seen that each UAV can pass through a maximum of 8 targets, that is, there are a maximum of 9 edges. Therefore, the effective adjustment range for the conservative value of flight fuel consumption of each UAV is ${\mathsf{\Gamma }}_k\in \{0,1,\cdots ,9\}(k=1,2,3,4)$. Hence, the conservative degree of this task assignment model can be described by vector $\mathsf{\Gamma }=({\mathsf{\Gamma }}_1,{\mathsf{\Gamma }}_2,{\mathsf{\Gamma }}_3,{\mathsf{\Gamma }}_4)$. Therefore, the number of conservative values is $|{\mathsf{\Gamma }}_k{|}^4={10}^4$. Here, the conservative degree of each UAV is described as follows: 16 kinds of model conservative degrees are described and the objective values are respectively solved to analyze the robust effectiveness, which is shown in Table 6.

As depicted in Figure 3, increasing the conservatism of the model—manifested as greater uncertainty in flight fuel consumption—induces a preference for redundancy and lower-risk strategies in path selection, task assignment, and resource utilization. This shift leads to a decrease in maximum task profits, an increase in total flight distance, and an extension of task completion time. These changes primarily reflect the inherent trade-off between robustness and optimality under fuel consumption uncertainty.

In Figure 3a, with an increase in conservatism, the objective of maximizing task profits demonstrates a significant decline in overall revenue. This trend highlights the conflict between pursuing maximum profits and mitigating fuel consumption uncertainty while enhancing the model’s adaptability to worst-case scenarios. To ensure successful task execution under extreme conditions, the model tends to prefer task paths that consume less fuel, even if these paths yield lower profits. Consequently, high-profit but fuel-intensive tasks or routes are often excluded, directly reducing total task profits. This behavior reflects the model’s prioritization of reliability over optimality as it seeks to safeguard against adverse outcomes due to fuel uncertainty.

When the optimization goal is minimizing total distance, the results in Figure 3b reveal an increase in path length as conservatism grows. This trend illustrates the model’s inclination to prioritize reliability over distance optimality in response to uncertain fuel consumption. The uncertainty in flight fuel consumption significantly impacts path selection. To ensure mission completion under conditions of fuel consumption variability, the model tends to look for more robust paths that, while not the shortest, provide greater stability in terms of fuel risk and mission feasibility. This trade-off sacrifices direct distance minimization in favor of increased robustness and reliability, leading to a longer total flight distance.

For the objective of minimizing task completion time, Figure 3c shows a marked increase in task duration with higher levels of conservatism. While this prolongation may seem undesirable, it significantly enhances the robustness of task assignment under worst-case scenarios, thereby avoiding task failures caused by insufficient fuel. Uncertainty in fuel consumption exerts a substantial influence on task assignment and route planning. To mitigate the risk of task delays or incomplete missions, the model tends to distribute tasks more evenly among UAVs. This balanced assignment reduces risk but often deviates from the theoretically optimal completion time. Additionally, under higher conservatism, the model prioritizes paths and assignments that are more reliable, even if they require a slightly longer execution time. Consequently, this strategy results in an overall extension of task completion time, reflecting the trade-off between timely completion and robust task execution.

These changes underscore the delicate balance between robustness and optimality. While increasing conservatism mitigates the risks posed by fuel consumption uncertainty, it also reduces the overall efficiency and optimality of the solutions. Thus, determining an appropriate level of conservatism requires careful consideration of the specific operational context and the relative importance of robustness versus optimality. The comparison of objective values between the robust and non-robust solutions for different objectives is illustrated in Figure 4.

Compared with the optimal solution in Figure 1a, which focuses entirely on maximizing task profit while ignoring the uncertainty of flight fuel consumption and flying longer distances to obtain higher benefits, Figure 5a shows that the robust optimal solution, while still maximizing profit, considers the uncertainty of flight fuel consumption and balances maximum profit with fuel consumption robustness. Specifically, UAVs discard tasks with high profits but long paths in favor of tasks with lower profits but closer distances. Therefore, under the robust optimal solution, although the profit is reduced, the total flight distance is significantly decreased.

In comparison to Figure 1b, where the optimal path planning solely aims to minimize the total distance, resulting in task assignments that are geographically concentrated, the robust optimal solution fully accounts for the uncertainty of flight fuel consumption. As shown in Figure 5b, this approach effectively increases the path length to enhance the solution’s stability. Due to this increase in path length, UAVs that previously undertook too many tasks must discard tasks that cannot be completed, leading to a more balanced UAV workload. Consequently, UAV utilization rates are improved, and the total flight path is optimized.

Compared with the optimal solution in Figure 1c, which aims to minimize the makespan by prioritizing task assignments to UAVs with fast flight speeds and shorter completion times, the robust optimal solution achieves a balance between minimizing task completion time and ensuring robustness in fuel consumption. Therefore, due to the increase in fuel consumption, which is directly related to the longer path lengths, the robust solution assigns more tasks to the slow-flying reconnaissance UAVs and reduces the tasks assigned to the fast-flying attack UAVs and integrated UAVs, thereby sacrificing part of the goal of minimizing the task completion time, as shown in the Figure 5c.

To sum up, robust optimization primarily focuses on maintaining the validity and reliability of solutions in uncertain environments. Compared with traditional optimal solutions, robust optimal solutions typically sacrifice some degree of optimality to enhance the stability and adaptability of the solutions.

4.4. Sensitivity Analysis

In this section, sensitivity analysis of fuel consumption deviation disturbance $\epsilon$ is carried out. In the discussion of fuel consumption deviation disturbance, we set the model conservative degree to $\mathsf{\Gamma }=(8,8,8,8)$, that is, conservative degree to ${\mathsf{\Gamma }}_k=8(k=1,2,3,4)$ per UAV. The deviation disturbance $\epsilon$ is evaluated every 0.05 between 0 and 0.3 to calculate the current target value. Therefore, the maximum deviation ${\widehat{\xi }}_{i,j}^k$ of fuel consumption from the mean ${\xi }_{i,j}^k$ is calculated as follows:

(34)${\widehat{\xi }}_{i,j}^k=\epsilon {\xi }_{i,j}^k$

The result that the optimal value varies with the fuel consumption deviation disturbance under different optimization objectives is shown in Table 7.

As shown in Figure 6, under the three different optimization objectives, the optimal value becomes gradually worse with the increase of deviation disturbance $\epsilon$, that is, the task profit becomes less and less and the total distance and the makespan become longer and longer. The reason for this is that the parameter ${\mathsf{\Gamma }}_k(k=1,2,3,4)=8$ makes the flight fuel consumption between any eight paths of each UAV at the same time deviate from the mean value to the maximum, and with the increase of deviation interference $\epsilon$, the deviation from the mean value becomes larger and larger, and the impact of uncertainty on the task assignment also increases. In summary, the programming model is more sensitive to deviation disturbance $\epsilon$, and with the increase of $\epsilon$, the controlling power of ${\mathsf{\Gamma }}_k$ on the model also increases significantly. Although the value of the objective function is worse, the robustness of understanding is guaranteed and the adaptability to parameter changes is improved.

5. Conclusions

This study presents an adaptive robust optimization model to tackle the CTAPTW for multi-UAVs. Additionally, our model accommodates complex scenarios involving heterogeneous UAVs, multiple consecutive tasks, time windows, and different objective functions. In contrast to previous literature, which often assumes that the true probability distributions of uncertain parameters are known, our approach constructs a robust optimization framework that addresses uncertain fuel consumption. This framework integrates the mean, mean absolute deviation, and a parameter to control the level of robustness.

Based on duality theory, we conduct robust equivalence transformation, ultimately converting the robust optimization model into an MILP. This transformation enables the use of commercial optimization software to solve the problem efficiently. To validate the proposed approach, a series of simulations were conducted, demonstrating the feasibility and effectiveness of the robust optimization models.

Given their practical, systematic, and universal nature, the solution frameworks developed in this study can be applied to a wide range of similar or simplified scenarios, such as the multiple traveling salesman problem with resource constraints and task sequencing restrictions. The findings of this paper are most beneficial to researchers, military strategists, and operational planners involved in the optimization of UAV task assignments in uncertain environments, as well as the developers of optimization algorithms and UAV mission planning systems.

While the proposed model offers significant advantages in robustness, there are certain limitations when applying it to real-world UAV operations. First, the current model is designed for task assignments before a mission begins, but in dynamic real-world scenarios real-time adjustments may be necessary to respond to unforeseen changes. Second, for large-scale problems, real-time adaptation of the model may require further advancements in computational speed and decision-making frameworks to ensure timely responses. Future research on robust optimization in the CTAP may focus on multi-objective optimization to balance task completion time, energy consumption, and mission success rate.

Author Contributions

Conceptualization, Z.G. and Y.M.; methodology, Z.G., M.Z., and Y.M.; software, Z.G. and H.Z.; validation, Z.G. and M.Z.; formal analysis, Z.G. and M.Z.; investigation, Z.G. and H.Z.; resources, Z.G.; data curation, Z.G. and H.Z.; writing—original draft preparation, Z.G.; writing—review and editing, Z.G. and Y.M.; visualization, Z.G. and H.Z.; supervision, M.Z. and Y.M.; project administration, M.Z.; funding acquisition, Y.M. and M.Z. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

All data are contained within the article.

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. (a) The optimal task path with the objective of maximizing task profit. (b) The optimal cooperative assignment scheme with the objective of maximizing task profit. (c) The optimal task path with the objective of minimizing total distance. (d) The optimal task path with the objective of minimizing total distance. (e) The optimal task path with the objective of minimizing makespan. (f) The optimal task path with the objective of minimizing makespan. Notation: In (a,c,e), the orientation of the “yellow aircraft” indicates the direction of the corresponding path.

Figure 2. (a) The optimal task path under no time window. (b) The optimal cooperative assignment scheme under no time window. (c) The optimal task path under a loose time window. (d) The optimal cooperative assignment scheme under a loose time window. (e) The optimal task path under a tight time window. (f) The optimal cooperative assignment scheme under a tight time window.

Figure 3. (a) Influence of conservative degree with the objective of maximizing task profit. (b) Influence of conservative degree with the objective of minimizing total distance. (c) Influence of conservative degree with the objective of minimizing makespan.

Figure 4. (a) Comparison of objective values between robust and non-robust solutions with the objective of maximizing task profit. (b) Comparison of objective values between robust and non-robust solutions with the objective of minimizing total distance. (c) Comparison of objective values between robust and non-robust solutions with the objective of minimizing makespan.

Figure 5. (a) The sub-optimal task path with the objective of maximizing task profit. (b) The sub-optimal cooperative assignment scheme with the objective of maximizing task profit. (c) The sub-optimal task path with the objective of minimizing total distance. (d) The sub-optimal task path with the objective of minimizing total distance. (e) The sub-optimal task path with the objective of minimizing makespan. (f) The sub-optimal task path with the objective of minimizing makespan.

Figure 6. (a) Influence of fuel consumption deviation disturbance with the objective of maximizing task profit. (b) Influence of fuel consumption deviation disturbance with the objective of minimizing total distance. (c) Influence of fuel consumption deviation disturbance with the objective of minimizing makespan.

Table 1

Summary of existing surveys on UAV research areas.

References	Description	Heterogeneity	Energy	Robustness	Time	Task
			Constraint		Window	Coordination
Gao et al. [35]	Cooperative mission assignment using conditional probability theory.	✔	×	×	×	✔
Yu et al. [36]	Cooperative mission planning taking into account the ammunition inventory.	✔	×	×	×	✔
Cui et al. [37]	Task assignment problem with complex time window constraints.	×	✔	×	✔	×
Jia et al. [23]	Two-stage stochastic programming model with stochastic velocities.	✔	✔	×	✔	✔
He et al. [24]	Two-stage stochastic programming model with recourse cost.	×	✔	×	✔	×
Sun et al. [31]	Task path assignment with collaborative action constraints.	×	✔	✔	×	✔
Liu et al. [32]	A new robust task assignment formulation that reduces the calculation of robust scores.	✔	×	✔	×	×
Chen et al. [33]	Task assignment problem with the failure rate treated as a random variable.	✔	✔	✔	×	✔
Our work	Cooperative task assignment problem with time windows.	✔	✔	✔	✔	✔

Table 2

The capabilities of heterogeneous UAVs.

Type	Capability	Task
Integrated UAVs	reconnaissance, attack, verification	{C, A, V}
Reconnaissance UAVs	reconnaissance, verification	{C, V}
Attack UAVs	attack	{A}

Table 3

Parameters of heterogeneous UAVs and coordinates of base $T_0$ and targets $T_1$–$T_8$.

UAV	Fuel Capacity	Flight Speed	Target	x	y
Reconnaissance UAV 1	320	1.8	$T_1$	25	25
			$T_2$	25	50
Reconnaissance UAV 2	340	1.5	$T_3$	38	62
			$T_4$	55	50
Attack UAV 3	360	2.5	$T_5$	62	42
			$T_6$	54	18
Integrated UAV 4	380	3.2	$T_7$	34	12
			$T_8$	16	30
Base $T_0$: x = 40, y = 40

Table 4

Objective values and run time under different optimization objectives.

Optimization Objective	Task Profit	Total Distance	Makespan	Time (s)
Maximum Task Profit	711	629.91	161.73	0.16
Minimum Total Distance	675	510.07	128.02	0.42
Minimum Makespan	644	589.33	92.33	1292.92

Table 5

Performance evaluation under different time windows.

Time Window	Task Profit	Makespan	Time (s)
no	711	174	0.13
loose	709	160	5.48
tight	687	150	126.83

Table 6

The optimal value varies with the conservative degree under different optimization objectives.

$\mathsf{\Gamma }$				Conservative	Objective Functions
${\mathsf{\Gamma }}_{\mathbf{1}}$	${\mathsf{\Gamma }}_{\mathbf{2}}$	${\mathsf{\Gamma }}_{\mathbf{3}}$	${\mathsf{\Gamma }}_{\mathbf{4}}$	Degree	Max Task Profit	Min Total Distance	Min Makespan
0	0	0	0	0	711	510.07	92.33
2	0	0	0	1	711	510.07	94.96
4	0	0	0	2	711	510.07	94.96
6	0	0	0	3	711	510.07	94.96
8	0	0	0	4	711	510.07	94.96
8	2	0	0	5	710	510.07	102.49
8	4	0	0	6	710	510.07	102.49
8	6	0	0	7	710	510.07	102.49
8	8	0	0	8	710	510.07	102.49
8	8	2	0	9	705	513.63	102.49
8	8	4	0	10	705	513.63	102.49
8	8	6	0	11	705	513.63	102.49
8	8	8	0	12	705	513.63	102.49
8	8	8	2	13	696	516.75	116.87
8	8	8	4	14	696	516.75	116.87
8	8	8	6	15	696	516.75	116.87
8	8	8	8	16	696	516.75	116.87

Table 7

The optimal value varies with the fuel consumption deviation disturbance under different optimization objectives.

Fuel Consumption Deviation Disturbance	Max Task Profit	Min Total Distance	Min Makespan
0	711	510.07	92.33
0.025	711	510.07	94.96
0.05	711	510.07	94.96
0.075	711	510.07	94.96
0.1	711	510.07	94.96
0.15	709	513.19	102.49
0.2	704	516.75	116.87
0.25	696	516.75	116.87
≥0.3	-	-	-

References

1. Qin, B.; Zhang, D.; Tang, S.; Wang, M. Distributed grouping cooperative dynamic task assignment method of UAV swarm. Appl. Sci.; 2022; 12, 2865. [DOI: https://dx.doi.org/10.3390/app12062865]

2. Zhang, Z.; Jiang, J.; Xu, H. Distributed dynamic task allocation for unmanned aerial vehicle swarm systems: A networked evolutionary game-theoretic approach. Chin. J. Aeronaut.; 2024; 37, pp. 182-204. [DOI: https://dx.doi.org/10.1016/j.cja.2023.12.027]

3. Zhang, Y.; Xu, J.; Wu, Z.; Ma, Y. Complex task assignment of heterogeneous UAVs under timing constraints. Proceedings of the 2020 IEEE 16th International Conference on Control Automation; Sapporo, Japan, 9–11 October 2020; pp. 853-858.

4. Zhou, Y.; Rao, B.; Wang, W. UAV swarm intelligence: Recent advances and future trends. IEEE Access; 2020; 8, pp. 183856-183878. [DOI: https://dx.doi.org/10.1109/ACCESS.2020.3028865]

5. Zhang, R.; Chen, X.; Li, M.; Ding, Y. Multiple UAVs task assignment based on improved dung beetle optimizer. Proceedings of the 2023 IEEE International Conference on Unmanned Systems; Hefei, China, 13–15 October 2023; pp. 779-785.

6. Poudel, S.; Moh, S. Task assignment algorithms for unmanned aerial vehicle networks: A comprehensive survey. Veh. Commun.; 2022; 35, 100469. [DOI: https://dx.doi.org/10.1016/j.vehcom.2022.100469]

7. Yan, S.; Xu, J.; Song, L.; Pan, F. Research on cooperative task assignment scheme of heterogeneous UAVs. Proceedings of the 2022 5th International Conference on Artificial Intelligence and Big Data; Fuzhou, China, 8–10 July 2022; pp. 480-483.

8. Zhang, J.; Xing, J. Cooperative task assignment of multi-UAV system. Chin. J. Aeronaut.; 2020; 33, pp. 2825-2827. [DOI: https://dx.doi.org/10.1016/j.cja.2020.02.009]

9. Schumacher, C.; Chandler, P.; Pachter, M.; Pachter, L. UAV task assignment with timing constraints. Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit; Austin, TX, USA, 11–14 August 2003; 5664.

10. Yue, L.; Yang, R.; Zuo, J.; Zhang, Y.; Li, Q.; Zhang, Y. Unmanned aerial vehicle swarm cooperative decision-making for SEAD mission: A hierarchical multiagent reinforcement learning approach. IEEE Access; 2022; 10, pp. 92177-92191. [DOI: https://dx.doi.org/10.1109/ACCESS.2022.3202938]

11. Kewei, Z.; Zongzhe, L.; Xiaolin, Z.; Boxin, Z. Dynamic multi-UAV cooperative reconnaissance task assignment based on ICNP. Proceedings of the 2020 5th International Conference on Mechanical, Control and Computer Engineering; Harbin, China, 25–27 December 2020; pp. 25-27.

12. Shima, T.; Rasmussen, S.J.; Sparks, A.G. UAV cooperative multiple task assignments using genetic algorithms. Proceedings of the 2005 American Control Conference; Portland, OR, USA, 8–10 June 2005; pp. 2989-2994.

13. Ye, F.; Chen, J.; Tian, Y.; Jiang, T. Cooperative task assignment of a heterogeneous multi-UAV system using an adaptive genetic algorithm. Electronics; 2020; 9, 687. [DOI: https://dx.doi.org/10.3390/electronics9040687]

14. Zhao, Y.; Zhou, D.; Piao, H.; Yang, Z.; Hou, R.; Kong, W.; Pan, Q. Cooperative multiple task assignment problem with target precedence constraints using a waitable path coordination and modified genetic algorithm. IEEE Access; 2021; 9, pp. 39392-39410. [DOI: https://dx.doi.org/10.1109/ACCESS.2021.3063263]

15. Lu, Y.; Ma, Y.; Wang, J.; Han, L. Task assignment of UAV swarm based on wolf pack algorithm. Appl. Sci.; 2020; 10, 8335. [DOI: https://dx.doi.org/10.3390/app10238335]

16. Issac, T.; Silas, S.; Rajsingh, E.B. Investigations on PSO based task assignment algorithms for heterogeneous wireless sensor network. Proceedings of the 2019 2nd International Conference on Signal Processing and Communication; Coimbatore, India, 29–30 March 2019; pp. 89-93.

17. Zhang, J.; Wen, P.; Xiong, A. Multi-task assignment research for heterogeneous UAVs based on improved simulated annealing particle swarm optimization algorithm. Proceedings of the 2022 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery; Suzhou, China, 14–16 October 2022; pp. 284-288.

18. Naderi, E.; Mirzaei, L.; Trimble, J.P.; Cantrell, D.A. Multi-objective optimal power flow incorporating flexible alternating current transmission systems: Application of a wavelet-oriented evolutionary algorithm. Electr. Power Compon. Syst.; 2023; 5, pp. 766-795. [DOI: https://dx.doi.org/10.1080/15325008.2023.2234378]

19. Gorissen, B.L.; Yanıkoğlu, İ.; Den Hertog, D. A practical guide to robust optimization. Omega; 2015; 53, pp. 124-137. [DOI: https://dx.doi.org/10.1016/j.omega.2014.12.006]

20. Le Thi, H.A.; Nguyen, D.M.; Pham Dinh, T. Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches. Optim. Lett.; 2012; 6, pp. 315-329. [DOI: https://dx.doi.org/10.1007/s11590-010-0259-x]

21. Hu, X.; Cheng, J.; Luo, H. Task assignment for multi-UAV under severe uncertainty by using stochastic multicriteria acceptability analysis. Math. Probl. Eng.; 2015; 1, 249825. [DOI: https://dx.doi.org/10.1155/2015/249825]

22. Juan, A.A.; Freixes, A.; Copado, P.; Panadero, J.; Gómez, J.F.; Serrat, C. A genetic algorithm simheuristic for the open UAV task assignment and routing problem with stochastic traveling and servicing times. Proceedings of the 2021 Winter Simulation Conference; Phoenix, AZ, USA, 12–15 December 2021; pp. 1-12.

23. Jia, Z.; Yu, J.; Ai, X.; Xu, X.; Yang, D. Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm. Aerosp. Sci. Technol.; 2018; 76, pp. 112-125. [DOI: https://dx.doi.org/10.1016/j.ast.2018.01.025]

24. He, Y.; Zheng, Z.; Li, H.; Deng, J. A stochastic drone-scheduling problem with uncertain energy consumption. Drones; 2024; 8, 430. [DOI: https://dx.doi.org/10.3390/drones8090430]

25. Huang, H.; Jiang, Z.; Yan, T.; Bai, Y. Dynamic task allocation for heterogeneous multi-UAVs in uncertain environments based on 4DI-GWO algorithm. Drones; 2024; 8, 236. [DOI: https://dx.doi.org/10.3390/drones8060236]

26. Naderi, E.; Mirzaei, L.; Pourakbari-Kasmaei, M. Optimization of active power dispatch considering unified power flow controller: Application of evolutionary algorithms in a fuzzy framework. Evol. Intel.; 2024; 17, pp. 1357-1387. [DOI: https://dx.doi.org/10.1007/s12065-023-00826-2]

27. Zhen, L. Task assignment under uncertainty: Stochastic programming and robust optimization approaches. Int. J. Prod. Res.; 2015; 53, pp. 1487-1502. [DOI: https://dx.doi.org/10.1080/00207543.2014.951094]

28. Gabrel, V.; Murat, C.; Thiele, A. Recent advances in robust optimization: An overview. Eur. J. Oper. Res.; 2014; 235, pp. 471-483. [DOI: https://dx.doi.org/10.1016/j.ejor.2013.09.036]

29. Soyster, A.L. Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res.; 1973; 21, pp. 1154-1157. [DOI: https://dx.doi.org/10.1287/opre.21.5.1154]

30. Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A. Robust Optimization; Princeton University Press: Princeton, NJ, USA, 2009.

31. Sun, C.; Yao, Y.; Zheng, E. Enhancing unmanned aerial vehicle task assignment with the adaptive sampling-based task rationality review algorithm. Drones; 2024; 8, 422. [DOI: https://dx.doi.org/10.3390/drones8090422]

32. Liu, R.; Seo, M.; Yan, B.; Tsourdos, A. Decentralized task allocation for multiple UAVs with task execution uncertainties. Proceedings of the 2020 International Conference on Unmanned Aircraft Systems; Athens, Greece, 1–4 September 2020; pp. 271-278.

33. Chen, Y.; Yang, D.; Yu, J. Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm. IEEE Trans. Aerosp. Electron. Syst.; 2018; 54, pp. 2853-2872. [DOI: https://dx.doi.org/10.1109/TAES.2018.2831138]

34. Bertsimas, D.; Sim, M. Robust discrete optimization and network flows. Math. Program.; 2003; 98, pp. 49-71. [DOI: https://dx.doi.org/10.1007/s10107-003-0396-4]

35. Gao, X.; Wang, L.; Yu, X. Conditional probability based multi-objective cooperative task assignment for heterogeneous UAVs. Eng. Appl. Artif. Intell.; 2023; 123, 106404. [DOI: https://dx.doi.org/10.1016/j.engappai.2023.106404]

36. Yu, X.; Gao, X.; Wang, L.; Wang, X.; Ding, Y.; Lu, C.; Zhang, S. Cooperative multi-UAV task assignment in cross-regional joint operations considering ammunition inventory. Drones; 2022; 6, 77. [DOI: https://dx.doi.org/10.3390/drones6030077]

37. Cui, W.; Li, R.; Feng, Y.; Yang, Y. Distributed task allocation for a multi-UAV system with time window constraints. Drones; 2022; 6, 226. [DOI: https://dx.doi.org/10.3390/drones6090226]