Multi-Mission Oriented Joint Optimization of Task Assignment and Flight Path Planning for Heterogeneous UAV Cluster

Abstract

This paper puts forward a joint optimization algorithm of task assignment and flight path planning for a heterogeneous unmanned aerial vehicle (UAV) cluster in a multi-mission scenario (MMS). The basis of the proposed algorithm is to establish constraint and threat models of a heterogeneous UAV cluster to simultaneously minimize range and maximize value gain and survival probability in an MMS under the constraints of task payload, range, and task requirement. On one hand, the objective function for the heterogeneous UAV cluster within an MMS is derived and it is adopted as a metric for assessing the performance of the joint optimization in task assignment and flight path planning. On the other hand, since the formulated joint optimization problem is a multi-objective, non-linear, and non-convex optimization model due to its multiple decision variables and constraints, the roulette wheel selection (RWS) principle and the elite strategy (ES) are introduced in an ant colony optimization (ACO) to solve the complex optimization model. The simulation results indicate that the proposed algorithm is superior and more efficient compared to other approaches.

1. Introduction

1.1. Research Background

In recent years, unmanned aerial vehicle (UAV) combat has emerged as a highly promising and popular method. However, individual UAVs face limitations such as restricted payload capacity and low survivability, making them less adaptable to complex multi-mission scenarios (MMSs). To address these challenges, scholars have introduced the concept of “UAV clustering”, which shifts the focus of UAV combat from single-platform operations to a multi-platform approach. Research indicates that employing a clustered mode significantly enhances task efficiency compared to the cumulative performance of single UAVs [1].

Task assignment and path planning constitute two vital elements in the mission planning of UAVs [2]. Intriguingly, both of these elements fall under the category of non-deterministic polynomial problems [3,4,5,6,7,8], renowned for their complexity and difficulty to resolve. At present, the leading approaches to addressing the task assignment of UAV clusters encompass the centralized algorithm, the distributed algorithm, and the hybrid solving algorithm [9]. Specifically, Bays et al. [10] introduce a heuristic optimization algorithm to address the inefficiencies in route planning and fuel limitations for heterogeneous autonomous robot teams, using the concept of service agent transfer to minimize the operational time of both target planning and transportation agents. In their study [11], the authors present a group-based distributed control model that organizes UAVs into leader and follower categories, thereby creating a hierarchical control structure that enhances collaborative operations within UAV swarms, demonstrating notable superiority over other task assignment models. Wu et al. [12] tackle the intricate problems of task coordination and data management for UAVs by treating path planning as a sub-problem of task assignment, thereby reducing computational complexity, and effectively employ a distributed genetic algorithm to achieve collaborative combat tasks for UAVs. The research in [13] proposes a contract auction algorithm, guided by a simulated annealing criterion, to ascertain the optimal sequence for task execution, and leverages the A-Star algorithm to calculate the distance between the UAV and the task location, thus facilitating initial path planning before task assignment. Junior et al. [14] employ an innovative extended experiential evaluation system to address the challenge of task assignment among dynamic UAVs, with the objective of independently duplicating relevant data throughout the operational process, ensuring efficiency even when the number of UAVs varies. Wang et al. [15] introduce a dynamic distributed task planning methodology to manage the issue of varying task numbers in dynamic environments, dynamically adjusting the quantity and value of tasks to meet the needs of time-sensitive assignments, while considering the heterogeneous characteristics of UAVs and the temporal interdependencies of tasks.

The issue of path planning can essentially be bifurcated into two key categories: static path planning, typically resolved using conventional planning algorithms, and dynamic path planning, which is tackled through intelligent optimization algorithms. More specifically, the study referenced as [16] develops a heuristic evaluation function model grounded on the A-Star algorithm, thereby amplifying the efficiency and precision of optimal path selection in trajectory planning. In [17], Xu et al. innovatively tackle the issue of traditional artificial potential field methods getting stuck in trap zones and local optima during path planning by introducing “safety distance” and “prediction distance” concepts and judiciously positioning virtual target points to steer the robot away from local minima and trap areas. In [18], Zhang et al. enhance the efficiency of path planning by introducing an autonomous method for a robot manipulator, which is based on an improved rapidly exploring random tree algorithm to avoid unnecessary iterations in the manipulator’s movement. In response to bird infestation in farm orchards, Mesquita et al. [19] employ a particle swarm algorithm to reconfigure bird repellent and UAV patrol paths, taking into account constraints like UAV battery resources and operational range. The work of [20] presents a reconfigurable 3D dynamic trajectory planning model incorporating a fuzzy factor and introduces the wolf pack allocation and roulette wheel selection (RWS) principles to improve the computational efficiency, optimization capacity, and obstacle avoidance success rate of the classic ant colony optimization (ACO) algorithm. Reference [21] investigates the cooperative path planning issue for fixed-wing UAVs with velocity constraints in a two-dimensional plane to maintain a precise inter-UAV arc distance sequence, proposing a hybrid control law that addresses the constraints on the forward and angular speeds during flight.

1.2. Research Motivation

However, the decoupling of task assignment and path planning in previous studies has resulted in a diluted interaction between the two processes, with task assignment emphasizing only the timing and inter-task influences without accounting for the UAVs’ motion restrictions or environmental dangers. On the other hand, path planning considers these factors based on the results of task assignment. While this sequential methodology simplifies the complexity of the problem, it often fails to meet real-world operational standards. Consequently, the academic community has seen a growing trend towards research into the integrated optimization of task assignment and path planning to create more robust and practical UAV operational strategies. In [22], Albani et al. introduce a hierarchical framework for task assignment and path planning, effectively integrating and addressing both aspects through the application of the Floyd–Warshall algorithm. In [23], Kim et al. introduce a distributed collaborative combat method that utilizes the response threshold model and probabilistic decision making, allowing UAVs to swiftly detect targets and execute precise strikes. The study outlined in reference [24] introduces an integrated algorithm for the distributed collaborative dynamic task planning of UAVs, effectively tackling complex planning issues within dynamic task scenarios. Reference [25] proposes an intelligent marine task allocation and route planning algorithm for multiple UAVs, which combines improved particle swarm optimization with a genetic algorithm to address random task allocation for multiple UAVs and two-dimensional route planning for a single UAV through the introduction of partial matching crossover and secondary transposition mutation.

1.3. Organization

The above research outcomes have established a strong foundation for improving the efficiency of task assignment and flight path planning for UAVs. However, existing studies have not considered the joint optimization of task assignment and flight path planning for a heterogeneous UAV cluster within an MMS. Therefore, this paper focuses on the areas of MMSs, heterogeneous UAVs, as well as task assignment and path planning, and proposes a joint optimization algorithm. Firstly, we derive the joint optimization objective function based on the constraint model and threat model. Secondly, a joint optimization model of task assignment and flight path planning for a heterogeneous UAV cluster in an MMS is established. Finally, an ACO is used with an elite strategy (ES) and RWS to solve this problem. The main sections of this article are arranged as follows:

The primary focus of the first section is to elucidate the background and motivation behind the research. It aims to address issues pertaining to the range, value gain, and survival probability of UAV operations. It also elaborates on the existing research methods for task assignment and path planning. Additionally, this paper proposes improvement methods based on relevant research to overcome the shortcomings of existing research on joint optimization problems of task assignment and path planning, thereby showcasing the innovation of this article. Finally, the main content and structural arrangement of this article is introduced.

The second section primarily introduces the system model. When faced with non-deterministic polynomial problems such as the joint optimization of task assignment and flight path planning, a constraint model and an environment model are first established. Then, the raster graph method is employed to process the threat environment. Towards the end of the section, the objective function is formulated to evaluate the superiority of this algorithm.

In the third section, a detailed introduction is provided for the joint optimization of task assignment and flight path planning for heterogeneous UAV clusters in an MMS. ACO with RWS and ES is utilized to address the problem by establishing an optimization mathematical model. The RWS principle enhances the randomness of node selection and prevents the algorithm from getting stuck in local optima or a stagnant state, while the ES strengthens the positive feedback mechanism of the ACO and prevents premature convergence.

In the fourth section, two types of threats and three different scenarios are considered, followed by the design of simulation experiments. By comparing the algorithm proposed in this paper with task assignment and trajectory planning algorithms, it becomes evident that the proposed algorithm possesses significant advantages.

The fifth section summarizes the work conducted throughout the article, and also provides an analysis and projections for the future of joint optimization for UAV cluster task assignment and flight path planning.

2. System Model

The complexity of task assignment and flight path collaborative planning for a heterogeneous UAV cluster in an MMS is reflected in the following points:

• There are numerous tasks with complex requirements, and these requirements vary for different tasks. This article highlights that the value gains achieved by the same UAV when performing different tasks also differ;
• In this article, it is highlighted that there is a wide range of UAVs available, each with different types and capabilities of mounted resources. As a result, when performing the same task, different UAVs can achieve varying value gains due to the constraints imposed by their payloads. It is worth noting that a UAV has the potential to participate in multiple tasks, and this collection of tasks is referred to as a task set;
• The task encompasses a vast geographical area, with multiple departure locations (ground stations), and each station allocates varying amounts of resources for UAV platforms. When it comes to UAVs undertaking long-range tasks, the distance traveled to reach the task area becomes a crucial factor that cannot be overlooked.

Let us consider an MMS, which involves a heterogeneous UAV cluster consisting of $N$ UAVs, forming the set $U=\{u_1,u_2,\dots ,u_i,\dots ,u_N\}$ and a set of $M$ tasks denoted as $T=\{t_1,t_2,\dots ,t_i,\dots ,t_M\}$. In order to simplify the derivation and computation in the following subsections, we assume that there is robust communication between UAVs and that there will be no collisions among UAVs during flight. The operational diagram is shown in Figure 1.

2.1. Constraint Model

2.1.1. Payload Constraint

The payload of a UAV encompasses the various equipment and machinery installed on the aircraft, allowing it to execute specific tasks or collect particular information. Common types of payloads include cameras, sensors, target detectors, communication devices, and more. When a cluster of UAVs is established, the allocation of payloads is determined by the requirements of the task at hand. It is crucial to remember that, barring actual turning angle limitations, the total weight of the payload assigned to the UAV for tasks should not exceed its maximum carrying capacity. Assuming the task set of UAV $u_i$ is denoted as $TA$, there is:

$${\displaystyle \sum _{t_j\in TA}{B}_j^t}\le B_i^u,\forall i$$

(1)

where $B_j^t$ denotes the payload needed for UAV $u_i$ to perform task $t_j$, and $B_i^u$ denotes the total payload carried by UAV $u_i$.

2.1.2. Range Constraint

The flight path of UAVs often needs to circumvent obstacles, making it challenging to maintain a straight trajectory. The maximum range of a UAV is dictated by its battery’s energy consumption, which in turn impacts its capability to execute tasks over extended distances. Furthermore, a range of parameters such as fuel reserves, flight time, and flight status are collectively considered under the range constraint to aid in modeling and problem solving. The aggregate length of the paths that the UAV takes for its tasks must not surpass its own range constraint:

$${\displaystyle \sum _{t_j\in TA}{L}_j^t}\le L_i^u,\forall i$$

(2)

where $L_j^t$ denotes the range traveled by UAV $u_i$ to perform task $t_j$, and $L_i^u$ denotes the total range of UAV $u_i$.

2.1.3. Task Requirement Constraint

To enhance the efficiency of task execution and prevent resource wastage, it is mandated that all tasks are performed once. This is articulated as the task requirement constraint:

$$x_{ij}=\{\begin{array}{l}1,\mathrm{UAV}{u}_i\mathrm{complete}\mathrm{task}{t}_j\\ 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{otherwise}\end{array}$$

(3)

furthermore

$${\displaystyle \sum _{i=1}^N{x}_{ij}}=1,\forall j$$

(4)

where $x_{ij}$ denotes the task decision variable.

2.2. Environment Model

2.2.1. Passive Threat

Passive threats do not actively emit energy to detect signals. Instead, they reflect and manipulate the energy of the opposing party, serving a suppressive and deceptive function. Examples of passive threats include geographical peaks, buildings, and atmospheric conditions. These threats have definitive boundaries, and exposure to such obstacles could result in collisions and subsequent damage to the UAV. If the UAV’s position can be pinpointed on the map, its safety can be directly evaluated. In our modeling process, these threats are represented on the map as polygons with distinct boundaries. A value of 1 indicates that the UAV is within the threat zone, while a value of 0 signifies that the UAV lies outside of it:

$$P_{\mathrm{p}}=\{\begin{array}{l}1,\mathrm{within}\mathrm{the}\mathrm{threat}\mathrm{zone}\\ 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{otherwise}\end{array}$$

(5)

where $P_{\mathrm{p}}$ denotes the probability of the UAV entering the passive threat zone.

2.2.2. Active Threat

The risk range of active threats is typically small, usually requiring power to function and often actively detecting and interfering with signals. In this article, we design an active threat to detect targets with a certain probability. When a UAV enters the threat zone, but the probability of being threatened falls outside the detectable range of the active threat, the UAV is deemed safe. Examples of these active threats include radar, artillery, and missiles. In our modeling process, these threats are represented on the map as circles with varying radii, centered on the threats themselves:

$$P_{\mathrm{a}}=\{\begin{array}{l}{K}_{\mathrm{a}}\frac{1}{r_{ij}},r_{ij}\le R_j\\ 0,\hspace{1em}{r}_{ij}>R_j\end{array}$$

(6)

where $P_{\mathrm{a}}$ denotes the probability of an active threat to the UAV, $r_{ij}$ denotes the distance between the UAV $u_i$ and the task $t_j$, $R_j$ denotes the effective range of the threat source, and $K_{\mathrm{a}}$ denotes the constant of proportionality, which is related to the distance between the active threat and the UAV.

2.2.3. Threat Mapping

The primary techniques for designing threat maps encompass the Voronoi diagram approach and the raster method. The Voronoi diagram method portrays threat sources directly as polygons or circles with unequal radii, randomly scattered across a 2D map. Although this method is straightforward and requires fewer computational data, it has significant limitations, such as diminished depiction accuracy and an inability to capture the interrelationships among various threats. The raster method, on the other hand, divides the 2D plane into numerous rectangles, known as rasters. As the number of rasters increases, so does the precision in representing threat sources, resulting in a more accurate depiction of the threat environment. If a raster signifies an obstacle, it is given a value of 1; if not, it is assigned 0. This is illustrated in Figure 2.

2.3. Solution Evaluation Model

Within the MMS for a heterogeneous UAV cluster, several key metrics are instrumental in evaluating the performance of the joint optimization algorithm, such as range, survival probability, and value gain. By integrating the constraint model and threat model established in the preceding sections, we can derive:

1.

Cost of the range:

$$L_{\mathrm{T}}={\displaystyle \sum _{t_j\in TA}{L}_j^t}$$

(7)

where $L_{\mathrm{T}}$ denotes the total range of the UAV $u_i$ to perform tasks.

2.

Cost of the threat:

$$P_{\mathrm{T}}={\displaystyle \sum _{t_j\in TA}\left(w_1{P}_{\mathrm{p}}+w_2{P}_{\mathrm{a}}\right)}$$

(8)

where $P_{\mathrm{T}}$ denotes the probability that UAV $u_i$ is threatened during the execution of its tasks, $w_1$ denotes the passive threat weight coefficient, and $w_2$ denotes the active threat weight coefficient.

3.

Total value gain: Considering the varying importance levels of tasks, the gains achieved upon their completion also differ. Hence, this section introduces the concept of “value gain” and provides the formula for its calculation:

$$V_{\mathrm{T}}={\displaystyle \sum _{t_j\in TA}{V}_{ij}},\forall i$$

(9)

where $V_{ij}$ denotes the value gain when UAV $u_i$ performs task $t_j$, $V_{\mathrm{T}}$ denotes the sum of the value gain obtained by UAV $u_i$ performing tasks.

When assessing the solution, it is paramount to consider all three factors mentioned above. Therefore, these three factors are normalized by introducing weight coefficients, and then the joint optimization objective function is described as:

$$\max F={\delta }_1\left(1-\frac{L_{\mathrm{T}}}{L_{\mathrm{Tmax}}}\right)+{\delta }_2\frac{V_{\mathrm{T}}}{V_{\mathrm{Tmax}}}+{\delta }_3\left(1-\frac{P_{\mathrm{T}}}{P_{\mathrm{Tmax}}}\right)$$

(10)

where ${\delta }_1$, ${\delta }_2$, and ${\delta }_3$ denote the weighting coefficients of UAV cluster range cost, value gain, and survival probability, respectively, $L_{\mathrm{Tmax}}$ denotes the maximum range among all UAVs, $V_{\mathrm{Tmax}}$ denotes the maximum value gain obtained from the task executed by all UAVs, and $P_{\mathrm{Tmax}}$ denotes the maximum threatened probability among all UAVs.

3. Multi-Mission Oriented Joint Optimization of Task Assignment and Flight Path Planning for Heterogeneous UAV Cluster

3.1. Optimization Modeling Establishing

This paper aims to maximize the operational efficiency of the heterogeneous UAV cluster by jointly optimizing the UAV range, value gain, and survival probability, under the constraints of payload, range, and task requirement. The mathematical representation for this joint optimization is as follows:

$$\begin{array}{l}\underset{L_{\mathrm{T}},V_{\mathrm{T}},P_{\mathrm{T}}}{\max }F={\delta }_1\left(1-\frac{L_{\mathrm{T}}}{L_{\mathrm{Tmax}}}\right)+{\delta }_2\frac{V_{\mathrm{T}}}{V_{\mathrm{Tmax}}}+{\delta }_3\left(1-\frac{P_{\mathrm{T}}}{P_{\mathrm{Tmax}}}\right)\\ \mathrm{s}.\mathrm{t}.\{\begin{array}{l}\{\begin{array}{l}{L}_{\mathrm{T}}={\displaystyle \sum _{t_j\in TA}{L}_j^t},\forall i\hfill \\ L_{\mathrm{T}}\le L_{\mathrm{Tmax}}\hfill \end{array}\hfill \\ \{\begin{array}{l}{V}_{\mathrm{T}}={\displaystyle \sum _{t_j\in TA}{V}_{ij}},\forall i\hfill \\ V_{\mathrm{T}}\le V_{\mathrm{Tmax}}\hfill \end{array}\hfill \\ \{\begin{array}{l}{P}_{\mathrm{T}}={\displaystyle \sum _{t_j\in TA}\left({\omega }_1{P}_{\mathrm{p}}+{\omega }_2{P}_{\mathrm{a}}\right)},\forall i\hfill \\ P_{\mathrm{T}}\le P_{\mathrm{Tmax}}\hfill \end{array}\hfill \\ {\displaystyle \sum _{i=1}^N{x}_{ij}}\le 1,\forall j\hfill \\ {\displaystyle \sum _{t_j\in TA}{B}_j^t}\le B_i^u,\forall i\hfill \end{array}\end{array}$$

(11)

in Equation (11), the first constraint limits the UAV’s flying distance; the second constraint ensures the maximization of the UAV’s value gain; the third constraint aims to enhance the UAV’s survivability in a threatening environment; the fourth constraint represents the number of UAVs required for task execution; and the fifth constraint pertains to the UAV’s payload limits.

3.2. Optimization Model Solving

To solve the joint optimization model described in Section 3.1, we introduced the RWS principle and ES principle into the ACO. The ant colony algorithm is a probabilistic intelligent swarm algorithm designed to mimic the foraging behavior of ants in order to find the optimal path [26]. As a type of intelligent optimization algorithm, the ACO is frequently employed in UAV task assignment and path planning due to its excellent characteristics of self-organization, parallelism, positive feedback, and robustness [27]. However, classical ACO exhibits significant performance degradation when applied to trajectory planning problems, such as extended iteration time, slow convergence speeds, and premature local optima or even algorithmic stagnation [28]. To address these issues, this paper introduces an ES and employs an RWS principle to optimize the pheromone update mechanism and node selection method, respectively.

3.2.1. RWS Principle

The selection probability is a critical factor in determining the next node an ant will move to in traditional ant colony algorithm. It directly influences the randomness of the node selection and can often lead to the algorithm getting stuck in a local optimum or stagnant state. The fundamental principle of rank-based RWS is that the selection probability of an individual is directly proportional to its fitness level. If we denote an individual as $x_i\left(i=1,2,\dots ,ant\right)$, with $ant$ representing the total population, and its fitness as $f\left(x_i\right)$, then the probability of selecting an individual from the group is determined by:

$$P\left(x_i\right)=\frac{f\left(x_i\right)}{{\displaystyle \sum _{i=1}^{ant}f\left(x_i\right)}},\left(i=1,2,\dots ,ant\right)$$

(12)

a roulette wheel is formed using $P\left(x_1+x_2+\dots +x_{ant}\right)=1$, where each individual has the same probability of being chosen. Then, the cumulative probability is cumulated. Based on the cumulative probability $q_i={\displaystyle {\sum }_{j=1}^{i}P\left(x_j\right)}$, $rand\left(\right)$ is used to generate a random number $r$ between $\left[0,1\right]$. If $q_{k-1}<r\le q_k$, individual $k$ is selected. This mechanism ensures not only the probability of selecting nodes with high probability but also guarantees that all nodes have a chance of being selected. It enhances the overall randomness of the ant pathfinding process and prevents the algorithm from falling into a local optimum or stagnation.

3.2.2. Pheromone Update Rules

The pheromone update mechanism significantly impacts the overall performance of ACO. The basic concept behind the ES involves identifying the solutions of the elite ants at the end of each loop. The paths of these elite ants undergo local pheromone adjustment, thereby amplifying the attractiveness of the best solution discovered so far in the subsequent loop [29].

Pheromone update rule for the elite paths is as follows:

$$\mathsf{\Delta }{\tau }_{mn}^{\mathrm{best}}=\{\begin{array}{l}e\frac{Q}{L_{\mathrm{best}}},\left(m,n\right)\in T^{\mathrm{best}}\\ 0,\hspace{1em}\hspace{1em}\mathrm{otherwise}\end{array}$$

(13)

where $\mathsf{\Delta }{\tau }_{mn}^{\mathrm{best}}$ denotes the increment of pheromone on path $\left(m,n\right)$ caused by the elite ants, $L_{\mathrm{best}}$ denotes the path length of the optimal solution found up to now, $Q$ denotes the pheromone enhancement coefficient, and $e$ denotes the adjustment parameter, which is related to the length of the elite path. The shorter the elite path length, the larger the parameter and the higher the information concentration.

Incorporating the ES into the ACO not only strengthens the positive feedback mechanism of the ACO and boosts its efficiency, but it also employs a combination of local and overall pheromone updates to prevent premature convergence of the algorithm.

3.2.3. Improved ACO

The update rule for information concentration is shown in Formula (14). And Formula (17) is the probability of node selection.

$${\tau }_{mn}\left(t+1\right)=\left(1-\rho \right){\tau }_{mn}\left(t\right)+\mathsf{\Delta }{\tau }_{mn}\left(t\right)$$

(14)

where

$$\mathsf{\Delta }{\tau }_{mn}\left(t\right)={\displaystyle \sum _{k=1}^{ant}\mathsf{\Delta }{\tau }_{mn}^k\left(t\right)+\mathsf{\Delta }{\tau }_{mn}^{\mathrm{best}}}$$

(15)

in the above equations

$$\mathsf{\Delta }{\tau }_{mn}^k\left(t\right)=\{\begin{array}{l}\begin{array}{l}\frac{Q}{L_{mn}},\mathrm{at}\mathrm{moment}t\mathrm{the}k-\mathrm{th}\mathrm{ant}\\ \hspace{1em}\hspace{1em}\mathrm{visits}\mathrm{node}n\mathrm{from}\mathrm{node}m\end{array}\\ 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{otherwise}\end{array}$$

(16)

The probability that the $k$-th ant goes from node $m$ to node $n$ is:

$$p_{mn}^k=\{\begin{array}{l}\frac{{\left[{\tau }_{mn}(t)\right]}^{\alpha }\cdot {\left[{\eta }_{mn}(t)\right]}^{\beta }}{{\displaystyle \sum _{k\in C_m}{\left[{\tau }_{mn}(t)\right]}^{\alpha }\cdot {\left[{\eta }_{mn}(t)\right]}^{\beta }}},n\in C_m\\ 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{otherwise}\end{array}$$

(17)

where ${\tau }_{mn}\left(t\right)$ denotes the concentration of pheromones between nodes $m$ and $n$ at moment $t$, $\mathsf{\Delta }{\tau }_{mn}\left(t\right)$ denotes the total concentration of pheromones released by all ants between nodes $m$ and $n$, $\mathsf{\Delta }{\tau }_{mn}^k\left(t\right)$ denotes the concentration of pheromones released by the $k$-th ant between nodes $m$ and $n$, ${\eta }_{mn}\left(t\right)=1/d_{mn}$ represents the heuristic function from node $m$ to node $n$, where $d_{mn}$ is the distance between the UAV and the task. $C_m$ denotes the set of feasible nodes around the current node $m$.

Based on the above principles, applying ACO to solve task assignment and flight path planning joint optimization problems typically involves the following key steps:

• Initialization parameters: At the beginning of the calculation, relevant parameters need to be initialized, such as ant scale $ant$, information heuristic factor $\alpha$, expectation heuristic factor $\beta$, information volatility factor $\rho \left(0<\rho <1\right)$, pheromone enhancement factor $Q$, and maximum number of iterations $K$.
• Constructing the solution space: Each ant is placed in a different initial position, and the next node each ant will access is calculated according to Equation (17) until all nodes have been accessed by the ants.
• Update pheromones: The length of each ant’s path is calculated, and the optimal solution in the current iteration count is recorded. Simultaneously, the pheromone concentration on the connecting paths of each node is updated according to Equation (14).
• Judging whether to terminate: If the number of iterations is less than $K$, the path record table of the ants is cleared and the process returns to step 2. Otherwise, the calculation is terminated and the optimal solution is output.

The flow chat of the joint optimization algorithm in this article is as in Figure 3.

4. Simulation Results and Analysis

4.1. Simulation Parameter Setting

Under the hardware conditions of Intel 2.5 GHz CPU and 16 GB of memory, simulation experiments were conducted using MATLAB 2018b. To confirm the feasibility and effectiveness of the joint optimization algorithm, we assume $N=6$ and $M=6$ on a 2D threat map spanning 100 km × 100 km. After repeated testing and experiments, we have found that when the number of ants $ant$ is set to 40, this algorithm neither converges prematurely nor reduces global optimality. When the maximum number of iterations $K$ is set to 100, the operation time is shorter and it will not fall into local optima. The optimization selection of parameters such as information heuristic factor $\alpha$, expectation heuristic factor $\beta$, information evaporation factor $\rho$, and pheromone enhancement factor $Q$ is shown in

Table 1. Simulation parameter settings.

Parameters	Notation	Value
Number of ants	$ant$	40
Maximum number of iterations	$K$	100
Information heuristic factor	$\alpha$	1
Expectation heuristic factor	$\beta$	7
Information evaporation factor	$\rho$	0.3
Pheromone enhancement factor	$Q$	1

. The information about the UAVs is provided in

Table 2. Information on UAVs.

UAV No.	Placement (km)	Value Gains	Maximum Range (km)	Payload
1	(2.5, 97.5)	8	200	3
2	(87.5, 92.5)	7	200	5
3	(42.5, 27.5)	9	200	4
4	(97.5, 37.5)	7	200	3
5	(67.5, 57.5)	6	200	5
6	(27.5, 47.5)	8	200	4

, while the details of task point information are given in

Table 3. Information on task points.

Task No.	Placement (km)	Value Gains
1	(62.5, 97.5)	4
2	(7.5, 77.5)	6
3	(12.5, 22.5)	5
4	(72.5, 7.5)	8
5	(97.5, 67.5)	9
6	(42.5, 57.5)	7

.

The position details of fixed obstacles are outlined in

Table 4. Position of fixed obstacles.

Threat	Vertex 1 (km)	Vertex 2 (km)	Vertex 3 (km)	Vertex 4 (km)
Threat 1	(0, 0)	(0, 15)	(15, 0)	(15, 15)
Threat 2	(45, 75)	(45, 80)	(50, 75)	(50, 80)
Threat 3	(30, 5)	(30, 20)	(50, 5)	(50, 20)
Threat 4	(75, 15)	(75, 30)	(90, 15)	(90, 30)
Threat 5	(45, 85)	(45, 100)	(55, 85)	(55, 100)

. In this simulation, active threats are symbolized by radars and anti-aircraft guns, with their positional information provided in

Table 5. Position of active threat obstacles.

Threat	Placement (km)	Radius of Action (km)
Radar 1	(57.5, 42.5)	2.5
Radar 2	(77.5, 77.5)	2.5
Anti-aircraft gun	(27.5, 72.5)	2.5

.

4.2. Simulation Results and Analysis

To compare the planning results and objective function values of the heterogeneous UAV cluster under varying threat environments, simulations are conducted under the following three scenarios:

• Scenario 1: The threat source is solely composed of fixed obstacles.
• Scenario 2: The threat source comprises fixed obstacles and an anti-aircraft gun.
• Scenario 3: The threat includes fixed obstacles, an anti-aircraft gun, radar 1, and radar 2.

In the simulation result figures, the green rectangle depicts the threat range of fixed obstacles, the blue circle denotes the threat range of the anti-aircraft gun, and the red circle signifies the threat range of the radar.

The joint optimization results and objective function curves of task assignment and flight path planning for Scenario 1 are shown in Figure 4 and Figure 5, respectively. Figure 4 reveals the task assignment results as follows: UAV1→Task6, UAV2→Task5, UAV3→Task 3, UAV4→Task1, UAV5→Task4, and UAV6→Task2. Figure 5 shows that the range of values of the objective function for Scenario 1 is between 0.4 and 0.455. The joint optimization results and objective function curves of task assignment and flight path under Scenario 2 are given in Figure 6 and Figure 7, respectively. As can be seen in Figure 6, the results of task assignment are: UAV1→Task2, UAV2→Task5, UAV3→Task4, UAV4→Task6, UAV5→Task1, and UAV6→Task3. As can be seen in Figure 7, the range of values of the objective function under Scenario 2 is between 0.6 and 0.65. The joint optimization results and objective function curves of task assignment and flight path under Scenario 3 are given in Figure 8 and Figure 9, respectively. From Figure 8, it can be seen that the results of task assignment are: UAV1→Task2, UAV2→Task5, UAV3→Task4, UAV4→Task1, UAV5→Task6, and UAV6→Task3. From Figure 9, it can be seen that the range of values of the objective function under Scenario 3 is between 0.65 and 0.75. In summary, as the complexity of the threat scenarios increases, resulting in different task assignment outcomes, the objective function takes on larger and larger values. This indicates that the algorithm proposed in this paper can effectively utilize the payload resources and enhance the combat effectiveness of a heterogeneous UAV cluster.

To prove the superiority of the algorithm proposed in this paper, it will be compared with the following two algorithms, and their performance differences will be analyzed:

• Task assignment algorithm: Tasks are assigned to UAVs under various constraints to accomplish the overall mission. Subsequently, the results of task assignment are used as inputs for flight path planning, ignoring the coupling between the two.
• Trajectory planning algorithm: A feasible path is generated under the satisfaction of internal or external constraints such as minimum turning radius, minimum trajectory segment length, and environmental variables. Unlike the task assignment algorithm, it does not thoroughly consider value-gains-related matters.

The assignment projects of the task assignment algorithm and trajectory planning algorithm in the three scenarios are summarized in

Table 6. The assignment project in Scenario 1.

UAV No.	Task Assignment Algorithm	Trajectory Planning Algorithm
1	—	Task2
2	Task5→Task6	Task1
3	Task3→Task2	Task3
4	—	Task4
5	Task4	Task5
6	Task1	Task6

,

Table 7. The assignment project in Scenario 2.

UAV No.	Task Assignment Algorithm	Trajectory Planning Algorithm
1	Task2	Task2
2	Task5→Task6	Task5
3	Task3	Task4
4	—	Task1
5	Task4	Task6
6	Task1	Task3

and

Table 8. The assignment project in Scenario 3.

UAV No.	Task Assignment Algorithm	Trajectory Planning Algorithm
1	—	Task2
2	Task1→Task6	Task5
3	Task3→Task2	Task4
4	Task5	Task6→Task1
5	Task4	—
6	—	Task3

. The position coordinates of the UAVs, the position coordinates of the task points, and the threat environment are consistent with Section 4.1. By analyzing the data in the tables, we can draw the following conclusions:

• In Scenario 1, the heterogeneous UAV cluster completed all tasks using the task assignment algorithm. However, UAV1 and UAV4 in the cluster were not assigned any tasks, while UAV2 and UAV3 were assigned two tasks each. Conversely, using the trajectory planning algorithm, the cluster completed all tasks and assigned each UAV a task;
• In Scenario 2, the heterogeneous UAV cluster completed all tasks using the task assignment algorithm, but UAV4 in the cluster was not assigned any tasks, while UAV2 was assigned two tasks. In the same scenario, the cluster completed all tasks and assigned each UAV a task using the trajectory planning algorithm;
• In Scenario 3, the heterogeneous UAV cluster completed all tasks using the task assignment algorithm, but UAV1 and UAV6 in the cluster were not assigned any tasks, while UAV2 and UAV3 were assigned two tasks each. In the same scenario, the cluster also completed all tasks using the trajectory planning algorithm, but UAV5 was not assigned a specific task, while UAV4 was assigned two tasks.

In summary, while ensuring the successful completion of tasks, the task assignment algorithm shows that UAVs have “free time” in all three scenarios, and the trajectory planning algorithm also exhibits “free time” in Scenario 3. Therefore, the trajectory planning algorithm outperforms the task assignment algorithm in terms of resource utilization for UAVs. However, the algorithm proposed in this paper does not exhibit this phenomenon, indicating that resource allocation is more balanced across all three scenarios.

To further demonstrate the superiority of the algorithm proposed in this paper, the convergence values of the objective functions of the six UAVs in the cluster were summed to obtain the targeted consolidated cost, as depicted in Figure 10. Based on this figure, it is possible to infer the following:

• The targeted consolidated cost of the algorithm proposed in this paper is higher than that of the other two algorithms in the three scenarios, corroborating that the algorithm can fully leverage the UAV resources and enhance the effectiveness of cluster combat. This indicates that the algorithm introduced in this study offers distinct advantages in addressing issues related to task assignment and joint flight path planning optimization;
• The targeted consolidated cost of the task assignment algorithm is more expensive than that of the trajectory planning algorithm in each scenario. Given the environment established in this study, the task assignment algorithm proves more beneficial than the trajectory planning algorithm;
• An upward trend is observed in the targeted consolidated value of all three algorithms as the complexity of the scenario increases. This suggests that the environment significantly influences all three algorithms.

5. Conclusions

In this paper, a joint optimization algorithm is developed for task assignment and flight path planning for a heterogeneous UAV cluster in an MMS. The primary objective of this algorithm is to employ optimization techniques in order to minimize range, maximize value gain, and enhance survival probability, thus improving the utilization of UAV payload and effectiveness of cluster operations under the constraints of task payload, range, and task requirement. The formulated multi-objective, non-linear, and non-convex optimization problem is tackled using the ACO with ES. This approach introduces the RWS principle and ES perfectly, ensuring effective optimization. The simulation results show task assignment and flight path planning results are different where in various threat environments, but the algorithm in this article always has the highest targeted consolidated cost compared with the other two common algorithms. In summary, this joint optimization algorithm has the ability to enhance the combat effectiveness of a heterogeneous UAV cluster and has significant advantages over the other two algorithms.

Looking ahead, our research will not be confined to 2D simulation environments. Instead, we will consider more complex 3D threat environments. Also, taking into account the unequal number of UAVs and tasks in a cluster, we plan to propose more effective algorithms to further enhance the combat effectiveness of a heterogeneous UAV cluster.