Dynamic Task Allocation of Multiple UAVs Based on Improved A-QCDPSO

Abstract

With the rapid changes in the battlefield situation, the requirement of time for UAV groups to deal with complex tasks is getting higher, which puts forward higher requirements for the dynamic allocation of the UAV group. However, most of the existing methods focus on task pre-allocation, and the research on dynamic task allocation technology during task execution is not sufficient. Aiming at the high real-time requirement of the multi-UAV collaborative dynamic task allocation problem, this paper introduces the market auction mechanism to design a discrete particle swarm algorithm based on particle quality clustering by a hybrid architecture. The particle subpopulations are dynamically divided based on particle quality, which changes the topology of the algorithm. The market auction mechanism is introduced during particle initialization and task coordination to build high-quality particles. The algorithm is verified by constructing two emergencies of UAV sudden failure and a new emergency task.

1. Introduction

Multiple unmanned aerial vehicle (UAV) swarms are currently widely used in various fields, including disaster management [1,2,3,4], telecommunications [5,6], and cooperative operations [7,8,9,10,11]. Among them, the dynamic allocation of multi-UAV tasks is the key problem in the cooperative operations of formations, whose purpose is to use the resource sharing and coordination of operations of the UAV group to reasonably select the formation task plan, so as to improve the cooperative operational efficiency of the UAV group, avoid the paralysis of our UAV groups caused by the dynamic changes of the battlefield and increase the probability of the fleet completing the task.

In terms of system division, the problem of dynamic task allocation can be divided into centralized task allocation and distributed task allocation [7,8,9,10,11]. At present, scholars have conducted a large body of research on task allocation and have achieved a series of results. The related research works mainly use intelligent algorithms (ant colony algorithms [12,13,14,15], genetic algorithms [16,17,18], particle swarm algorithms [19,20,21,22], artificial neural networks [23], etc.), and contract network algorithms [24,25,26] to solve task coordination problems in a distributed architecture. Considering long-term benefits and current benefits, [27] proposes a distributed deep compression algorithm, and a distributed quick compression algorithm and adopts a distributed framework to complete task optimization. In view of the rapid response characteristics of multiple UAVs in a dynamic environment, [28] extends the consensus-based bundling algorithm to quickly allocate new tasks without completely redistributing existing tasks. Based on task and the UAV group, [29] establishes the state information model of the UAV and UAV group, and solves the problem by improving particle swarm algorithm and distributed auction algorithm. The authors of [30] propose a game theory method based on predator–prey particle swarm optimization (PP-PSO), which models the problem as a two-player game, and considers the optimal task plan at each stage as a mixed strategy Nash balance solved by the PP-PSO algorithm. The authors in [31] take into account the situation that the UAV is performing tasks in the bidding stage of the contract network and the dynamic factors in the task allocation problem, which improved the adaptability of the multi-agent system to the dynamic environment. However [27,28,29,30], does not consider the dynamic task allocation when the task performer changes, such as sudden failure; and [31] does not consider the situation of multi-agent performing tasks together. In conclusion, the existing research mainly focuses on the simplex platform and limited task characteristics, and the research on the dynamic allocation of UAV tasks is still insufficient.

Aiming at solving the above problems, this paper uses a hybrid architecture to design auction quality clustering discrete particle swarm optimization (A-QCDPSO), which solves dynamic task allocation problems based on the pre-allocation scheme in the case of a change in the battlefield. In Section 2, the multi-UAV dynamic task allocation model is established; in Section 3, the A-QCDPSO algorithm is proposed by adopting the dynamic subpopulation strategy and the market auction mechanism based on the DPSO algorithm; and in Section 4, the simulation experiments are performed to verify the effectiveness of the proposed algorithm from the two aspects of effectiveness and timeliness.

2. Problem Description

This paper studies the dynamic task allocation of multi-UAVs attacking multi-ground targets which are all visible for two situations: the new emergency task and the sudden failure of a UAV. For UAVs on their duties, the new relationship between the tasks and UAVs is necessary to be determined when new emergency tasks and the sudden failure of UAVs occur. The problem we aim to solve is to determine for each UAV which targets are its responsibility, and the sequence of attack if it is responsible for more than one target, where the damage capability, survival capability, total flight range, ground target detection capability, and task scheduling of the UAV should be considered.

2.1. Definitions and Models

UAV model: The UAV set is $U=\left\{U_i\right|i=1,2,\dots ,u\}$, $u$ is the number of UAVs, $U_i$ means the i-th UAV. The set of the UAV’s attributes is:

(1)$U_i=\{U^{ID},U^L,U^V,U^W,U^R,U^{PI},U^{PA},U^{PD}\}$

Among them:

$U^{ID}\subset Z^{+}$—The set of the UAV identification;

$U^L$—The set of the UAV three-dimensional position coordinates;

$U^V\subset R^{+}$—The set of the UAV’s own value;

$U^W\subset Z^{+}$—The set of the maximum number of weapons that the UAV carries;

$U^R\subset R^{+}$—The set of the maximum combat radius;

$\left\{U^{PI}|0\le U_{ij}^{PI}\le 1\right\}$—The set of UAV survival probability when performing a task;

$\left\{U^{PA}|0\le U_{ij}^{PA}\le 1\right\}$—The set of UAV damage probability when attacking a target;

$\left\{U^{PD}|0\le U_{ij}^{PD}\le 1\right\}$—The set of UAV detection probability when detecting a target.

Task model: Task collection is $T=\left\{T_j\right|j=1,2,\dots ,t\}$, $t$ is the number of tasks, $T_j$ means the j-th task. Detection and attack are the two main tasks considered in this paper. The set of tasks’ attributions is:

(2)$T_i=\{T^{ID},T^L,T^V,T^{Sep},T^{Type}\}$

Among them:

$T^{ID}\subset Z^{+}$—The set of the task identification;

$T^L$—The set of the task three-dimensional position coordinates;

$T^V\subset R^{+}$—The set of the task’s own value;

$T^{Sep}$—The set of the timing relationship between tasks, 1 for $T_i$ before

$T_j$ and non 1 for no timing constraint;

$T^{Type}\subset \left\{1,2\right\}$—The set of task types, 1 stands for detection mission and 2 stands for attack mission.

Task decision variables:

(3)$X_{ij}=\{\begin{array}{l}0\\ 1\end{array}\begin{array}{cc}& i=1,2,\dots ,u,j=1,2,\dots ,t\end{array}$

where $X_{ij}$ is the decision variable for the UAV $U_i$ to perform the task $T_j$, $X_{ij}=0$ means that the UAV does not perform the task, while $X_{ij}=1$ means that the UAV performs the task.

2.2. Performance Indies

Overall benefit: The overall benefit of the mission plan is the sum of the benefits obtained by the UAV formation to perform detection and attack tasks, which is the product of the mission value and success probability. When UAV $U_i$ completes a detection or attack task $T_j$, the benefit can be expressed by $U_{ij}^{PD}{T}_j^V$ or $U_{ij}^{PA}{T}_j^V$. Then, the total benefit $R_T$ is the sum of the benefit of all single UAV values completing a task $T_j$:

(4)$R_T={\displaystyle \sum _{i=1}^u{\displaystyle \sum _{j=1}^t(U_{ij}^{PD}{T}_j^V+U_{ij}^{PA}{T}_j^V)X_{ij}}}$

Threat cost: The threat cost of the task plan is the sum of the threat cost to all UAVs during the task, which is the synthesis of the value and survival probability of the UAV. Assuming that UAV $U_i$ performs $t$ tasks $T_j(j=j_1,j_2,j_3,\dots ,j_t)$, the survival probability of $U_i$ from $t$ tasks is $1-{\displaystyle \prod _{j=j_1}^{j_t}{U}_{ij}^{PI}}$. Then, the threat cost $C_T^{risk}$ caused by the UAV formation to perform tasks is as follows:

(5)$C_T^{risk}={\displaystyle \sum _{i=1}^u((1-{\displaystyle \prod _{j=j_1}^{j_k}{U}_{ij}^{PI}})U_i^V)}$

Range cost: The range cost of the task plan is the sum of the flight range after the completion of the task by all UAVs. Because the actual range of the UAV is unknown at the time of the task allocation, the range of the UAV is calculated by using an estimation method.

Assuming that a UAV performs $t$ tasks $T_j(j=j_1,j_2,j_3,\dots ,j_t)$ in sequence, the range cost ${C_i^{dis}}^{\prime }$ caused by the task is as follows:

(6)${C_i^{dis}}^{\prime }=\sqrt{{(U_i^L{}_x-T_j^L{}_x)}^2+{(U_i^L{}_y-T_j^L{}_y)}^2}+{\displaystyle \sum _{l=j_1}^{j_t-1}\sqrt{{{(\mathrm{T}}_{l+1}^L{}_x-T_l^L{}_x)}^2+{{(\mathrm{T}}_{l+1}^L{}_y-T_l^L{}_y)}^2}}$

Assuming that there are some threats in the battlefield environment, this paper approximates all threats as circles to modify the UAV range. Furthermore, the UAV flies along the edge of the threat area when meeting it, which is shown by the solid line in Figure 1. Threat collection is $R=\left\{R_k\right|k=1,2,\dots ,r\}$, $r$ is the number of threats, $R_k$ means the k-th task. The set of threat’s attributes is:

(7)$R_k=\{R^{ID},R^L,R^r\}$

Among them:

$R^{ID}\subset Z^{+}$—The set of the threat identification;

$R^L$—The set of the threat center location;

$R^r$—The set of the threat radius.

Define the shortest distance between a threat $R_k$ to the UAV’s task flight path as $d_{R_k}$, then the UAV’s modified range cost $C_i^{dis}$ can be expressed as follows:

(8)$C_i^{dis}={C_i^{dis}}^{\prime }+{\displaystyle \sum _{k=1}^{K}2\delta (k)(\arccos (\frac{d_{R_k}}{r_{R_k}})r_{R_k}}-\sqrt{r_{R_k}{}^2-d_{R_k}{}^2})$

(9)$\delta (k)=\{\begin{array}{c}\begin{array}{ll}0& d_{R_k}\ge r_{R_k}\end{array}\\ \begin{array}{cc}1& d_{R_k}<r_{R_k}\end{array}\end{array}$

The total range cost $C_T^{dis}$ is:

(10)$C_T^{dis}={\displaystyle \sum _{i=1}^u{C}_i^{dis}}$

2.3. Problem Formulation

The multi-UAV task allocation problem can be formulated as the following optimization problem.

(11)$\begin{array}{l}\mathrm{s}.\mathrm{t}.\{\begin{array}{ll}{\displaystyle \sum _{j=1}^t{X}_{ij}\le U_i^W}\hfill & (T_j\mathrm{is}\mathrm{attack}\mathrm{task})\hfill \\ C_i^{dis}\le U_i^R\hfill & \forall U_i\in U\hfill \\ {\displaystyle \sum _{i=1}^t{X}_{ij}\le 1}\hfill & \forall U_i\in U\hfill \end{array}\\ \max E={\omega }_1\frac{T^R}{T^V{}_{\max }}+{\omega }_2\left(1-\frac{C_T^{\mathrm{risk}}}{U^V{}_{\max }}\right)+{\omega }_3\left(1-\frac{C_T^{\mathrm{dis}}}{di{s}_{\max }}\right)\end{array}$

The objective function maximizes the effectiveness function E of the UAV task allocation plan, which includes three factors: the overall benefit $R_T$, the threat cost $C_T^{risk}$, and the range cost $C_T^{dis}$; ${\omega }_1,{\omega }_2,{\omega }_3$ are the weights of the above three factors, which are directly determined by expert experience; $T^V{}_{\max }$ is the maximum value of tasks in the set; $U^V{}_{\max }$ is the maximum value of UAVs in the set; $di{s}_{\max }$ is the shortest perimeter of the area composed of all task points calculated using the convex hull algorithm [32] according to the task coordinate distribution. The first constraint represents the maximum number of UAV attack task constraints, which indicates the number of attack tasks performed that cannot exceed the number of air-ground weapons mounted on it. The second constraint represents the range constraint of the UAV. The last constraint represents that each mission can be executed by at most, one UAV.

3. Task Allocation Based on A-QCDPSO

The particle swarm optimization (PSO) algorithm is a simple, efficient, and easy-to-implement heuristic optimization algorithm, which is widely used in various optimization scenarios. Therefore, this paper proposes a method to solve the optimization problem based on the PSO algorithm. However, its original purpose is to solve the optimization problem with continuous function in continuous space. Furthermore, the problem of multi-UAV cooperative dynamic task allocation is a multi-constraint multi-objective, discrete optimization problem. This paper designs a particle coding strategy and other strategies to realize the transformation from a continuous PSO algorithm to the discrete particle swarm optimization (DPSO) algorithm suitable for discrete problems. In addition, aiming at the problem of the poor-quality solution, and falling into local optimum easily, this paper proposes the A-QCDPSO algorithm by introducing the dynamic subpopulation strategy and the market auction mechanism into the DPSO algorithm to meet the requirements of timeliness of the dynamic task allocation problem, as shown in Figure 2. The dynamic subpopulation strategy guarantees the search space of the internal particles of the subpopulation, which ensures the diversity of the population to some extent. The market auction mechanism can initialize some particles to ensure the quality of the initial solution; meanwhile, for the task coordination problem of the illegal solution, it makes the UAV decide to bid on the principle of efficiency maximization to ensure the efficient solution of the task coordination process.

3.1. Transformation from PSO to DPSO

3.1.1. Particle Coding Strategy

PSO simulates the birds in a flock by designing a massless particle, whose method is called particle coding strategy. Particle coding strategy is a mapping method between algorithm expression and subjective thought expression. In addition, the coding operation is able to complete the conversion by continuing to the discrete problem, fully considering the restrictions, and naturally excluding part of the illegal solutions that do not meet the restrictions to reduce the identification and processing of illegal solutions in subsequent operations, which improves the efficiency of the algorithm.

The two-dimensional task allocation matrix and sequence matrix are used as encoding methods in this paper. Among them, the task allocation matrix is composed of task decision variables, indicating whether the UAV executes the task; the task sequence matrix represents the sequence of tasks, where the i-th row uses real numbers to represent the tasks’ sequence performed by the UAV $U_i$ and uses 0 to represent tasks that are not assigned. The particle encoding method is shown in Figure 3.

After particle decoding, the UAV $U_1$ executes the task sequence as $T_N\to T_2$. Therefore, the encoding method can represent the mapping relationship between the particle and the solution, which can clearly describe the task allocation scheme and the sequence of performing tasks. Because the task sequence matrix determines the order of performing tasks through the comparison of the element magnitude, the number of illegal solutions caused by rounding can be reduced.

3.1.2. Particle Update Strategy

In each iteration, the particle in the task allocation matrix and task sequence matrix updates its position through two “extreme values”. The first is the optimal solution found by the particle itself (denoted as $P_i^k$), and the other is the global optimal solution found by the subpopulation (denoted as $P_g^k$). The particles use “extreme value” to calculate the speed, and thus update their position.

(12)$V_i^{k+1}=\omega V_i^k+c_{1}rand(0,1)(P_i^k-X_i^k)+c_{2}rand(0,1)(P_g^k-X_i^k)$

(13)$X_i^{k+1}=X_i^k+V_i^{k+1}$

The above equations represent the strategy for the k-th update of particle i. $\omega$ represents the inertia weight; $X_i^k$ and $V_i^k$ are the current position and velocity of the particle; $c_1$ and $c_2$ are the historically optimal and globally optimal learning factors; $V_i^{k+1}$ is the update speed of the particles; $X_i^{k+1}$ is the position of the particle at the next iteration; $P_g^k$ and $P_i^k$ represent the global optimal position and historical optimal position, respectively.

3.2. Dynamic Subpopulation Strategy Based on Particle Quality Clustering

The task allocation problem may be a multi-peak optimization problem, resulting in the particles with better fitness in the different positions of the search space. Compared with the DPSO algorithm, the dynamic subpopulation strategy—based on particle quality clustering—guarantees the search space of the internal particles of the subpopulation. Therefore, the divided particles can fully search the space according to the cluster center of the subpopulation by the dynamic subpopulation strategy, which ensures the diversity of the population to some extent.

The core idea of the dynamic subpopulation strategy based on particle quality clustering is to sort all the particles according to fitness and select particles to form subpopulations according to the relevant parameters. The dynamic subpopulation strategy inputs subpopulation parameters and all particles, and outputs the divided subpopulation by sorting particles according to the iteration interval and the fitness. Please refer to [33] for detailed steps of the strategy.

3.3. Market Auction Mechanism

The market auction algorithm is similar to the auction mechanism of the human economic market. It is essentially a task coordination mechanism based on the search tree method [34,35]. The auction algorithm imitates the auction behavior between humans and obtains the optimization scheme through the information transmission and sharing mechanism between bidders and auctioneers to solve the optimization problems.

The market auction mechanism, which is integrated into PSO to apply to the UAV cooperative task allocation problem, can initialize some particles to ensure the quality of the initial solution. Meanwhile, for the task coordination problem of the illegal solution, it makes the UAV decide to bid on the principle of efficiency maximization to ensure the efficient solution of the task coordination process.

When solving the task allocation problem, the UAV that needs to allocate its own tasks becomes the auctioneer, and others become the bidders. The tasks flow within the formation system as a lot. The bidder adds the task to the sequence to complete the auction when signing the contract with the auctioneer. Through the auction, the auctioneer designates the highest bidder to accept the lot and completes the task distribution among multiple UAVs.

For the multi-UAV task allocation problem, the auction algorithm is described as follows [36]:

(14)$Auction=<T,A,B,G,C,J>$

$T=\{T_1,T_2,\dots ,T_N\}$ is the set of tasks to be completed. $A=\{A_1,A_2,\dots ,A_a\}$ is the set of UAVs performing auction operations. $B=\{B_1,B_2,\dots ,B_b\}$ is the set of auction UAVs participating in the auction. $G=\{G_{U_1{T}_1},\dots ,G_{U_1{T}_N},\dots ,G_{U_i{T}_j},\dots ,G_{U_M{T}_N}\}$ is the set of proceeds for the UAV to complete the task, and $G_{U_i{T}_j}$ is the benefit of the UAV $U_i$ after completing the task $T_j$. $C=\{C_{U_1{T}_1},\dots ,C_{U_1{T}_N},\dots ,C_{U_i{T}_j},\dots ,C_{U_M{T}_N}\}$ is the cost set for the UAV to complete the task, and $C_{U_i{T}_j}$ represents the cost for the UAV $U_i$ to complete the task $T_j$. $J=\{J_{U_1{T}_1},\dots ,J_{U_1{T}_N},\dots ,J_{U_i{T}_j},\dots ,J_{U_M{T}_N}\}$ is the bidding price set for the bidding UAV, $J_{U_i{T}_j}$ represents the bidding price of the UAV $U_i$ for task $T_j$. $i\in \left(0,M\right]$, $j\in \left(0,N\right]$, where M and N are positive integers.

3.3.1. Design of Auction Efficiency Function

This paper takes multi-UAV cooperative air-to-ground combat as the task background, which covers two types of detection and attack tasks. Aiming at the negotiation process between the internal auction UAV and the bidding UAV in the formation, a reasonable auction efficiency function is designed to evaluate the auction negotiation process. In this paper, the overall effectiveness E is obtained by (8) as the auction efficiency function.

3.3.2. The Rule of Maximum Efficiency Based on Matrix Full Arrangement

The task allocation scheme of the UAV $U_i$ can be regarded as a task set containing the task execution sequence $S_i=\{T_1,T_2,\dots ,T_n\}$. The flight range of the UAV to perform the task is different because of the different task execution sequence, so the task plan efficiency of the UAV calculated by the range cost is different. Therefore, in order to ensure the optimality of the UAV task execution plan, it is necessary to determine the order in which the UAV performs new tasks to maximize its effectiveness.

• Matrix arrangement

The task matrix of a certain UAV is constructed as a $1\times n$ matrix by the n tasks in its task set to express the task’s execution plan of it. Matrix arrangement is to arrange all elements of it. The number of the types of matrix arrangements with n elements is calculated as follows:

(15)$P_n=n\cdot (n-1)\cdot (n-2)\cdot \cdot \cdot 2\cdot 1=n!$

Since the auctioneer randomly selects a task in the task set for auction during each auction transaction, for the complete arrangement of a single UAV, it only needs to be arranged on the basis of the results of the last auction transaction in an inserted manner to obtain arrangements of $n$ task schemes. Then, calculate the effectiveness of each arrangement and select the arrangement scheme with the maximum effect as the execution plan for this UAV task.

For example, the current task execution plan of the UAV $U_i$ is $T_1\to T_3\to T_2$. After the auctioneer releases the task, the complete arrangement of the task matrix of the UAV is shown in Figure 4.

• 2.. Analysis of changes in auction performance

The auction transaction is a process of negotiation between the UAVs. The bidding UAVs select the appropriate price to participate in the auction according to the amount of change in efficiency after buying/selling a certain task. From the above analysis, we know that for a certain UAV task set S, different sequences of tasks will greatly affect the overall evaluation of the UAV’s tasks. Therefore, in the process of auction transactions, UAVs need to use their maximum effectiveness as a criterion and rely on independent decision-making to select the optimal task execution plan to participate in the auction.

The evaluation criterion for auction transactions is the amount of change in the effectiveness of the UAV’s task. UAV $U_i$ achieves a different efficiency by completing tasks in the task set $S_i=\{T_1,T_2,\dots ,T_n\}$ in different orders. Assuming that the number of fully arranged tasks is $P_n$, the maximum efficiency of the UAV in performing tasks is:

(16)$E(S_i)=\underset{\lambda \in P_n}{\max }E(\lambda )$

After the UAV buys the task $T_{n+1}$ at the auction transaction, the maximum efficiency of the UAV is:

(17)$E(S_i\cup T_{n+1})=\underset{\lambda \in P_n^{\prime }}{\max }E(\lambda )$

Therefore, the price of the UAV participating in the auction is the amount of effectiveness’ change of the UAV:

(18)$\Delta E=E(S_i\cup T_{n+1})-E(S)$

3.4. A-QCDPSO Algorithm

The A-QCDPSO algorithm uses the PSO as the main operating process. The PSO is transformed to DPSO by particle coding strategy, and the particle update strategy in the basic PSO is used. Then, the dynamic subpopulation strategy is introduced to divide the particle group; and the market auction mechanism is introduced to initialize some particles and coordinate the illegal solution.

The flow process of the A-QCDPSO algorithm is shown in Figure 5. The specific implementation steps are as follows:

Step 1: Initialize the particle number PN, accuracy requirements, subpopulation size, dynamic subgroup iteration interval ∆t, and the maximum number of iterations PT, and enter the mission pre-allocation plan.

Step 2: Based on the mission pre-allocation scheme, initialize some particles using an auction mechanism.

Step 3: Calculate the objective function value of each particle and sort the particles according to the objective function value.

Step 4: Determine whether the number of iterations meets the iteration interval of the dynamic subgroup. If it does, the sorted particles are generated according to the dynamic subgroup strategy and the size of the subpopulation; otherwise, the atomic population is used.

Step 5: Calculate the particle’s own optimal solution $P_i^k$ and the optimal solution $P_g^k$ of the subpopulation in which the particle is located, update the particle velocity/position, and calculate the corresponding objective function value.

Step 6: Screen illegal solutions according to the constraints of the problem to be solved, introduce an auction mechanism, select auction UAVs and bid UAVs, and adjust the elements of the illegal solutions that do not meet the constraints in all dimensions to meet the requirements.

Step 7: Determine whether the maximum number of iterations is reached. If it has been reached, go to Step 8; otherwise, go to Step 3.

Step 8: Calculate the fitness of each particle and select the particle with the best fitness as the resulting output.

4. Simulation

In order to verify the effectiveness of the A-QCDPSO algorithm in solving the problem of dynamic task allocation, this paper considers two emergencies: the sudden failure of UAV in the formation, and the new emergency task to construct multi-UAV ground detection/attack simulation examples. The fitness is used as the evaluation index. Besides, in order to verify the timeliness of the A-QCDPSO algorithm, the time to obtain the optimal solution of it is compared with that of the QCDPSO algorithm and the contract network distributed coordination algorithm in the above-mentioned two battlefield emergencies to verify the superiority of the proposed algorithm.

4.1. Simulation Setup

Determine the particle size $PN=40$, the maximum number of iterations of the algorithm $PT=50$, the inertia weight $\omega =0.6$, the number of subpopulations is 5, each subpopulation contains 8 particles, the acceleration factor $c_1=c_2=1.5$. Particle initialization and task coordination are performed in the form of a single auction winning bid, and 10 of the particles are initialized through an auction algorithm.

Assuming that there are 8 UAVs to perform 12 air-to-ground detection/attack missions, the situation information of both sides is shown in Table 1, Table 2, Table 3, Table 4, Table 5 and Table 6.

After the pre-allocation operation of UAV collaborative tasks, the task pre-allocation scheme is obtained, as shown in Table 7.

4.1.1. Sudden Failure of UAV

Assume UAVs $U_1$ and $U_5$ cannot perform combat tasks due to unexpected situations during the process of their tasks.

4.1.2. New Emergency Task

Suppose that during the process of the UAV’s task, there are three new emergency tasks, whose information is shown in Table 8, Table 9, Table 10 and Table 11.

4.1.3. Comparison Setup

In the comparison simulation, the A-QCDPSO algorithm, the contract network distributed coordination algorithm, and the QCDPSO algorithm are compared in the two battlefield emergencies with the same parameters and the coding method.

4.2. Simulation Result and Analysis

4.2.1. Sudden Failure of UAV

Figure 6 and Figure 7 show the changes in the fitness of the task allocation process, respectively, before and after the UAV’s sudden failure and the final task allocation results.

The formation efficiency changes before and after the UAV failure, and is shown in Figure 6. When the algorithm iterates 51 times, the UAVs $U_1$ and $U_5$ suddenly fail, and the overall efficiency decreases. With the increase in the number of optimizations, the overall effectiveness of the formation is on the rise, and finally reaches the maximum efficiency value of 2.8765 after 10 iterations. When the market auction mechanism is introduced into the PSO for dynamic task allocation, it can be seen that the algorithm can obtain a better solution in fewer iterations than the task pre-allocation.

After the UAV suddenly breaks down, the task re-allocation is performed on the basis of the pre-allocation plan. The final task allocation plan is shown in Table 12.

In the process of the UAV formation task execution, UAVs $U_1$ and $U_5$ cannot continue their tasks due to the sudden failure. At this time, the task sets $T_{10},T_{11},T_{12}$ become an unassigned task and needs to be reassigned. Based on the current task allocation scheme that excludes UAVs $U_1$ and $U_5$, the particles are iteratively optimized through the A-QCDPSO algorithm model in order to pursue a better solution under the current situation in a shorter time. From the final dynamic allocation scheme, it can be seen that the task sequence of some UAVs has not changed, and the other part has made major changes in order to adapt to the current situation.

4.2.2. New Emergency Task

Figure 8 and Figure 9 show the changes in the fitness of the task allocation process, respectively, before and after the new emergency tasks and the final task allocation results.

The overall effectiveness of the formation before and after the new emergency task is changed as shown in Figure 8. The emergency tasks are added when the algorithm iterates 51 times. The initial efficiency of the algorithm is low, and as the number of optimization times of the algorithm increases, the overall efficiency of the formation is on the rise. The algorithm finally completes the mining of the better solution after 10 iterations and continues to optimize to reach the maximum efficiency value of 3.6952.

After adding new tasks, the tasks are reassigned based on the pre-allocation plan. The final task allocation plan is shown in Table 13.

During the process of the UAV formation task execution, the superior suddenly issues three tasks. At this time, task sets $T_{13},T_{14},T_{15}$ become unassigned tasks and need to be reassigned. Taking the initial task pre-allocation scheme as the basic scheme, the particles are initialized on the basic scheme through the single auction mechanism, and the particles are iteratively optimized through the A-QCDPSO algorithm model to seek a better solution in the current situation. It can be seen from the situation that the three new emergency tasks are more dispersed in space, and different UAVs have different capabilities for different tasks. Because of the limitation of the maximum number of tasks that the UAV can perform, the task allocation scheme is shown in Table 13. It can be seen that the task sequence of some UAVs has not changed, but most UAVs have adjusted the task execution plan due to subjective and objective factors.

Based on the above two sets of simulation results, the A-QCDPSO algorithm model proposed in this paper can solve the problem of dynamic task allocation of multi-UAVs and can find a better solution to the problem in a shorter time. According to the simulation analyses of two unexpected situations, such as the sudden failure of the UAV and new emergency tasks, the algorithm has achieved ideal results.

4.2.3. Comparison Result

The time comparison for the three algorithms to obtain the optimal solution under the two battlefield emergencies is shown in Figure 10.

In order to ensure the fairness of the experimental results and avoid the randomness of the algorithm optimization in a few simulations, 50 simulations are carried out for the 3 optimization algorithms, respectively, and the final optimization results are counted, as shown in Table 14.

Based on the comparison of the solution time of the 3 algorithms in 1 simulation experiment and the average solution time of the 3 algorithms in 50 simulation experiments, the A-QCDPSO algorithm proposed in this paper is significantly optimized for the task allocation solution time compared with the QCDPSO algorithm and has certain advantages in timeliness compared with the traditional contract network distributed algorithm, which shortens the reaction time and improves the efficiency of command decision and the operational efficiency of the OODA loop in the formation operations.

5. Conclusions

The problem of dynamic task allocation of multiple UAVs is a discontinuous optimization problem, which needs to respond quickly when the battlefield environment changes. Aiming at this problem, this paper adopts a hybrid architecture and designs an improved discrete particle swarm algorithm model that introduces a market auction mechanism, designs a two-matrix coding method for task allocation with timing, and dynamically divides subpopulations based on particle quality and a change of the topology. An efficiency function model based on the principle of maximum efficiency of matrix full arrangement is proposed, and a market auction mechanism is introduced in the iterative process to construct high-quality particles. By constructing two kinds of sudden situations: UAV failure and new emergency tasks, based on the task pre-allocation scheme, the algorithm can complete the mining of better solutions in a shorter time, and the algorithm model’s effectiveness is verified to solve the problem of dynamic task allocation.

This paper introduces a local dynamic assignment strategy. In the future, we can optimize task allocation in a rolling manner according to the dynamic changes of the battlefield environment. Additionally, the UAV dynamic task decision process can be further studied.

Author Contributions

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

Funding

This work was supported in part by the Equipment Pre-Research Foundation of China under Grant 61403120205 and Natural Science Basic Research Program of Shaanxi (Program No.2022JQ-593). Gratitude goes to all the staff at the Foundation.

Data Availability Statement

No new data were created or analyzed in this study. Data sharing is not applicable to this article.

Acknowledgments

Thank you to my partners for their trust and collaboration, facilitating our work’s completion.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures and Tables

Figure 1. UAV flight path when meeting threat situation.

Figure 2. The structure of the A-QCDPSO algorithm.

Figure 3. Particle encoding. (a) Task allocation matrix. (b) Task sequence matrix.

Figure 4. Schematic diagram of matrix arrangement.

Figure 5. The flow process of the A-QCDPSO algorithm.

Figure 6. The change curve of fitness before and after UAV sudden failure.

Figure 7. Task allocation results after UAV failure.

Figure 8. The change curve of fitness before and after new emergency tasks.

Figure 9. Task allocation results after new emergency tasks.

Figure 10. Time comparison of three algorithms to obtain an optimal solution.

Table 1

Air-to-ground task parameters.

Task Number	Position	Value	Type
1	(55,50)	20	Detection
2	(60,70)	20	Detection
3	(65,30)	40	Attack
4	(75,20)	100	Detection
5	(80,50)	40	Attack
6	(78,70)	50	Detection
7	(75,90)	30	Attack
8	(95,40)	80	Detection
9	(50,90)	70	Attack
10	(125,60)	90	Attack
11	(95,80)	75	Detection
12	(90,110)	100	Detection

Table 2

UAV parameters.

UAVNumber	Position	Value	Max Range	Number of Weapons	Position
1	(20,90)	50	500	0	Detection
2	(30,70)	100	400	2	Attack
3	(20,40)	90	400	2	Detection and Attack
4	(35,25)	80	550	0	Detection
5	(120,100)	67	450	2	Detection and Attack
6	(35,35)	98	600	0	Detection
7	(45,105)	45	390	2	Attack
8	(110,25)	87	480	0	Detection

Table 3

UAV detection capability information.

	UAV	1	3	4	5	6	8
Task
1		0.4	0.3	0.3	0.4	0.5	0.3
2		0.5	0.6	0.35	0.35	0.45	0.55
4		0.5	0.4	0.55	0.55	0.75	0.45
6		0.8	0.5	0.65	0.35	0.25	0.85
8		0.43	0.65	0.5	0.65	0.43	0.13
11		0.2	0.6	0.6	0.73	0.2	0.2
12		0.6	0.4	0.4	0.5	0.6	0.4

Table 4

UAV damage capability information.

	UAV	2	3	5	7
Task
3		0.3	0.5	0.6	0.5
5		0.6	0.93	0.7	0.4
7		0.2	0.3	0.5	0.3
9		0.64	0.5	0.64	0.7
10		0.45	0.3	0.45	0.7

Table 5

UAV stealth capability information.

	UAV	1	2	3	4	5	6	7	8
Task
1		0.5	0.3	0.4	0.3	0.4	0.5	0.4	0.3
2		0.45	0.35	0.35	0.35	0.65	0.45	0.75	0.55
3		0.8	0.2	0.6	0.2	0.6	0.8	0.5	0.4
4		0.75	0.35	0.55	0.35	0.55	0.75	0.55	0.45
5		0.3	0.4	0.2	0.4	0.2	0.3	0.4	0.7
6		0.25	0.65	0.35	0.65	0.35	0.25	0.45	0.85
7		0.2	0.8	0.5	0.8	0.5	0.2	0.3	0.4
8		0.43	0.5	0.65	0.5	0.65	0.43	0.23	0.13
9		0.6	0.3	0.64	0.3	0.64	0.6	0.7	0.3
10		0.5	0.6	0.45	0.6	0.45	0.5	0.7	0.4
11		0.2	0.6	0.73	0.6	0.73	0.2	0.3	0.2
12		0.6	0.4	0.5	0.4	0.5	0.6	0.4	0.4

Table 6

Threat information.

Threat Number	Position	Radius
1	(40,50)	4
2	(70,43)	7
3	(60,80)	5

Table 7

Task pre-allocation scheme.

UAV Number	Task Sequence	Effectiveness
$U_1$	$T_6\to T_{12}$	3.335
$U_3$	$T_3\to T_1\to T_2$
$U_4$	$T_4$
$U_5$	$T_{10}\to T_8\to T_5$
$U_7$	$T_9\to T_7$
$U_8$	$T_{11}$

Table 8

New task parameters.

Task Number	Position	Tactical Value	Type
13	(35,95)	60	Attack
14	(110,65)	40	Detection
15	(45,70)	80	Detection

Table 9

UAV stealth capability information.

	UAV	1	2	3	4	5	6	7	8
Task
13		0.5	0.4	0.6	0.6	0.8	0.45	0.8	0.86
14		0.6	0.3	0.6	0.2	0.5	0.55	0.8	0.5
15		0.3	0.4	0.4	0.5	0.5	0.95	0.6	0.33

Table 10

UAV detection capability information.

	UAV	1	2	3	4	5	6	7	8
Task
14		0.6	0.85	0.4	0.8	0.55	0.9	0.8	0.86
15		0.8	0.6	0.6	0.75	0.45	0.7	0.8	0.5

Table 11

UAV damage capability information.

	UAV	1	2	3	4	5	6	7	8
Task
13		0.6	0.75	0.45	0.9	0.55	0.9	0.8	0.86

Table 12

Task allocation scheme after UAV failure.

UAV Number	Task Sequence	Effectiveness
$U_2$	$T_3$	2.8765
$U_3$	$T_6\to T_5\to T_8\to T_{10}$
$U_4$	$T_4$
$U_6$	$T_1\to T_2$
$U_7$	$T_9\to T_7$
$U_8$	$T_{11}\to T_{12}$

Table 13

Task allocation scheme new emergency tasks.

UAV Number	Task Sequence	Effectiveness
$U_1$	$T_{15}\to T_{12}$	3.6952
$U_3$	$T_3\to T_6\to T_{11}\to T_7$
$U_4$	$T_4$
$U_5$	$T_{10}\to T_8\to T_5$
$U_6$	$T_1\to T_2$
$U_7$	$T_{13}\to T_9$
$U_8$	$T_{14}$

Table 14

Comparison of the average time of three algorithms to obtain the optimal solution.

Algorithms	UAV Sudden Failures (s)	New Emergency Tasks (s)
A-QCDPSO	1.985	2.298
QCDPSO	4.067	4.547
Contract network	2.504	2.872

References

1. Alsamhi, S.H.; Almalki, F.A.; Ma, O.; Ansari, M.S.; Angelides, M.C. Correction to: Performance optimization of tethered balloon technology for public safety and emergency communications. Telecommun. Syst.; 2019; 72, 155.

2. Saif, A.; Dimyati, K.; Noordin, K.A.; Alsamhi, S.H.; Hawbani, A. Multi-UAV and SAR collaboration model for disaster management in B5G networks. Internet Technol. Lett.; 2021; e310. [DOI: https://dx.doi.org/10.1002/itl2.310]

3. Saif, A.; Dimyati, K.; Noordin, K.A.; MohdShah, N.S.; Abdullah, Q. Energy-Efficient Tethered UAV Deployment in B5G for Smart Environments and Disaster Recovery. Proceedings of the 2021 1st International Conference on Emerging Smart Technologies and Applications (eSmarTA); Sana’a, Yemen, 10–12 August 2021.

4. Saif, A.; Dimyati, K.B.; Noordin, K.; Shal, N.S.M.; Alsamhi, S.H.; Abdullah, Q.; Farah, N. Distributed Clustering for User Devices Under Unmanned Aerial Vehicle Coverage Area during Disaster Recovery. Proceedings of the 2021 IEEE International Conference in Power Engineering Application (ICPEA); Shah Alam, Malaysia, 8–9 March 2021.

5. Alsamhi, S.H.; Almalki, F.A.; Al-Dois, H.; Othman, S.B.; Saleh, H. Machine Learning for Smart Environments in B5G Networks: Connectivity and QoS. Comput. Intell. Neurosci.; 2021; 11, 6805151. [DOI: https://dx.doi.org/10.1155/2021/6805151]

6. Almalki, F.A.; Alsamhi, S.; Sahal, R.; Hassan, J.; Breslin, J. Green IoT for Eco-Friendly and Sustainable Smart Cities: Future Directions and Opportunities. Mob. Netw. Appl.; 2021; pp. 1-25. [DOI: https://dx.doi.org/10.1007/s11036-021-01790-w]

7. Budaev, D.; Amelin, K.; Voschuk, G.; Skobelev, P.; Amelina, N. Real-time task scheduling for multi-agent control system of UAV’s group based on network-centric technology. Proceedings of the International Conference on Control, Decision and Information Technologies (CoDIT); Saint Julian’s, Malta, 6–8 April 2016.

8. Wu, W.; Cui, N.; Shan, W.; Wang, X. Distributed task allocation for multiple heterogeneous UAVs based on consensus algorithm and online cooperative strategy. Aircr. Eng. Aerosp. Technol.; 2018; 90, pp. 1464-1473.

9. Miao, Y.; Zhong, L.; Yin, Y.; Zou, C.; Luo, Z. Research on dynamic task allocation for multiple unmanned aerial vehicles. Trans. Inst. Meas. Control; 2017; 39, pp. 466-474.

10. Yang, M.; Bi, W.; Zhang, A.; Gao, F. A distributed task reassignment method in dynamic environment for multi-UAV system. Appl. Intell.; 2022; 52, pp. 1582-1601.

11. Jia, T.; Xu, H.; Yan, H.; Du, J. Decentralized Multi-agent Task Planning for Heterogeneous UAV Swarm. Trans. Nanjing Univ. Aeronaut. Astronaut.; 2020; 37, pp. 528-538.

12. Wu, H.; Li, H.; Xiao, R.; Liu, J. Modeling and simulation of dynamic ant colony’s labor division for task allocation of UAV swarm. Phys. A Stat. Mech. Its Appl.; 2018; 491, pp. 127-144.

13. Zaza, T.; Richards, A. Ant Colony Optimization for routing and tasking problems for teams of UAVs. Proceedings of the 2014 UKACC International Conference on Control (CONTROL); Loughborough, UK, 9–11 July 2014.

14. Yavuz, H.S.; GöKtas, H.; Çevıkalp, H.; Sarıbaş, H. Optimal Task Allocation for Multiple UAVs. Proceedings of the 2020 28th Signal Processing and Communications Applications Conference (SIU); Gaziantep, Turkey, 5–7 October 2020.

15. Chen, X.; Liu, Y. Cooperative task assignment and track planning for multi-UAV attack mobile targets. Fire Control Command Control; 2020; 45, pp. 35-46.

16. Ma, Y.; Zhang, H.; Zhang, Y.; Gao, R.; Yang, J. Coordinated Optimization Algorithm Combining GA with Cluster for Multi-UAVs to Multi-tasks Task Allocation and Path Planning. Proceedings of the 2019 IEEE 15th International Conference on Control and Automation (ICCA); Edinburgh, UK, 16–19 July 2019.

17. Wu, X.; Yin, Y.; Xu, L.; Wu, X.; Meng, F.; Zhen, R. MULTI-UAV Task Allocation Based on Improved Genetic Algorithm. IEEE Access; 2021; 9, pp. 100369-100379.

18. Han, S.; Fan, C.; Li, X.; Luo, X.; Liu, Z. A modified genetic algorithm for task assignment of heterogeneous unmanned aerial vehicle system. Meas. Control.; 2021; 54, pp. 994-1014.

19. Hafez, A.T.; Kamel, M.A. Cooperative task allocation and trajectory planning of unmanned systems via HFLC and PSO. Unmanned Syst.; 2019; 7, pp. 65-81.

20. Lin, L.; Qibo, S.; Shangguang, W.; Fangchun, Y. Research on PSO based multiple UAVs real-time task allocation. Proceedings of the 2013 25th Chinese Control and Decision Conference (CCDC); Guiyang, China, 25–27 May 2013.

21. Zhang, X.; Chen, X. Solving “limited” task allocation problem for UAVs based on optimization algorithms. Wirel. Commun. Mob. Comput.; 2021; 2021, pp. 1-14. [DOI: https://dx.doi.org/10.1155/2021/5530454]

22. Wang, J.; Jia, G.; Lin, J.; Hou, Z. Cooperative task allocation for heterogeneous multi-UAV using multi-objective optimization algorithm. J. Cent. South Univ.; 2020; 27, pp. 432-448.

23. Humphrey, L.; Cohen, K.; Rasmussen, S. Application of proper orthogonal decomposition and artificial neural networks to multiple UAV task allocation. Proceedings of the AIAA Guidance, Navigation, and Control Conference; Toronto, ON, Canada, 2–5 August 2010.

24. Lian, H.; Kang, F. Task allocation modeling for agent-oriented UUV collaborative system. J. Syst. Simul.; 2015; 09, pp. 155-162.

25. Zhang, K.; Zhao, X.; Li, Z.; Zhao, B.; Xiao, Z. Real-time reconnaissance task assignment of multi-UAV based on improved contract network. Proceedings of the 2020 International Conference on Artificial Intelligence and Computer Engineering (ICAICE); Beijing, China, 23–25 October 2020.

26. Chen, P.; Yan, F.; Liu, Z. Communication-constrained task allocation of heterogeneous UAVs. Acta Aeronaut. Et Astronaut. Sin.; 2021; 42, pp. 313-326.

27. Wang, L.; Guo, Q. Compression based distributed dynamic task allocation algorithms for heterogeneous multiple unmanned aerial vehicles. Proceedings of the 2017 IEEE International Conference on Robotics and Biomimetics (ROBIO); Macau, China, 5–8 December 2017; IEEE: Piscataway, NJ, USA, pp. 2401-2406.

28. Buckman, N.; Choi, H.L.; How, J.P. Partial Replanning for Decentralized Dynamic Task Allocation. Proceedings of the AIAA SciTech 2019 Forum; San Diego, CA, USA, 7–11 January 2019.

29. Cao, L.; Tan, H.; Peng, H.; Pan, M. Multiple UAVs hierarchical dynamic task allocation based on PSO-FSA and decentralized auction. Proceedings of the 2014 IEEE International Conference on Robotics and Biomimetics (ROBIO 2014); Bali, Indonesia, 5–10 December 2014.

30. Duan, H.; Li, P.; Yu, Y. A predator-prey particle swarm optimization approach to multiple UCAV air combat modeled by dynamic game theory. IEEE/CAA J. Autom. Sin.; 2015; 2, pp. 11-18.

31. Li, M.; Liu, W.; Zhang, Y. Multi-Agent dynamic task allocation based on improved contract net protocol. J. Shandong Univ.; 2016; 46, pp. 51-63.

32. Li, B.; Yan, H.; Wang, Z.; Liu, H. Algorithm of convex hull generation for point sets based on sorted coordinates. Sci. Surv. Mapp.; 2017; 42, pp. 14-17.

33. Wang, S.; Zhang, J.D.; Zhang, Z.; Yu, X. A Discrete Particle Swarm Optimization Algorithm for Solving TSP Problem under Dynamic Topology. Proceedings of the 2019 IEEE International Conference on Cybernetics and Intelligent (CIS), Robotics, Automation and Mechatronics (RAM); Bangkok, Thailand, 18–20 November 2019.

34. Bangla, A.K. Auction Algorithms for Generalized Nonlinear Network Flow Problems; Boston University: Boston, MA, USA, 2013.

35. Wan, L.; Yao, P.; Sun, P. Distributed task allocation method of manned/unmanned combat agents. J. Syst. Eng. Electron.; 2013; 35, pp. 310-316.

36. Fei, A.G.; Zhang, L.Y.; Liu, G.; Wang, Y. The Technique for Air-to-Air Missile Guidance Superiority Handover Based on Particle Swarm Auction Hybrid Algorithm. Electron. J. Astronaut.; 2013; 34, pp. 340-346.