Distributed Grouping Cooperative Dynamic Task Assignment Method of UAV Swarm

Abstract

Aiming at the problem of UAV swarms with distributed subsets performing cooperative reconnaissance-and-attack tasks on multi-targets in complex and uncertain combat scenarios, a distributed grouping cooperative dynamic task assignment method is proposed based on extended contract network protocol. The dynamic task assignment model for the UAV swarm with the topology of distributed subsets is established considering multiple constraints such as task cooperation, performing sequence, dynamic environment, communication topology, payload model, and UAV capability. According to the characteristics of multi-participants and multi-tasks in the process of UAV swarm executing tasks, the determination mechanism on cooperators and the selection mechanism of sequential tasks are proposed, and then the contract network protocol is extended. On the basis of the above, an event-triggered task assignment strategy for dynamic tasks is designed. The simulated results show that the proposed method can achieve the cooperative dynamic assignment of the UAV swarm to perform reconnaissance-and-attack tasks to multi-targets in complex and uncertain combat scenarios, improve the adaptiveness of the swarm under the sudden circumstance, and realize the optimization for task execution efficiency of the UAV swarm.

1. Introduction

The advances of intelligent autonomous systems have led UAV swarm technology and its application to the current scientific research hotspot [1,2]. Cooperative task assignment stands out as an essential component and a precondition of task accomplishment and autonomous control of UAV swarm systems [3].

Cooperative task assignment is to assign a considerable number of different types of subtasks and their order to each UAV in the swarm while meeting the task requirements with UAV capabilities and the multiple constraints involved. In the past few decades, there have been several main sorts of assignment algorithms for UAV swarm cooperative task assignment: the heuristic algorithm and the market-based algorithm, for example [4]. Heuristic algorithms generally search a certain range of solution space in an acceptable time by simulating natural phenomena to obtain feasible solutions to optimization problems. Common methods include the genetic algorithm [5,6,7,8], the particle swarm optimization algorithm [9], the ant colony algorithm [10,11], and the wolf swarm algorithm [12]. For UAV swarms with distributed architecture, heuristic algorithms always need to obtain global information. This process consumes lots of communication and computing resources as well as time to achieve global consensus; it is not suitable to apply heuristic algorithms. Compared with heuristic algorithms, market-based approaches (such as contract network protocol), distinctively characterized by distributed computing of swarms, requires only local information of the swarm and have the advantages of flexibility, robustness, and high operation speed [13] and, hence, are more suitable for distributed UAV swarms. Meanwhile, with strong scalability, market-based approaches can well handle cooperative task assignments with complex constraints such as limited communication [14] and time windows [15] and have been applied to dynamic task assignments [16,17,18]. The algorithms adopted are a part of the assignment approaches for the task assignment in complex and changeable combat scenarios, which are usually modeled as constraints or objectives from different perspectives.

The crucial topics to be investigated in this field include cooperative task assignment with the trajectory coupled [19,20] as well as under dynamic resistant circumstances [21,22,23]. In [24], a scheme to assign tasks in UAV swarms based on the contract network protocol (CNP) is presented, in which an A* algorithm is applied in flight path planning and path length estimation with a no-fly zone and threat considered. Under this scheme, the coupling between task assignment and flight path planning can be solved. However, their work does not take into consideration either pop-up missions or UAV faults. A study [25] has proposed a novel model for UAV coalition and an algorithm derived from basic geometry that generates a path derived from the original Dubins curve for application in remote sensing missions of fixed-wing UAVs. Another study [26] proposed an unmanned air vehicle (UAV) swarm task and a resource dynamic assignment algorithm based on the task sequence mechanism. By establishing a task sequence, each UAV strictly separates the necessary task time and synchronization waiting time. For the newfound targets, each UAV quickly determines its available time period. According to the available time and task resources, an auction algorithm and a consensus algorithm are used to decompose the task assignment into the initial distributed assignment phase and the swarm consensus phase to develop real-time conflict-free task solutions for UAV swarms. However, their work does not take into account the communication topology and time constraints. In [27], a CNP-based approach to a multi-UAV task assignment is proposed, in which a flight path planning method based on PH curves is combined with cooperative particle swarm optimization (PSO), cooperative variables, and cooperative functions to achieve attack synchronization on certain targets. Nevertheless, it does not take into account no-fly zones, threats, communication topology, and time constraints in addition to the task reassignment in the case of UAV faults. On the basis of this, [27,28] introduced local communication constraints with communication distance and information hop times to determine whether other UAVs participate in the local task assignment; however, it neglected the communication constraint caused by the swarm specific topology, which is crucial for certain command structures so as to improve operational effectiveness.

Compared with [21,22,23,24,25,26,27,28], the problem investigated in this paper is the dynamic task assignment for the heterogeneous UAV swarm consisting of distributed subsets with specific topology. In this paper, common constraints such as time windows, the UAV capability model, as well as new constraints such as topology constraints are combined to build the complex model of dynamic task assignment. The key contribution of this paper is that it proposes a solution to rectify the problem of heterogeneous UAV swarm cooperative dynamic task assignments with specific hierarchical communication topologies and other multiple constraints. An extended-CNP-based distributed assignment approach is proposed, along with distributed heterogeneous UAV swarm executing reconnaissance and attack tasks as the main scenario. The swarm consists of several subsets. On the swarm discovering new targets, it firstly assigns each target to subsets according to communication topology, and then each subset assigns subtasks to the UAVs within the group. The modified artificial potential field method is adopted to preplan the threat avoidance flight path, and battlefield survivability and fuel consumption are introduced to describe the flight path’s impact on the task assignment. Correspondingly, the consumption penalty and threat penalty functions can be designed so as to solve the coupling between task assignment and path planning. Meanwhile, constraints on time and cooperation are introduced to adjust the task executing sequence.

The rest of paper is organized as follows. The description of distributed grouping UAV swarm task assignment problem with multiple constraints is presented in Section 2. In Section 3, combined with hierarchical communication topologies of the UAV swarm, the distributed assignment algorithm based on extended contract network protocol is thoroughly addressed. In Section 4, the dynamic cooperative task assignment scheme based on an event-trigger strategy is proposed. Section 5 demonstrates the approach’s effectiveness, both in uncertain environments and with UAV failure, by numerical examples, and the whole work is concluded in Section 6.

2. Problem Description

2.1. Mission Scenario Analysis

There are heterogeneous UAV swarms consisting of distributed subsets in the mission area. Each subset is composed of several reconnaissance UAVs, attack UAVs, and reconnaissance-attack UAVs. The procedure of task assignment includes target allocation and subtask assignment. The swarm accomplishes the initial assignment, and then the UAVs cooperatively perform tasks. If a UAV discovers a new target, it relays the target information to others within a limited range according to hierarchical communication topologies, which triggers dynamic task assignment and then updates each UAV’s task sequence.

2.2. Hierarchical Communication Topology

The UAV swarm is divided into several distributed subsets. Communication exists within each subset and among subsets, hence hierarchical communication topology is established. In the application process, the swarm can cooperate to assign and complete tasks through the two-layer mechanism of inter-group cooperation and intra-group coordination based on hierarchical communication topology. The structure of the distributed subsets adopted integrates the advantages of both centralized structure and fully distributed structure to realize “global centralization and local autonomy”, which avoids the problems of low redundancy and the heavy central load of the fully centralized structure as well as the disadvantages of high individual capability requirements, communication complexity, and the command conflicts of the fully distributed structure. The structure conforms to the actual combat scenario as well as the development status of UAV swarm technology and will become more normalized and practical [29,30,31,32].

The algebraic graph theory is used to describe the internal interaction of the UAV swarm system. Assume that the UAV swarm has N UAVs, and each UAV is regarded as a node, then the communication relationship is seen as an edge. A directed graph G = {V, E, W} which consists of the node set V = {v₁,v₂,…,v_N}, the edge set $E\subseteq \{(v_i,v_j):v_i,v_j\in V,i\ne j\}$ and the adjacency matrix $\mathit{W}=[w^{ij}]\in {ℝ}^{N\times N}$, with non-negative entries $w^{ij}$. The entries in $\mathit{W}$ are defined with $w^{ij}=1$ for $(v_i,v_j)\in E$ and $w^{ij}=0$ otherwise. In addition, $w^{ii}=0$ for all $i=1,2,\cdots ,N$. The neighbor set of node $v_i$ is described as $N_i=\{v_j:(v_i,v_j)\in E\}$.

There is a top leader, N_m group leaders, and N_f followers in UAV swarms with distributed subsets, as shown in Figure 1. Each subset i has N_fi followers. The top leader is the highest leader node and leads the initial task assignment. The group leader, which obtains information of each UAV in the subset, is the leader node of the subset, participates in target allocation on behalf of the subset, and leads subtask assignment; the followers are members of the subset and participate in subtask assignment and execution.

Each node is numbered in the UAV swarm, in which the top leader index is 1, the indexes of group leaders are i = 2, …, N_m + 1, and the indices of followers are i = N_m + 2,…, N_m + N_f + 1. The adjacency matrix $W\in {ℝ}^{N\times N}$ has the following form:

$$W={\left[\begin{array}{ccc}0& W^{TM}& 0\\ W^{MT}& W^{M0}& W^{MF}\\ 0& W^{FM}& W^{F0}\end{array}\right]}_{N\times N}$$

(1)

where $W^{MT}\in {ℝ}^{N_m\times 1}$ and $W^{TM}\in {ℝ}^{1\times N_m}$ indicate the communication topology among the top leader and group leaders, $W^{M0}\in {ℝ}^{N_m\times N_m}$ expresses the communication topology among group leaders, the communication topology among group leaders, and their followers are denoted as $W^{M0}\in {ℝ}^{N_m\times N_m}$, while $W^{F0}\in {ℝ}^{N_f\times N_f}$ is denoted as the communication topology among followers. Assuming that no direct communication exists between each follower and the top leader, the followers of each subset only communicate within UAVs in the subset:

$$\begin{array}{c}{\mathit{W}}^{FM}=diag\left\{{\mathit{W}}^{F{M}_1},{\mathit{W}}^{F{M}_2},\dots ,{\mathit{W}}^{F{M}_{N_m}}\right\}\\ {\mathit{W}}^{MF}=diag\left\{{\mathit{W}}^{M{F}_1},{\mathit{W}}^{M{F}_2},\dots ,{\mathit{W}}^{M{F}_{N_m}}\right\}\\ {\mathit{W}}^{F0}=diag\left\{{\mathit{W}}^{F_1},{\mathit{W}}^{F_2},\dots ,{\mathit{W}}^{F_{N_m}}\right\}\end{array}$$

(2)

where $W^{F{M}_i}\in {ℝ}^{N_{fi}\times 1}$ and $W^{M{F}_i}\in {ℝ}^{1\times N_{fi}}$ express the communication topology among group leader and its followers in subset i, and $W^{F_i}\in {ℝ}^{N_{fi}\times N_{fi}}$ is the topology among followers in subset i.

2.3. UAV and Payload Model

Denote UAV set V = {V_i| i = 1, 2, …, N}, in which any UAV V_i can be described as a seven-element combination $<X_i,h_i,C_i,P_i,F_i,D_{i,max},N_{vi,max}>$. $X_i=(x_i,y_i,z_i,v_i,{\phi }_i,{\psi }_i)$ represents the kinetic parameters of UAV V_i, including position, velocity, flight path angle, and flight heading angle; $h_i\in [0,1]$ represents the survivability of UAV V_i, and $h_i=0$ indicates V_i is destroyed or has encountered faults and then completely loses its mission capability; C_i = {C_i1, C_i2, …, C_inCi} expresses indices of UAVs that communicate with V_i; $P_i=\{P_{i,scout},P_{i,attack}\}$ is the executable task type of V_i, where $P_{i,scout}\in \{0,1\}$, and $P_{i,attack}\in \{0,1\}$ means reconnaissance capability and attack capability, respectively. When the capability is available, the value is 1, otherwise 0; $F_i$ is the fuel consumption rate per unit air-range of V_i; $D_{i,\max }$ is the maximum air-range; $N_{vi,max}$ is the maximum number of executable tasks of V_i.

The condition that a reconnaissance UAV discovers and confirms the threat or target is that it is located in the detection area of the reconnaissance payload, as shown in Figure 2a. Reference [33] gives the typical mathematic model of the detection area. The condition that an attack UAV can strike a target is that the target is located in the available area of the attack payload, as shown in Figure 2b. References [33,34] give the typical mathematic model of the available area.

2.4. Threat Model

Any threat can be described by a five-element combination $<q_{o,i},R_{o,i},R_{a,i},p_{o,i},F_{o,i}>$, where $q_{o,i}$ is the position vector of the threat $O_i$ center, $R_{o.i}$ is the no-fly zone radius of threat $O_i$, and $R_{a.i}$ is the impact radius of threat $O_i$. When a UAV flies into the no-fly zone, it will be destroyed; when the UAV enters the impact area, it will be affected by the threat. $p_{o,i}\in [0,1]$ expresses the estimation of threat impact. $F_{o,i}\in \{0,1\}$ indicates the detected status flag of the target, where the value 0 means the target is undetected; otherwise, the value is 1.

The estimation $p_{o,i}(q)$ of the threat $O_i$ impact on any point in space is denoted as

$$p_{o,i}(q)=\{\begin{array}{l}1,0<\Vert q-q_{o,i}\Vert <R_{o,i}\hfill \\ A_i(q,q_{o,i}),R_{o,i}\le \Vert q-q_{o,i}\Vert \le R_{a,i}\hfill \\ 0,\Vert q-q_{o,i}\Vert >R_{a,i}\hfill \end{array}$$

(3)

where $A_i(q,q_{o,i})\in (0,1)$, which is a function of the distance between the point and the threat center, represents the effect evaluation within the threat range; for the convenience of the study, $A_i(q,q_{o,i})$ can be taken as a constant value. When the UAV approaches threat $O_i$ and enters the impact range, its survivability will decrease. We assume the survivability of UAV V_j is $h_j$ and the survivability becomes ${h^{\prime }}_j$ under the impact of threat $O_i$, of which the process can be expressed as

$${h^{\prime }}_j=h_j\cdot (1-A_i)$$

(4)

2.5. Dynamic Task Allocation Problem

We adopt a seven-element combination {V, Sg, T, O, M_t, R, C} to describe the dynamic task assignment problem. V = {V₁, V₂, …, V_N} is the set of UAVs and N represents the number of UAVs in the swarm; S_g = {S_g1, S_g2, …, S_gNG} is the set of subsets and $N_G$ represents the number of UAV subsets in the swarm; T = {T₁, T₂, …, T_NT} is the set of targets, where $N_T$ is the number of targets; O = {O₁, O₂, …, O_Nobs} is the set of obstacles, where N_obs is the number of obstacles; M_t = {M_t1, M_t2, …, M_t,Ntype} is the task type set of each target, where $N_{type}$ is the number of the types. For the “Reconnaissance-Attack” mission scenario, the task type set includes the reconnaissance and attack of two elements, which can be expressed as $M_t=\{Scout,Attack\}$; R = {R₁, R₂, …, R_Ntype} is the set of the maximum task values for the “Reconnaissance-Attack” mission scenario $R=\{R_S,R_A\}$; $C$ is the set of multiple constraints, mainly including UAV capacity constraint, time window constraint, sequential constraint, and cooperation constraint. These constraints are described as follows:

Definition 1 (UAV capability constraints).

The UAV capability constraints are mainly reflected in three aspects: the maximum range, the executable task types, and the maximum number of executable tasks.

(a) (The maximum range constraint) Assume that the initial state of UAV V_i is $s_{i0}$, and the task sequence is Seq_i = {s_i1, s_i2, …, s_i,Ns,i}, where $N_{s,i}$ is the number of tasks to be executed. From Section 2.3, the maximum range of UAV V_i is $D_{i,max}$ and the maximum range constraint can be expressed as

$${\displaystyle \sum _{j=1}^{N_{s,i}}L(s_{ij},s_{i,j-1})\le }{D}_{i,max}$$

(5)

where $L(s_{ij},s_{i,j-1})$, which relates to task $s_{i,j-1}$ and task $s_{ij}$, represents the air-range from the position of task $s_{i,j-1}$ to the position of task $s_{ij}$. That means the whole air-range couples with the task sequence.

(b) (The executable task type constraint) In the process of the swarm cooperative task execution, different sorts of UAVs perform different types of tasks. There is a mapping between the UAV capability $P_i=\{P_{i,scout},P_{i,attack}\}$ and $M_t=\{Scout,Attack\}$, which can be expressed as

$$P_i=\{P_{i,scout},P_{i,attack}\}=\{\begin{array}{l}\{1,\ast \}\to Scout\hfill \\ \{\ast ,1\}\to Attack\hfill \end{array}$$

(6)

(c) (The task number constraint) The payload number and energy carried by UAVs have limits; thus, it is necessary to restrict the maximum number of tasks performed by the UAV. Assuming that the number of tasks assigned to UAV $V_i$ is $N_{vt,i}$ and the upper limit is $N_{vi,\max }$, the constraint is expressed as

$$N_{vt,i}\le N_{vi,\max }$$

(7)

Definition 2 (Sequence constraint).

If there is a specific execution order between subtasks$Tas{k}_i$and$Tas{k}_j$, there is sequence constraint between$Tas{k}_i$ and$Tas{k}_j$. Reference [9] gives the concrete model of sequence constraint.

Definition 3 (Time window constraint).

The start time when task$s_{i,j}$inSeq_i= {s_i1, s_i2, …, s_i,Ns,i} is performed by UAV$V_i$needs to be guaranteed to be in the time window$t_{si,j}\in [t_{b,j},t_{e,j}]$, where$t_{b,j}$is the earliest start time and$t_{e,j}$is the latest one. The start time$t_{si,j}$has relations with the last task and the preplanned flight path of the UAV. Suppose$t_{e,j-1}$the time when UAV accomplishes the last task and the preplanning air-range from$s_{i,j-1}$to$s_{i,j}$, then the time window constraint can be expressed as

$$\{\begin{array}{l}{t}_{si,j}\le t_{e,i}\hfill \\ t_{si,j}=\max \left\{t_{b,i},t_{e,j-1}+\frac{L_i}{V}\right\}\hfill \end{array}$$

(8)

Definition 4 (Cooperation constraint).

For the process of several UAVs cooperatively performing reconnaissance or attack task$Tas{k}_j$, the expected number of participants$N_{pe,j}$is introduced, which means that$Tas{k}_j$can be accomplished by$N_{pe,j}$UAVs at most. The actual number of participants is$N_{p,j}$and has

$$0\le N_{p,j}\le N_{pe,j}$$

(9)

Definition 5 (The dynamic task allocation problem).

The objective is to find the best assignment. To be more concise is to optimize the swarm’s reward B_s during the task execution, such that:

$$\begin{array}{ll}{\widehat{B}}_s& =\max B_s(V,S_g,T,O,M_t,R)\\ & =max{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{j=1}^{N_{s,i}}{B}_{ij}(h_{i,est},L_{ij},t_{tas{k}_j})}}\end{array}$$

subject to the constraints:

$$\{\begin{array}{l}{\displaystyle \sum _{j=1}^{N_{s,i}}L(s_{ij},s_{i,j-1})\le }{D}_{i,max}\hfill \\ P_i=\{P_{i,scout},P_{i,attack}\}=\{\begin{array}{l}\{1,\ast \}\to Scout\hfill \\ \{\ast ,1\}\to Attack\hfill \end{array}\hfill \\ N_{vt,i}\le N_{vi,\max }\hfill \\ t_{si,j}\le t_{e,i}\hfill \\ t_{si,j}=\max \left\{t_{b,i},t_{e,j-1}+\frac{L_i}{V}\right\}\hfill \\ 0\le N_{p,j}\le N_{pe,j}\hfill \end{array},\forall i\in V$$

where the value of $B_{ij}$ indicates the reward of UAV i performing the task j; the survivability estimation is $h_{i,est}$, which means more loss to the UAV performing the task; the air-range performing $Tas{k}_j$ is $L_{ij}$; the start time of task j is $t_{tas{k}_j}$.

Due to the objective function coupling with the process of contract net protocol, the detailed expression is designed in Section 3.2, where the bidding function of the market mechanism is introduced.

3. Task Assignment Algorithm Based on Extended CNP

This section designs a distributed dynamic task assignment algorithm based on extended contract network protocol. The core of contract net protocol (CNP) is to simulate the “bid–win” market mechanism and realize the optimization of task assignment based on the interaction of individuals. The classical CNP is not suitable for sequential task assignments with multiple constraints under multiple rounds, which means that it needs extending according to complex task constraints.

3.1. Distributed Multi-Constraint Dynamic Task Assignment Algorithm

The algorithm includes four steps: target information release, bidding scheme generation, bid winning authorization, and task execution. The process is shown in Figure 3. The following describes the algorithm process in turn.

Step 1: Release the information of targets

Assume that the UAV detects a sudden target $T_k$ and reports the target information to the subset leader UAV $V_i$, which becomes the tendering UAV on behalf of the subset, and sends a bidding invitation to each subset in the local communication network.

According to the hierarchical communication topology, the set of other subset leaders interacting with $V_i$ is $V_{p,i}=\left\{V_j\right|w_{ij}=w_{ji}=1,j\in [2,1+N_m]\cup j\ne i\}$. $V_{p,i}$ composes the potential bidders of assignment for target $T_k$. Tendering UAV $V_i$ releases tendering information $I_i$ to each UAV in set $V_{p,i}$, and $I_i$ is expressed as

$$I_i=(V_i,T_k,\{Tas{k}_k\},t_{now},H_b)$$

(10)

where $V_i$ is the index of tendering UAV; $T_k$ is the index of the sudden target; $\left\{Tas{k}_k\right\}$ is denoted as the subtask set of target $T_k$; $t_{now}$ is the releasing time; $H_b$ is the information state flag, of which value 0 means no relay, otherwise 1. The information structure of $Tas{k}_k$ can be denoted as:

$$Tas{k}_k=\{M_{t,k},q_{t,k},TimeBa{r}_k,R_{x,k},N_{pe,j},T{h}_k\}$$

(11)

where $M_{t,k}$ means task type; $q_{t,k}$ is the position coordinates; $TimeBa{r}_k=[t_{b,k},t_{e,k}]$ is the time window; $R_{x,k}$ is the maximum task value; $N_{pe,j}$ is the expected number of participants; $T{h}_k$ is the negotiation threshold.

As attached information during the subtask $Tas{k}_k$ assignment process, negotiation threshold $T{h}_k$ is applied to preselect bidders from the potential bidder set $\left\{V_{p,i}\right\}$, reducing the negotiation scale as well as the consumption of communication resources and improving assignment efficiency. To adjust the threshold adaptively, the reward of subtask $Tas{k}_k$ in performing the subset to which UAV $V_i$ belongs is selected as $T{h}_k$. If the bidder’s bidding value is greater than $T{h}_k$, it indicates that the swarm efficiency will be optimized and improved after $Tas{k}_k$ is assigned to the bidder.

In the process of information release, different UAV groups with intersections of local communication topologies may discover the same target, causing multiple bidding UAVs to release information at the same time in their respective local communication topologies, resulting in system conflict and resource waste. In order to avoid this problem, it is necessary to ensure that different UAV subsets reach a consensus on tendering UAVs and tendering information, which is realized by Algorithm 1.

Algorithm 1: Release tendering information and achieve information consensus.
1:	$\mathrm{if}{I}_i$ is not empty
2:	$\mathrm{if}{I}_i.H_b=0$
3:	$\mathrm{broadcast}{I}_i$$\mathrm{to}\left\{V_{p,i}\right\}$
4:	endif
5:	endif
6:	$\mathrm{for}j=1$ $\mathrm{to}\mathrm{number}\mathrm{of}\mathrm{tendering}Tas{k}_k$ invitation received
7:	$\mathrm{if}{I}_i.Tas{k}_k.T{h}_k$ < $I_j.Tas{k}_k.T{h}_k$
8:	$I_i=I_j$
9:	$\mathrm{broadcast}\mathrm{StopCmd}\mathrm{to}\left\{V_{p,i}\right\}-\left\{V_{p,j}\right\}$
10:	endif
11:	endfor

In Algorithm 1, “StopCmd” means to abort the negotiation command, and the operation “.” represents the reference to elements in the information structure. For any UAV $V_i$ in the local communication topology, the tendering information related to subtask $Tas{k}_k$ will be released to its directly connected UAV if it is not empty and has not been transmitted (Line 1–4). Meanwhile, the UAV can also receive the tendering information related to $Tas{k}_k$ transmitted by others directly connected with it (Line 6–11).

If UAV $V_i$ finds that the negotiation threshold of UAV $V_j$ about $Tas{k}_k$ is greater, $V_i$ saves the tendering information $I_j$ and issues commands to other UAV groups interacted with $V_i$ but not interacted with $V_j$ to stop the negotiation so as to make them exit the assignment dominated by UAV $V_j$.

After Step 1, the tendering information released in the local communication network achieves consensus, that is $I_i=I_j$.

Step 2: Generate bidding scheme

On the basis of the target information and various constraints, each potential bidder first determines the bidding scheme for the target of the group, including whether the subset participates in the bidding for target $T_k$, subtasks that can be performed and the corresponding UAVs, and the reward for performing each subtask, and so forth.

Through the contract network in subsets, each subtask of target $T_k$ is preassigned to form the bidding scheme for target $T_k$. The specific process is as follows:

① A subset leader UAV $V_j$ releases subtask information to each follower UAV. In order to improve the assignment efficiency and shorten the time, the task concurrency mechanism is introduced to publish the information of each subtask at the same time;

② For subtask $Tas{k}_k$, the follower UAV $V_m$ judges whether it has the corresponding type of payload, whether the number of payloads can meet the task execution requirements, and whether it meets the time window $TimeBa{r}_k$ according to the subtask information. If any constraint is not satisfied, UAV $V_m$ will not bid for subtask $Tas{k}_k$;

③ If the above constraints are met, UAV $V_m$ preplans the flight path of $Tas{k}_k$ based on the modified artificial potential field (MAP) method and substitutes the preplanned range $L_{mk}$ and survivability estimation $h_{m,est}$ into the individual bidding function to calculate the bidding value $B_{mk}$;

④ Compare the bidding value $B_{mk}$ with the subtask negotiation threshold $T{h}_k$. If $B_{mk}<T{h}_k$, it means that the system efficiency has not been improved when UAV $V_m$ is used to perform subtask $Tas{k}_k$, and $V_m$ actively abandons pre-assignment bidding for $Tas{k}_k$; otherwise, $V_m$ participates in the bidding;

⑤ Each follower UAV respectively performs steps ②–④ to complete the pre-assignment of each subtask. The subset leader UAV $V_j$ generates the subset’s bidding scheme for target $T_k$ according to the pre-assignment results.

The above is the basic process of bidding scheme generation. Due to the existence of multi-UAV cooperatively performing subtasks and the introduction of the task concurrency mechanism, the generation of the bidding scheme needs to solve a “multi-participants–multi-tasks” assignment optimization subproblem.

In order to solve the subproblem, an assignment mechanism based on the contract network within subsets is constructed. For the subtasks that need to be executed by multiple UAVs, a cooperator determination mechanism is introduced to complete the task allocation; for the sequential subtasks with time windows, a sequential task selection mechanism is introduced. Details are as follows:

(1) The determination mechanism on cooperators

The process of the determination mechanism on cooperators is shown in Figure 4. To simplify the assignment process, give the tenderee the initiative, expand the set of bidders, and provide more feasible pre-assignment schemes, the tenderee bidding mechanism is introduced, that is, when the subtask tenderee (subset leader UAV $V_j$) meets conditions such as capability constraints and time constraints, it can participate in bidding.

If $V_j$ meets the constraints for performing $Tas{k}_k$ and decides to bid with the bidding value $B_{jk}$, then $Th$ is chosen as $B_{jk}$. UAV $V_j$ sends $Tas{k}_k$ information and negotiation threshold $B_{jk}$ to each follower UAV. The bidding value of follower UAV $V_m$ for $Tas{k}_k$ is $B_{mk}$. If $B_{mk}>B_{jk}$, $V_m$ decides to bid and feedback $B_{mk}$ to $V_j$. At the time, the set of all bidders participating in the $Tas{k}_k$ assignment is

$$V_{b,k}=\left\{V_m\right|w_{jm}=w_{mj}=1,j\ne m;B_{mk}>B_{jk}\}\cup \{V_j\}$$

If tenderee $V_j$ does not participate in the bidding, i.e., $B_{jk}=\varnothing$,

$$V_{b,k}=\left\{V_m\right|w_{jm}=w_{mj}=1,j\ne m;B_{mk}>0\}$$

To sum up, after preselection of negotiation threshold, all bidders participating in the assignment for $Tas{k}_k$ can be represented as

$$V_{b,k}=\{\begin{array}{l}\left\{V_m\right|w_{jm}=w_{mj}=1,j\ne m;B_{mk}>0\},B_{jk}=\varnothing \hfill \\ \left\{V_m\right|w_{jm}=w_{mj}=1,j\ne m;B_{mk}>B_{jk}\}\cup \{V_j\},B_{jk}\ne \varnothing \hfill \end{array}$$

(12)

Consider the cooperative constraints of subtask $Tas{k}_k$, assume $Tas{k}_k$ requires the participation of $N_{p,k}$ UAVs, and quickly sort the bidding value set $\left\{B_{jk}\right\}$. The greedy algorithm is used to select the $N_{p,k}$ largest bidding values in the set to form the winning bidding value set (reward set) $B_k$

$$B_k=\left\{B_{\left(1\right),k},B_{\left(2\right),k},\dots ,B_{\left(Np,k\right),k}\right\}$$

(13)

where $B_{(x),k}$ represents the $x$-th order element of $\left\{B_{mk}\right\}$ in descending order. The winner set $Winne{r}_k$ is correspondingly:

$$Winne{r}_k=Index(B_{\left(1\right),k},B_{\left(2\right),k},\dots ,B_{\left(Np,k\right),k})$$

(14)

(2) Sequential task selection mechanism

Take the sequential task assignment process of a single follower UAV as an example. After receiving the task information, the bidder determines the executable tasks according to the negotiation threshold, UAV capability constraints, and the execution sequence and combines them to generate an alternative sequence without a time window conflict. Based on the bid winning situation, the optimal sequence is selected as the final signing one. The operation process is shown in Figure 5.

Assume that the concurrent task set $Tas{k}^{new}=\left\{Tas{k}_1^{new},\dots ,Tas{k}_{Ntask}^{new}\right\}$ is received by the follower UAV $V_m$. The set of tasks that $V_m$ can execute and determine to participate in bidding is expressed as

$$Tas{k}^{a,m}=\left\{Tas{k}_k^{a,m}\right|k=1,2,\dots ,N_{a,m}\}\subseteq Tas{k}^{new}$$

(15)

where $N_{a,m}$ is the element number of $Tas{k}^{a,m}$. Denote $Com{b}_n(N_{a,m},N_{vm,n})$ as the combination which consists of random $N_{vm,n}$ elements from set {1, 2, …, N_a,m}, where $N_{vm,n}\le N_{a,m}$.

Definition 6 (Task Sequence Alternative).

If $\forall k\in Com{b}_n(N_{a,m},N_{vm,n})$,$\forall \overline{k}\in Com{b}_n(N_{a,m},N_{vm,n})-\left\{k\right\}$, there is$TimeBa{r}_k\cap TimeBa{r}_{\overline{k}}=\varnothing$. Then,$Com{b}_n(N_{a,m},N_{vm,n})$is called a sequence alternative.$TimeBa{r}_k$is the time window of subtask$Tas{k}_k^{a,m}$. The corresponding task sequence alternative is defined as

$$\begin{array}{c}\begin{array}{c}Se{q}_n^m=\left\{Tas{k}_k^{a,m}\right|k\in Com{b}_n(N_{a,m},N_{vm,n})\}\end{array},n\le N_{sm},Se{q}_n^m\subseteq Tas{k}^{a,m}\end{array}$$

(16)

where$N_{sj}$is the number oftask sequence alternatives.

After the bidding is completed, the set of losing bidding tasks is denoted by $Tas{k}^{de,m}$. After the sequences containing losing bidding tasks are eliminated, the set composed of the remaining sequence alternatives is

$$\begin{array}{c}SeqSe{t}_m=\left\{Se{q}_n^m\right|n\le N_{sm};\forall Tas{k}_k^{a,m}\in Se{q}_n^m,Tas{k}_k^{a,m}\notin Tas{k}^{de,m}\}\end{array}$$

(17)

Assuming that the bidding value of $V_m$ for any subtask $Tas{k}_k^{a,m}$ in $Se{q}_n^m$ is $B_{mk}$, where $Se{q}_n^m\in SeqSe{t}_m$, the sum of bidding value for each task in $Se{q}_n^m$ is

$$B_{m,n}={\displaystyle \sum _k{B}_{m,k}},k\in Com{b}_n(N_{a,m},N_{vm,n})$$

(18)

and the final signing sequence of follower UAV $V_m$ is

$$Se{q}^{win,m}=Se{q}_{n_{best}}^m,n_{best}=\underset{n}{\arg \max }(B_{m,n})$$

(19)

Through the above mechanism, the subtask pre-assignment scheme of the subset in which $V_j$ is located is generated, that is, the bidding scheme of the subset

$$BidSc{h}_j=\left\{Se{q}^{win,m}\right|m\in G_j\}$$

(20)

After that, UAV $V_j$ calculates the bidding function of the subset according to the bidding scheme and bids to the tenderee $V_i$.

Step 3: Determine the winners

After the bidding scheme generation and bidding application in Step 2, the tendering UAV $V_i$ selects the scheme of which the efficiency is greatest according to the bidding value of each group so as to determine which subset executes subtasks of target $T_k$.

The set of bidding values of subsets is $\left\{B_{g,jk}\right\}$. Apply the greedy algorithm and select the greatest value and corresponding subset as the winning value (reward) $B_{g,k}$ and the winner $Winne{r}_{g,k}$. The process can be expressed mathematically as

$$B_{g,k}=\max \{B_{g,jk},Winne{r}_{g,k}=\underset{j}{\mathrm{argmax}}(B_{g,jk})$$

(21)

After determining the winner, UAV $V_i$ authorizes the subset $Winne{r}_{g,k}$ to perform each subtask of target $T_k$.

Step 4: Perform the tasks

The winner subset formally authorizes each follower UAV in the subset to perform the subtasks, and the pre-assignment scheme in Step 2 becomes the formal assignment scheme. Follower UAV $V_m$ will add the signing subtask sequence $Se{q}^{win,m}$ to its task sequence to be executed, that is:

$$A_m=A_m\oplus Se{q}^{win,m}$$

(22)

where $A_m$ is the task sequence to be executed, $\oplus$ expresses the operation that it adds the sequence $Se{q}^{win,m}$ to the sequence $A_m$. Each UAV performs each task according to sequence $A_m$ and the preplanning flight path in the specific time window.

The pseudo-code of the whole algorithm 2 process described above is as follows:

Algorithm 2: The extended Contract Network Protocol.
Input:Task assignment combination {V, Sg, T, O, Mt, R, C}; Topology G0; time tnow Output: Task execution sequence set {Am}
1:	/* Step 1: Release the information of targets */
2:	for i from the first index of leader UAVs to the last one
3.	if Vi is a target tenderee UAV
4:	{Vp,i} = detTargetPotentialBidders(G0,C) /* determine the set of potential bidder subsets. */
5:	for k = 1 to number of targets
6:	if Tk is tendered by leader UAV i
7:	{Taskk} = generateSubtasks(Tk) /* Tenderee UAV i generates subtask information. */
8:	end if
9:	end for
10:	Ii = releaseTargetInfo ({Tk}, {Taskk}, tnow, {Vp,i}}  /* Tenderee UAV i releases target information. */
11:	end if
12:	end for
13:	/* Step 2: Generate bidding scheme */
14:	for j from the first index of leader UAVs to the last one
15:	for i from the first index of tenderee leader UAVs to the last one
16:	if Vj belongs to {Vp,i}
17:	Receive Ii and broadcast it to Vj ‘s followers
18:	end if
19:	end for
20:	for m from the first index of followers of Vj to the last one
21:	{Taska,m} = checkTaskConstaints({Ii.Taskk})   /* Select the executable subtasks from {Taskk} */
22:	{$Se{q}_n^m$} = combineTasks({Taska,m })   /* Generate the set of alternative sequence */
23:	{Bm,n} = biddingFuncCal({SeqSetm})   /* Calculate the bidding function of each sequence */
24:	Seqwin,m = $Se{q}_{n_{best}}^m$, nbest = $\underset{n}{\mathrm{argmax}}\left(B_{m,n}\right)$   /* Determine the sequence to execute */
25:	end for
26:	Bg,jk = ${\displaystyle \sum }_m\max \left(B_{m,n}\right)$
27:	end for
28:	/*  Step 3: Determine the winners */
29:	for i = 1 to number of tenderee leader UAV i
30:	for k = 1 to number of targets tendered by leader UAV i
31:	Bg,k = max{Bg,jk}, Winnerg,k = $\underset{j}{\mathrm{argmax}}\left(B_{g,jk}\right)$ /* Determine winner of tendering for Target k */
32:	end for
33:	end for
34:	/* Step 4: Perform the tasks */
35:	for n = 1 to number of subsets
36:	for m = 1 to number of follower UAV m of Subset n
37:	Am = Am $\oplus$ Seqwin,m  /* Add the signing subtask sequence to task execution sequence Am. */
38:	end for
39:	end for

Analyze the worst time complexity of the algorithm and take the case of task assignment by the top leader as an example:

The time complexity of the top leader issuing N_T targets with subtasks bidding information to N_G subset leaders is O(N_TN_G), the complexity of the initial evaluation of 4 types of constraints presented in Section 2.5 by N_G subset leaders is 4O(N_TN_G), the complexity of the bidding of potential bidder subsets {V_p,i} is O(K), where K is the number of elements in {V_p,i}; after K potential bidder subsets are determined, each potential bidder subset needs to pre-assign the subtasks and generate the bidding scheme of the subset.

Assume that each target has N_t subtasks, each subtask needs the most N_p participants and each subset consists of (N_f + 1) UAVs. Each subset will generate the target scheme based on the CNP within the subset. The time complexity of the subset leaders issuing N_t subtasks to their N_f followers is O(N_TN_tN_f). The sequential task selection is an arrangement–combination problem, of which the time complexity is N_T•O(N_t³), and the time complexity of bidding to the subset leader in each subset is O(N_TN_tN_f). Subset-leader-selecting cooperators can be regarded as a sorting problem, and the quick sort algorithm can be adopted so that the time complexity is N_TN_t•O(N_plog₂N_p). Therefore, the time complexity of the subtask pre-assignment is 2O(N_TN_tN_f) + N_T•O(N_t³) + N_TN_t•O(N_plog₂N_p).

After the bidding schemes of each subset are generated, the bidding winner subset will be determined. It is a quick sort process, so the time complexity is N_T•O(N_Glog₂N_G).

To conclude, the whole worst time complexity is 2O(N_TN_tN_f) + N_T•O(N_t³) + N_TN_t•O(N_plog₂N_p) + N_T•O(N_Glog₂N_G). It indicates that the algorithm is a polynomial one.

3.2. Bidding Function Design

As the core of extended CNP, the bidding function, which needs to be designed on the basis of the concrete task assignment problem in CNP, is a sort of objective function. According to the method process described above, the whole task assignment is divided into the target assignment and the subtask assignment. Both the target assignment and the subtask assignment are based on the extended CNP. Hence, the bidding function of each subset is designed for the target assignment, while the individual bidding function within the group is designed for the subtask assignment.

3.2.1. Individual Bidding Function

The individual bidding function B_ij consists of value function Re_ij and penalty function Pe_ij. Based on the analysis for the UAV swarm task assignment model in Section 2, the individual bidding function mainly relates to: ① the maximum task values, which is denoted in Section 2.5; ② the flight path; ③ the time windows and start time of each subtask.

Since the UAV task assignment couples with path planning, the bidding function needs to be designed in combination with the UAV flight path. By analyzing the scenario, it can be seen that the impact of the flight path on task assignment is mainly reflected in UAV survivability estimation $h_{i,est}$ and air-range $L_{ij}$ (fuel consumption), as shown in Figure 6.

Supposing that UAV $V_i$ participates in the bidding process of subtask $Tas{k}_j$ with time window $t_{tas{k}_j}\in [t_{s,j},t_{e,j}]$, where $t_{tas{k}_j}$ is the start time of task execution, of which the mathematical expression is given in Section 2.5, $t_{s,j}$ is the earliest start time, and $t_{e,j}$ is the latest one.

To evaluate the impact of threats {O_k | k = 1, 2, …, N_obs} on UAV $V_i$ performing tasks, it introduces the survivability estimation of $V_i$, which can be expressed as

$$h_{i,est}=h_i{\displaystyle \prod _{k=1}^{N_{app}}(1-A_{k,app})}$$

(23)

where $h_i$ is the current survivability of $V_i$, $A_{k,app}$ is the impact of threats $O_{k,app}\in \left\{O_k\right\}$ approached by $V_i$, $A_{k,app}\in (0,1)$, and $N_{app}$ is the number of threats approached.

(1) Value function Re_ij

In the actual scenario, the value of UAVs performing any task is generally related to the start time when the UAV performs the task. The nearer the start time $t_{tas{k}_j}$ to the time window $TimeBa{r}_k$, the greater the value for UAV $V_i$ to perform the task; otherwise, the smaller the value; hence, the item related to the start time $t_{tas{k}_j}$ is introduced. The value function of $V_i$ performing $Tas{k}_j$ is designed as

$${Re}_{ij}(h_{i,est},t_{tas{k}_j})=h_{i,est}\cdot R_{x,j}\cdot e^{-\lambda \frac{t_{tas{k}_j}-t_{s,j}}{t_{e,j}-t_{tas{k}_j}}}$$

(24)

where $R_{x,j}$ is the maximum value of $Tas{k}_j$; $\lambda$ is the attenuation factor of the start time $t_{tas{k}_j}$ on the task value. Apparently, ${Re}_{ij}$ is a monotonic increasing function of battlefield survivability $h_{i,est}$ and decreases monotonically with the start time $t_{tas{k}_j}$. When $h_{i,est}:1\to 0,t_{tas{k}_j}:t_{s,j}\to t_{e,j}$, there is ${Re}_{ij}:R_{x,j}\to 0$.

(2) Penalty function Pe_ij

The penalty function is composed of the consumption penalty and the threat penalty. Assuming that the per-unit fuel consumption of UAV $V_i$ is $F_i$, the air-range performing $Tas{k}_j$ is $L_{ij}$, the estimation of survivability is $h_{i,est}$, and the penalty function is designed as

$$P{e}_{ij}(h_{i,est},L_{ij})=\frac{1}{h_{i,est}}\cdot F_i{L}_{ij}$$

(25)

Obviously, ${Re}_{ij}$ is a monotonic function of battlefield survivability $h_{i,est}$. When $h_{i,est}:1\to 0^{+}$, there is $P{e}_{ij}:F_i{L}_{ij}\to +\infty$.

The penalty indicates the coupling impact of flight path planning on task assignment. On one hand, the fuel consumption of performing subtask $Tas{k}_j$ is directly related to the preplanned air-range $L_{ij}$; on the other hand, the more threats approached by UAV $V_i$ during the task execution, the lower the survivability estimation $h_{i,est}$, which means more loss when the UAV performs the task.

Combining the value function and the penalty function, the individual bidding function $B_{ij}$ of UAV $V_i$ for $Tas{k}_j$ is denoted by

$$B_{ij}(h_{i,est},L_{ij},t_{tas{k}_j})={Re}_{ij}-P{e}_{ij}=h_{i,est}\cdot R_{x,j}\cdot e^{-\lambda \frac{t_{tas{k}_j}-t_{s,j}}{t_{e,j}-t_{tas{k}_j}}}-\frac{1}{h_{i,est}}\cdot F_i{L}_{ij}$$

(26)

where a greater value of $B_{ij}$ indicates the reward of performing the task. $B_{ij}$ monotonically increases with $h_{i,est}$ and decreases with $L_{ij}$ and $t_{tas{k}_j}$, which agrees with the actual scenario, which suggests that $B_{ij}$ has practical significance.

3.2.2. Bidding Function of Each Subset

The bidding function of subsets is based on the individual function. For target $T_j$, supposing that the bidding value set is $\{B_1,B_2\}$ after the subtask assignment in subset $G_i$, $B_1,B_2$ respectively express the bidding value of subset $G_i$ performing the reconnaissance subtask and the attack one. The bidding function of subsets is defined as the sum of elements in $\{B_1,B_2\}$, which is

$$B_{g,ij}={\displaystyle \sum B_1}+{\displaystyle \sum B_2}$$

(27)

4. Dynamic Assignment Strategy Based on Event Triggering

4.1. Event Trigger Conditions for Dynamic Tasks

Due to the incomplete perception of the situation at the beginning and the occurrence of emergencies during the task execution, the initial assignment scheme needs to be adjusted. Therefore, the event trigger conditions are introduced to judge whether or not to carry out the dynamic task assignment. Event trigger conditions are the key to realizing dynamic task assignments, which need to be selected in combination with different scenarios. The dynamic task assignment process based on event triggering can be expressed as:

$$E:\mathrm{if}g(s(t),s_{t,j}(t))\ge 0,\mathrm{then}Targe{t}_j\leftarrow TargetInf{o}_j^{\ast },Tas{k}_{j,k}\leftarrow TaskInf{o}_{j,k}^{\ast }(k=1,2,\dots ,N_f)$$

where $g(s(t),s_{t,j}(t))\ge 0$ is the triggering condition, $s(t)$ is the state of UAV (such as the position), $s_{t,j}(t)$ is the status of target $T_j$. $Targe{t}_j\leftarrow TargetInf{o}_j^{\ast }$ expresses the update of the set of targets, and $Tas{k}_{j,k}\leftarrow TaskInf{o}_{j,k}^{\ast }$ expresses the update of the set of subtasks.

(1) The unknown targets appear

The initial target assignment is based on the initial situation awareness information, which can only cover the known targets but is not guaranteed to cover all the targets in the mission area. After the reconnaissance UAV or reconnaissance-attack UAV $V_i$ flies near the unknown target $T_j$ during task execution, it will detect the target and obtains the target information $TargetInf{o}_{new,j}$ and then updates the target set and the subtask set. Event trigger conditions can be described as

$$g(s(t),s_{t,j}(t))=DA(r_i,r_{nt,j},R_{detect,i})$$

where $DA(r_i,r_{nt,j},R_{detect,i})$ is defined as the reconnaissance payload constraint, which is the constraint on the relative position and angle relations between UAV $V_i$ and target $T_j$. The details are in reference [34]. When target $T_j$ is located in the detect area of the reconnaissance-attack UAV or reconnaissance UAV, $DA(r_i,r_{nt,j},R_{detect,i})\ge 0$; $r_i$ is the position vector of UAV $V_i$; $r_{nt,j}$ is the position vector of target $T_j$; $R_{detect,i}$ is the detection range of UAV $V_i$. The event-triggering process can be expressed as

$$\begin{array}{l}{E}_1:\mathrm{if}DA(r_i,r_{nt,j},R_{detect,i})\ge 0,\mathrm{then}Targe{t}_{N_{target}+j}\leftarrow TargetInf{o}_{new,j},\\ \hspace{1em}\hspace{1em}Tas{k}_{N_{target}+j,k}\leftarrow TaskInf{o}_{New,j,k}\end{array}(k=1,2,\dots N_{newtask,j})$$

where $Targe{t}_{N_{target}+j}\leftarrow TargetInf{o}_{new,j}$ indicates the update of target set, $N_{target}$ is the number of targets; $Tas{k}_{N_{target}+j,k}\leftarrow TaskInf{o}_{New,j,k}$ indicates the update of subtask set, $N_{newtask,j}$ is the number of subtasks of $T_j$.

(2) The UAV encounters faults and cannot perform tasks

During task execution, UAVs may encounter non-cooperative behaviors such as collision and attack and lose mission capability. Its tasks that have not been executed will be reassigned. Event triggering conditions can be described as

$$g(s(t),s_{t,j}(t))=h_{i,b}-h_i$$

where $h_i$ is the survivability of $V_i$; $h_{i,b}$ is the minimum survivability of $V_i$ with normal capability and is selected according to the concrete scenario. The event-triggering process can be expressed as

$$E_2:\mathrm{if}{h}_{i,b}-h_i\ge 0,\mathrm{then}Tas{k}_{j,k}\leftarrow TaskInf{o}_{i,j,k}(k=1,2,\dots ,N_{i,j})$$

where $Tas{k}_{j,k}\leftarrow TaskInf{o}_{i,j,k}$ is the reassignment for the subtasks that $V_i$ is to perform.

4.2. The Basic Process of Dynamic Task Assignment

Before describing the basic process of cooperative dynamic task assignment, the following assumptions are given for the scenario:

1. Based on the early situation awareness, several targets and pieces of threat information have been obtained, including target location, number of UAVs required to perform each subtask, threat location, and impact range;

2. Due to incomplete situational awareness, there are unknown targets and threats. After the UAV detects an unknown target or threat, it broadcasts the threat information, transmits the target information to the group leader, and triggers the assignment process.

Based on the scenario and assumptions above, the basic process of cooperative dynamic task assignment is shown in Figure 7. The concrete steps are as follows:

• Assign the known targets. The top leader assumes the role of the tenderee, dominates the initial assignment, and releases the target information to each group leader based on the inter-group contract network.
• Each group leader that has direct communication with the top leader receives the target information, releases the subtask information to their followers, and determines the group’s bidding scheme, which is obtained by subtasks pre-assignment based on the group’s internal contract network.
• The top leader selects the group with the largest bidding value as the bid winner according to the bidding schemes of the group submitted by the group leaders and assigns the target to the group.
• According to the assigned target, each subset performs tasks according to the corresponding subtask assignment scheme.
• If a UAV fails to perform tasks due to sudden failure, the tasks shall be assigned to other UAVs in this subset first; if no UAV in the subset can continue to perform, the group leader will release the tasks to other subsets, and then others will determine the pre-assignment scheme based on the contract network within the group. The tendering group shall determine the assistance according to each bidding scheme.
• If a UAV (including the group leader) detects a sudden target, it shall be reported to the group leader. After receiving the target information, the leader of this subset will release the target to other subsets. Each subset determines the pre-assignment scheme based on the contract network within the group, carries out the bidding based on the inter-group contract network, and, finally, completes the target and subtask assignment.
• Repeat steps 4–6 until there is no dynamic change.

5. Numerical Simulation

It is assumed that the swarm consists of 1 top leader and 2 subsets, with a total of 11 UAVs, including 2 reconnaissance-attack UAVs, 4 reconnaissance UAVs, and 4 attack UAVs. Among them, reconnaissance-attack UAVs are the group leaders. Consider the UAV swarm communication topology G₀, as shown in Figure 8.

Each UAV can perform no more than two subtasks, and each subtask is performed jointly by, at most, two UAVs. For flight path preplanning, the UAV kinematics model in reference [35] and the modified artificial potential field method [36,37,38] are used to realize the air-range estimation considering threat avoidance. The capability parameters of each UAV under the scenario are shown in

Table 1. The table of capability parameters of UAVs.

UAV	Initial Position (m)	The Maximum Air-Range (m)	Fuel Consumption Rate (m−1)	Velocity (m/s)	The Maximum Number of Tasks	Mission Capability
						Reconnaissance	Attack
V1	(2500,20,200)	10,000	0.01	120	2	√
V2	(0,20,200)	10,000	0.03	80	2	√	√
V3	(5000,20,200)	10,000	0.03	80	2	√	√
V4	(500,20,200)	10,000	0.01	120	2	√
V5	(1000,20,200)	10,000	0.01	120	2	√
V6	(1500,20,200)	10,000	0.02	100	2		√
V7	(2000,20,200)	10,000	0.02	100	2		√
V8	(4500,20,200)	10,000	0.01	120	2	√
V9	(4000,20,200)	10,000	0.01	120	2	√
V10	(3500,20,200)	10,000	0.02	100	2		√
V11	(3000,20,200)	10,000	0.02	100	2		√

, and the parameters of reconnaissance payload and attack payload are shown in

Table 2. The parameter table of UAV reconnaissance payload.

Flight Height H/m	Operating Distance Rs,max/m	Azimuth Search Angle φmax/°	Pitch Search Angle ϕmax/°	Mounting Angle α/°
200	500	45	30	30

and

Table 3. The parameter table of UAV attack load.

Flight Velocity V/m	The Minimum Launch Distance Ra,min/m	The Maximum off-Boresight Angle φa,max/°	The Maximum Operating Range of Guidance Equipment dmax/m	Maximum Horizontal Detection Angle of Guidance Equipment ± ϕa,max/°	Aiming Time of Guidance Equipmentta/s
100	80	60	30	±60	0.2

, respectively.

The feasible area of UAV reconnaissance and attack for a target on the ground, based on the above parameter configuration, is shown in Figure 9.

Consider a 5 × 5 km mission scenario. The information of known targets and the time window constraints of subtasks randomly generated is shown in

Table 4. The table of information on known targets.

Target	Coordinate (m)	Task Type		Time Window of S		Time Window of A
		Reconnaissance S	Attack A	Latest (s)	Earliest (s)	Latest (s)	Earliest (s)
T1	(538.4, 3516.3, 0)	√	√	73.7	93.7	98.7	123.7
T2	(1497.9, 3788.2, 0)	√	√	117.5	137.5	142.5	167.5
T3	(2396.8, 4602.3, 0)	√	√	150.3	170.3	175.3	200.3
T4	(4005.0, 4287.9, 0)	√	√	193.8	213.8	218.8	243.8
T5	(3359.0, 4171.4, 0)	√	√	249.6	269.6	274.6	299.6
T6	(1949.3, 3865.2, 0)	√	√	167.0	187.0	192.0	217.0

.

5.1. The Initial Task Assignment for Known Targets

Assume that the UAV swarm performs the reconnaissance-and-attack tasks at six enemy targets. The location of each UAV, threat, and target is shown in Figure 10.

Purple threats represent known threats, and blue threats represent unknown ones, all of which the coordinates are randomly generated. The targets are marked with “T”; Each UAV is marked with “V”, where “S” represents the reconnaissance UAV, “A” represents the attack UAV, and “SA” represents the reconnaissance–attack UAV.

In the simulation, the maximum value of the reconnaissance subtask is set at 100, the maximum value of the attack subtask is set at 150, and the attenuation factor $\lambda$ is set at 0.9.

Adopting the designed UAV swarm cooperative dynamic task assignment approach, the sequential task assignment results for known targets are shown in

Table 5. The task assignment of the UAV swarm.

UAV	Air-Range Estimation (m)	The Number of Tasks	The Execution Planning
V1	0	0	None
V2	3524.00	1	(T1, A, 98.7, 79.52)
V3	0	0	None
V4	3486.00	1	(T1, S, 73.7, 65.14)
V5	4230.00	2	(T2, S, 117.5, 62.14)→(T6, S, 167.0, 59.20)
V6	3756.52	1	(T2, A, 142.5, 74.87)
V7	3837.18	1	(T6, A, 192.0, 73.23)
V8	4298.74	1	(T5, S, 249.6, 57.04)
V9	6475.10	2	(T3, S, 150.3, 51.47)→(T4, S, 193.8, 57.34)
V10	4477.55	1	(T4, A, 218.8, 60.51)
V11	5702.98	2	(T3, A, 175.3, 56.75)→(T5, A, 274.6, 66.90)

. The task execution plan of each UAV is expressed in the format of (Target, Subtask type, Start time (s), Winning bidding value).

According to the known threat information and the unknown threat information detected by reconnaissance UAV during mission execution, the modified artificial potential field method is adopted to avoid local optimization, and the preplanning flight path considering threat avoidance during mission execution can be realized. Combined with the UAV swarm task assignment results, the preplanned path, and the task sequence, the swarm task execution diagram can be obtained, as shown in Figure 11.

As can be seen in Figure 11, the cooperative task assignment approaches can realize the “reconnaissance–attack” coverage of known targets under the consideration of flight path planning coupling and task time window constraints.

5.2. Dynamic TASK Assignment for Sudden Targets

Considering two unknown targets, T7 and T8, the swarm discovers targets through cooperative detection and then assigns tasks. The information of T7 and T8 is shown in

Table 6. The table of information on unknown targets.

Target	Coordinates (m)	Task Type
		Reconnaissance S	Attack A
T7	(3467.7, 2897.7, 0)	√	√
T8	(1307.7, 3057.7, 0)	√	√

, and the initial operational situation is shown in Figure 12.

The time when unknown targets are discovered by the UAVs and the corresponding subsets that discover the targets are shown in

Table 7. Information of unknown targets and corresponding subtasks.

Target	The Time It Is Discovered	Discoverer	Subset to Which the Discoverer Belongs	Time Window of S		Time Window of A
				Latest (s)	Earliest (s)	Latest (s)	Earliest (s)
T7	237.9	V8 (S)	2	271.0	291.0	291.0	316.0
T8	109.1	V5 (S)	1	155.8	175.8	175.8	200.8

. The generated subtask time window constraints are shown in Table 7 as well. The sequential task assignment results for the unknown targets are shown in

Table 8. The task assignment of the UAV swarm.

UAV	Air-range Estimation (m)	The Number of Tasks	The Execution Planning
V1	0	0	None
V2	3524.00	1	(T1, A, 98.7, 79.52)
V3	3262.79	1	(T7, A, 291.0, 84.77)
V4	4366.55	2	(T1, S, 73.7, 65.14)→(T8, S, 155.8, 32.90)
V5	4230.00	2	(T2, S, 117.5, 62.14)→(T6, S, 167.0, 59.20)
V6	4502.80	2	(T2, A, 142.5, 74.87)→(T8, A, 175.8, 135.13)
V7	3837.18	1	(T6, A, 192.0, 73.23)
V8	5747.08	2	(T5, S, 249.6, 57.04)→(T7, S, 271.0, 27.42)
V9	6475.10	2	(T3, S, 150.3, 51.47)→(T4, S, 193.8, 57.34)
V10	4477.55	1	(T4, A, 218.8, 60.51)
V11	5702.98	2	(T3, A, 175.3, 56.75)→(T5, A, 274.6, 66.90)

.

The swarm realizes the coverage of sudden targets through the distributed cooperative dynamic task allocation mechanism after the reconnaissance UAV V8, belonging to Subset 1, and the reconnaissance UAV V5, belonging to Subset 2, detect sudden targets T7 and T8, respectively, during task execution.

The concrete analysis is as follows: The reconnaissance UAV V4 and attack UAV V6, belonging to Subset 1, is assigned to perform the subtasks of sudden target T8 successively in the corresponding time window. The reconnaissance UAV V8 and reconnaissance-attack UAV V3, belonging to Subset 2, successively perform the subtasks of sudden target T7 in the corresponding time window so as to realize the “reconnaissance–strike” coverage of each sudden target.

We combine the assignment results with the preplanning flight path and task execution sequence based on the artificial potential field method. The diagrams of UAV swarm task execution and the execution sequence under sudden targets are shown in Figure 13.

Figure 13 indicates that through the dynamic task assignment approach based on the extended CNP, the swarm can mobilize the UAVs with task capability and the best execution effect obtained after bidding negotiation to complete tasks for each sudden target according to the time window.

5.3. Reassignment for Subtasks of Failed UAV

During the simulation, the reconnaissance UAV V5, belonging to Subset 1, fails and loses the capability to perform tasks. The failure time is 97.5 s.

According to the assignment results in Section 5.1, the reconnaissance UAV V5 prepares to perform the reconnaissance subtask. The fault of V5 triggers dynamic task assignment, and the tasks (T2, s, 117.5, 62.14)→(T6, s, 167.0, 59.20) of V5 become dynamic tasks. The bidding values of each group of potential bidders (including V2, V4, V3, and V8) are shown in

Table 9. The bidding values of potential bidders for dynamic subtasks.

Bidding Value of Subtask	Subset 1		Subset 2
	V2	V4	V3	V8
T2 (S)	10.72	30.88	−106.49	−48.62
T6 (S)	−6.74	21.83	−2.77	52.89

. The reassignment results of failed UAV subtasks obtained by the designed assignment approach are shown in

Table 10. Task assignment under the circumstance of UAV breakdown.

Subtask	Bidding Winner	Winning Bidding Value	Start Time (s)
T2 (S)	V4 (Subset 1)	30.88	117.5 s
T6 (S)	V8 (Subset 2)	52.89	167.0 s

.

The task assignment results in Table 9 show that UAV V4 of Subset 1 and UAV V8 of Subset 2 replace UAV V5 and continue to perform the tasks, respectively.

Combined with the assignment results, the diagrams of UAV swarm task execution and the execution sequence under UAV V5 failure are shown in Figure 14.

The explanation of the assignment result is as follows: after the reconnaissance, UAV V5 loses its mission capability, and its subtasks shall be preferentially executed by other reconnaissance UAVs or reconnaissance UAVs (i.e., V2 and V4) in Subset 1. It can be seen from Figure 14a that after the initial assignment in Section 4.1, the number of tasks that can be performed by UAV V4 is 1. Therefore, through the contract network within the group, it can undertake one reconnaissance subtask of V5. At this time, V2 is executing the attack subtask T1(a) according to the initial allocation results. During this execution, it crosses several threat areas, resulting in low survivability estimation, and the bidding value is negative, which is not suitable to continue to perform the subtask. Therefore, the leader UAV V2 of Subset 1 releases the information to Subset 2 for assistance through the contract network among the groups. Subset 2 conducts bidding negotiation through the contract network within the group and finally assigns UAV V8 to assist Subset 1 to take over reconnaissance subtask T6 (s).

5.4. The Analysis of the Real-Time Performance of the Assignment Approach

All the simulation experiments have been implemented on a personal PC; the parameters are Intel Core i5-5350U CPU @ 1.80 GHz 8 GB RAM, and the programming environment is MATLAB 2018b.

5.4.1. Real-Time Performance with Different Problem Scales

The real-time performance of the assignment approach is mainly influenced by three factors: ① the number of subsets of the UAV swarm; ② the number of UAVs in each subset; ③ the number of targets.

To illustrate the impact of the factors above, the variable-controlling method is adopted. The details of simulation cases to be compared are in

Table 11. The simulation cases to be compared.

Case	Number of Subsets	Number of UAVs of Each Subset	Number of Targets	The Size of the UAV Swarm
(a)	5, 10, 15, 20, 25	10	10	50, 100, 150, 200, 250
(b)	5	20, 40, 60, 80, 100	10	100, 200, 300, 400, 500
(c)	5	10	5, 10, 15, 20, 25	50

. Correspondingly, the comparison of assignment times in different cases is shown in Figure 15.

According to the comparison among the simulation, on one hand, due to the slowly increasing tendency of the assignment time in Figure 15a,b, it can be concluded that the real-time performance of the proposed approach has low sensitivity with the size of the UAV swarm. On the other hand, comparing (a) with (b), the task assignment time is more sensitive with the number of subsets than with the number of UAVs of each subset.

Moreover, according to Figure 15c, the task assignment time is sensitive to the number of targets, which indicates that the performance of the approach may become worse with the number of targets increasing.

5.4.2. Algorithm Comparison

In order to verify the effectiveness of the distributed approach based on contract network protocol (CNP) in solving the UAV swarm task assignment problem, it is compared with the centralized task assignment approach used in reference [10]. Scenarios are designed with different sizes of UAV swarm performing multiple task assignments. From the simulation results, both the centralized approach (ACO) and the distributed approach (CNP) are able to obtain the solution to the UAV swarm task assignment problem. However, the distributed approach (CNP) has an obvious advantage in terms of solution efficiency. The solution time for different sized assignment problems is shown in

Table 12. The real-time performance between the proposed approach and ACO in reference [10].

The Size of the UAV Swarm	The Number of Targets	The Total Solving Time of the CNP-Based Approach/(Seconds)	The Total Solving Time of ACO (50 Iterations)/(Seconds)
50	10	1.66	41.5
100	10	1.70	59.8
150	10	1.85	74.9
200	10	1.93	96.2
250	10	1.98	112.5
150	15	2.03	88.2
150	20	3.50	124.1
150	25	5.30	179.0

.

Remark:

Generally, a global optimal solution to such problems can rarely be obtained. Therefore, feasible solutions to the task assignment problem obtained in the solving process are considered in general.

As a heuristic algorithm, ACO searches in the solution space, learns from the results of each iteration, and finally converges to a feasible solution, which means that ACO requires a lot of computational resources and a much longer time. Simulation results show that this problem becomes more pronounced when the problem size (e.g., size of the UAV swarm, the number of targets) increases.

In contrast to heuristic algorithms such as ACO, CNP merely performs the optimization by bidding on each subset of UAVs as well as UAV individuals without the iterative process of searching for feasible solutions in a large solution space.

The results illustrate that, as a distributed assignment approach, the proposed method in this paper has advantages in real-time performance compared with the ACO proposed in reference [10], which proves the effectiveness of the method to some extent.

6. Conclusions

Aiming at the problem of the cooperative reconnaissance–attack task assignment of UAV swarms in complex environments, this paper proposes a distributed grouping cooperative dynamic task assignment approach by considering multiple constraints, realizes the effective assignment of cooperative reconnaissance–attack tasks to multiple targets, and optimizes the combat effectiveness of the swarm. The main conclusions include:

(1) The proposed extended CNP algorithm, which is based on the determination mechanism of cooperators and the selection mechanism of sequential tasks, with the bidding function considering the constraints of sequence, flight path, and threat; it can realize the reasonable assignment of reconnaissance and attack tasks on multiple targets under multiple constraints and the optimization of UAV swarm task execution efficiency.

(2) The proposed dynamic task assignment strategy based on the event-trigger mechanism constructs the overall architecture of cooperative dynamic task assignment for the distributed grouping of the UAV swarm and improves the adaptability of the swarm to the dynamic environment and sudden targets during task execution.

(3) Three typical simulation scenarios are designed. The simulation results show that the task assignment approach in this paper can solve the problem of cooperative sequential dynamic task assignment when the UAV swarm with subsets performs reconnaissance–attack tasks in a complex environment with incomplete situational awareness and sudden targets and realize reconnaissance and attack coverage on each target. Moreover, the real-time performance of the assignment approach has been analyzed, which indicates that the proposed approach has low sensitivity to the size of the UAV swarm.