# Hierarchical Task Assignment Strategy for Heterogeneous Multi-UAV System in Large-Scale Search and Rescue Scenarios

Authors: Jie Chen; Kai Xiao; Kai You; Xianguo Qing; Fang Ye; Qian Sun
Journal: International Journal of Aerospace Engineering
 (2021)

---

## Abstract

For the large-scale search and rescue (S&R) scenarios, the centralized and distributed multi-UAV multitask assignment algorithms for multi-UAV systems have the problems of heavy computational load and massive communication burden, which make it hard to guarantee the effectiveness and convergence speed of their task assignment results. To address this issue, this paper proposes a hierarchical task assignment strategy. Firstly, a model decoupling algorithm based on density clustering and negotiation mechanism is raised to decompose the large-scale task assignment problem into several nonintersection and complete small-scale task assignment problems, which effectively reduces the required computational amount and communication cost. Then, a cluster head selection method based on multiattribute decision is put forward to select the cluster head for each UAV team. These cluster heads will communicate with the central control station about the latest assignment information to guarantee the completion of S&R mission. At last, considering that a few targets cannot be effectively allocated due to UAVs’ limited and unbalanced resources, an auction-based task sharing scheme among UAV teams is presented to guarantee the mission coverage of the multi-UAV system. Simulation results and analyses comprehensively verify the feasibility and effectiveness of the proposed hierarchical task assignment strategy in large-scale S&R scenarios with dispersed clustering targets.


---

## Body

## 1. Introduction

Due to the advantages of no casualties, high flexibility, strong maneuverability, etc. [1–3], unmanned aerial vehicles (UAVs) are widely used in various search and rescue (S&R) scenarios, e.g., earthquake-hit areas or forest fire zones. Single UAV with limited capability and capacity cannot guarantee the multidimensional and extensive coverage of mission area [4, 5]. In order to carry out timely search and rescue to survivors in the S&R scenarios, the cooperative task assignment strategy for multi-UAV system is studied in this paper [6].For multi-UAV system in the S&R scenarios, the cooperative multi-UAV task assignment problem (CMTAP) has two characteristics: the time coupling constraints of tasks and the heterogeneity of UAVs.(1)
Each survivor needs to perform search (S) and rescue (R) tasks in sequence to achieve effective rescue. Thus, for the same target, the execution of S and R tasks needs to satisfy the task precedence constraint and task completion constraint. Besides, to ensure timely treatment of each survivor, its S and R tasks need to be carried out within a certain time window(2)
Different UAVs have different capabilities. Search UAVs equipped with various reconnaissance sensors can performS tasks to assessing damage and monitoring the environment, while rescue UAVs equipped with drugs, food, and other resources can perform R tasks to retrieve the wounded or dying survivorsTo solve the CMTAP model in the S&R scenarios, many scholars have raised two kinds of task assignment methods: centralized and distributed algorithms. However, these two kinds of algorithms both have some limitations in the large-scale S&R scenarios.CMTAP is a nondeterministic polynomial-time hard (NP-hard) combinational optimization problem [7, 8]. Centralized task assignment methods including the optimization methods (decision tree method [9], dynamic programming [10], etc.) and the intelligent optimization algorithms (ant colony algorithm [11, 12], particle swarm optimization algorithm [13, 14], genetic algorithm [15–17], etc.) depend on the central control station to make the execution plan for the multi-UAV system. With the increase of CMTAP scale, the optimization methods are faced with the risk of exponentially computational burden [18, 19]. [20] shows that when 2 UAVs need to perform search and strike mission against 3 targets, the optimization method can quickly search the entire solution space and obtain the optimal solution. However, when 8 UAVs are assigned to perform search and strike mission against 5 targets, the optimization method takes more than three weeks to produce the task assignment solution. Then, CMTAP is a combinational optimization problem with multiple constraints, and the intelligent optimization algorithms rely on iterations to obtain quick task assignment solutions. However, with the increase of CMTAP scale, there will be a large number of invalid solutions that violate the constraints in the iteration process, which seriously affects the efficiency of algorithms [4].Distributed task assignment algorithms including auction-based algorithm [21, 22], contract net method [23, 24], and consensus-based bundle algorithm (CBBA) [25–27] can produce timely execution plan for the multi-UAV system through the continuous communication and negotiation among all UAVs. The auction-based algorithm and contract net method have low communication efficiency and large communication cost, which is not conducive to realizing quick response in large-scale S&R scenarios [21]. CBBA has been developed into many extensions. [28] presents the grouped CBBA to improve the communication efficiency when ensuring the robustness and convergence of decentralized task assignment solution. Considering the scenario that some tasks must be allocated, [29] raises an extended CBBA to solve the decentralized task assignment problem with critical tasks. Further considering the fuel or time constraints in real-time scenarios, [30] extends CBBA to improve its assignment efficiency for the task allocation problem with spatially and temporally constraints. Besides, [31] evolves the swarm-generalized assignment problem method for better suitability for solving the task allocation problem in dynamic scenarios.Overall, the centralized and distributed task assignment algorithms have been greatly developed to solve different task assignment problems for multi-UAV systems. However, with the increase of CMTAP scale, the multi-UAV systems are faced with frequent and massive communication burden [32, 33]. Neither centralized nor distributed algorithms can produce real-time solution for the large-scale multi-UAV multitask assignment problem.Besides, in practical large-scale S&R scenarios, survivors tend to gather at different locations [34, 35]. That is, there will be dispersed clustering targets in the large-scale S&R scenarios. To realize the prompt response in the large-scale S&R scenarios with dispersed clustering targets, a hierarchical task assignment strategy is proposed to handle the multi-UAV multitask assignment problem.To effectively solve the task assignment problem in the large-scale S&R scenarios with dispersed clustering targets, the proposed hierarchical task assignment strategy is applied by the following procedures.(1)
Firstly, a model decoupling algorithm based on density clustering and negotiation mechanism is proposed to effectively decompose the whole task assignment model into several nonintersection and complete submodels with partial targets and UAVs. Then, the algorithm named CBBA with task coupling constraints [36] is applied to solve the local task assignment problem in each submodel. These two procedures ensure that the hierarchical task assignment strategy can produce conflict-free solution satisfying the time coupling constraints of tasks and the heterogeneity of UAVs in S&R scenarios and simultaneously reduces the computational amount and communication cost(2)
After that, the cluster head selection method based on multiattribute decision is put forward to select the cluster head for each UAV team according to the overall analyses of UAVs’ four factors including the mission execution time, the number of its undertaken tasks, the total score value, and the residual task capacity loads. These cluster head will communicate with the central control station about the local task assignment information to ensure the effective operation of S&R mission(3)
Finally, to realize the mission coverage in the S&R scenarios, an auction-based task sharing scheme among UAV teams is raised to assign the tasks that cannot be allocated within their submodels. The central control station and the cluster heads will participate in the auction process of unallocated targets to achieve the effective assignment of all tasks in the mission areaThe rest of this paper is constructed as follows. Section 2 illustrates the multi-UAV multitask assignment problem in the S&R scenarios and introduces the corresponding solution algorithm: CBBA with task coupling constraints. Then, Section 3 elaborates the hierarchical task assignment strategy including the hierarchical task assignment model, the model decoupling process, the cluster head selection, and the task sharing scheme. Simulations are given in Section 4 to demonstrate the effectiveness of the proposed hierarchical task assignment strategy in the large-scale S&R scenarios with dispersed clustering targets. At last, Section 5 concludes this paper.


## 2. Multi-UAV Multitask Assignment Problem

In the S&R scenarios, heterogeneous multiple UAVs need to successively perform search (S) and rescue (R) tasks on multiple stationary ground targets. Notably, in this paper, we assume that the mission area has been scouted, and the information (number, locations, etc.) of survivors is known [37, 38].


### 2.1. UAVs

Assume that there areNU heterogeneous UAVs in the multi-UAV system, the set of UAVs is
(1)U=U1type,U2type,⋯,UNUtype,where the superscript type∈S,R respectively denotes the search and rescue UAVs.The heterogeneity of UAVs reflects on different capabilities and kinematics parameters.(1)
Firstly, search UAV (S-UAV) equipped with various reconnaissance sensors is only capable to perform S task, while rescue UAV (R-UAV) equipped with drugs, food, and other resources is only capable to perform R task(2)
Then, different UAV has different cruise speed and fuel consumption rate(2)v=v1,v2,⋯,vNUms,(3)f=f1,f2,⋯,fNUkm.The cruise speeds and fuel consumption rates of UAVs are respectively introduced to describe the flight cost of UAVs and the fuel cost of UAVs. [39] reveals that the fuel consumption rate of actual flight is close to be linear to UAV’s flight distance. Thus, the fuel consumptions of UAVs are assumed to be constant in this paper.Besides, to simulate the practical S&R scenarios, assume that UAVUii=1,2,⋯,NU can be assigned a maximum of Lti tasks. That is, the task capacity of each UAV is limited.


### 2.2. Tasks

Suppose that there areNT stationary ground targets in the S&R mission, each target has two tasks MT=S,R(S,R separately represent the search and rescue tasks) need to be performed successively. The set of tasks is
(4)T=T1S,T2S,⋯,TNTS,T1R,T2R,⋯,TNTR=T1,T2,⋯,TNt,where TjS,TjRj=1,2,⋯,NT separately represent the S,R tasks of target j and Nt=2NT is the number of tasks.The time coupling constraints of tasks in the S&R scenarios reflect on task precedence constraint, task completion constraint, and time-sensitive constraint.(1)
For each target, the execution of two tasks should follow strict task precedence constraint thatR task can be performed only if S task is completed(2)
The task completion constraint means thatS and R tasks should be both assigned to guarantee the successful rescue of certain survivor(3)
To ensure the effective rescue of each survivor, itsS and R tasks should be performed within certain time windowSuppose that the performing times ofS and R tasks of target j are separately tjS,tjR, the time window of target j is tjstart,tjend, the execution durations of S and R tasks are separately tΔ1,tΔ2; the time coupling constraints can be defined as follows.
(5)tjstart≤tjS<tjR≤tjend,(6)tjS+tΔ1≤tjR,(7)tjR+tΔ2≤tjend.


### 2.3. Task Assignment Model

The multi-UAV multitask assignment problem in the S&R scenarios is described asNU heterogeneous UAVs need to consecutively perform S and R tasks on NT stationary ground targets (total Nt=2NT tasks). The objective of the task assignment model is to find a conflict-free matching of tasks to UAVs that maximizes the global reward and simultaneously satisfies the time coupling constraints of tasks and heterogeneity of UAVs.
(8)max∑i=1NU∑j=1Ntcijxi,pixij,subject to
(9)∑j=1Ntxij≤Lti,(10)∑i=1NU∑j=1Ntxij≤Nmin≜Nt,∑i=1NULti,(11)∑i=1NUxij≤1,(12)∑i=1NUxij+NT≤1,(13)∑i=1NUxij+∑i=1NUxij+NT=0,2,(14)tjstart≤tj<tj+NT≤tjend,(15)tj+tΔ1≤tj+NT,(16)tj+NT+tΔ2≤tjend,∀i=1,2⋯,NU,j=1,2⋯,NT.According to (4), Tj,Tj+NT∈T separately represents S and R tasks of target j. xij,xij+NT∈0,1 is the decision variable. xij,xij+Nt/2=1 if and only if task Tj,Tj+Nt/2 is allocated to UAV Ui∈U. xi∈0,1Nt is the decision vector, whose jth element is xij. pi∈T∪∅Lti represents the ordered task sequence of UAV Ui, whose kth element is Tj if UAV Ui conducts task Tj at kth waypoint along its task path, and becomes ∅ (empty task) if UAV conducts less than k tasks. The scoring function cijxi,pi≥0 is assumed to be a certain nonnegative function of xi or its path pi. The summation term inside the first parenthesis represents the local reward for UAV Ui, which is the sum of the rewards of its assigned tasks in path pi.The multi-UAV multitask assignment problem described above satisfies the time coupling constraints of tasks and the heterogeneity of UAVs in the S&R scenarios.(1)
The decision variablexij,xij+NT should meet the constraint on different capabilities of UAVs. That is, only S-UAV can perform S task of target j, and only R-UAV can perform its R task(2)
The different kinematics parameters of UAVs reflect on different cruise speed and fuel consumption rate, thus reflect on the scoring functioncijxi,pi in the task assignment model. The scoring value of UAV Ui performing task Tj is defined as(17)cijxi,pixij=Rj0+e−λjtij−tjstartRjutij−fiΔDij,where Rj0,Rjj=1,2,⋯,Nt separately represents the fixed reward and initial reward associated with task Tj, λj is the value decrement factor, tij is the execution time of task Tj in UAV Ui’s path pi, uij is the binary variable that shows if the constraint of time window is satisfied (defined below), and ΔDij is the distance from UAV Ui’s initial location to task Tj’s location.
(18)utij=1iftjstart≤tij≤tjend0otherwise.(3)
Considering the limited payload of UAVs, each UAV has limited capacity (9). That is, UAV Ui can perform a maximum of Lti limited tasks(4)
We can see from (13) that the S and R tasks of each target should be both assigned; otherwise, the target cannot be effectively rescued. Thus, task completion constraint is well described(5)
The task precedence constraint and time-sensitive constraint are reflected on (14)–(16). That is, S and R tasks of target j should be performed in sequence, and both S and R tasks should be performed in certain time window


### 2.4. CBBA-TCC

To solve the multi-UAV multitask assignment problem with time coupling constraints of tasks and the heterogeneity of UAVs in the S&R scenarios, an extension of CBBA, named consensus-based bundle algorithm with task coupling constraints (CBBA-TCC), has been raised in [29]. The flow diagram of CBBA-TCC is given in Figure 1. Details about CBBA-TCC please see [29].Figure 1
CBBA-TCC.CBBA-TCC can realize conflict-free task assignment through the iterations between inner and outer consensus stages. The inner consensus stage can guarantee that the task assignment solution meets the task precedence constraint and time-sensitive constraint in (14)–(16), while the outer consensus stage is raised to ensure that the task completion constraint in (13) is satisfied. [29] proves that CBBA-TCC can produce feasible and conflict-free task assignment solution in the S&R scenarios. Therefore, the multi-UAV multitask assignment problem in Section 2.3 is properly solved.Take the communication topology of the multi-UAV system as an undirected graph, the shortest path between two UAVsUi,Uki,k=1,2,⋯,NU is dik<∝. Thus, the network diameter of the communication topology is defined as
(19)D=maxi,k=1,2,⋯,NUdik.Accordingly, each UAV needs to communicate a maximum ofD times to get consensus solution. Besides, the worse situation is that only one task is assigned in one iteration of communication and negotiation. Thus, multi-UAV system needs a maximum of Nmin iterations to get global task assignment result. Therefore, the maximum communication amount of CBBA-TCC to produce feasible and conflict-free task assignment solution is
(20)Y=NminD.


## 2.1. UAVs

Assume that there areNU heterogeneous UAVs in the multi-UAV system, the set of UAVs is
(1)U=U1type,U2type,⋯,UNUtype,where the superscript type∈S,R respectively denotes the search and rescue UAVs.The heterogeneity of UAVs reflects on different capabilities and kinematics parameters.(1)
Firstly, search UAV (S-UAV) equipped with various reconnaissance sensors is only capable to perform S task, while rescue UAV (R-UAV) equipped with drugs, food, and other resources is only capable to perform R task(2)
Then, different UAV has different cruise speed and fuel consumption rate(2)v=v1,v2,⋯,vNUms,(3)f=f1,f2,⋯,fNUkm.The cruise speeds and fuel consumption rates of UAVs are respectively introduced to describe the flight cost of UAVs and the fuel cost of UAVs. [39] reveals that the fuel consumption rate of actual flight is close to be linear to UAV’s flight distance. Thus, the fuel consumptions of UAVs are assumed to be constant in this paper.Besides, to simulate the practical S&R scenarios, assume that UAVUii=1,2,⋯,NU can be assigned a maximum of Lti tasks. That is, the task capacity of each UAV is limited.


## 2.2. Tasks

Suppose that there areNT stationary ground targets in the S&R mission, each target has two tasks MT=S,R(S,R separately represent the search and rescue tasks) need to be performed successively. The set of tasks is
(4)T=T1S,T2S,⋯,TNTS,T1R,T2R,⋯,TNTR=T1,T2,⋯,TNt,where TjS,TjRj=1,2,⋯,NT separately represent the S,R tasks of target j and Nt=2NT is the number of tasks.The time coupling constraints of tasks in the S&R scenarios reflect on task precedence constraint, task completion constraint, and time-sensitive constraint.(1)
For each target, the execution of two tasks should follow strict task precedence constraint thatR task can be performed only if S task is completed(2)
The task completion constraint means thatS and R tasks should be both assigned to guarantee the successful rescue of certain survivor(3)
To ensure the effective rescue of each survivor, itsS and R tasks should be performed within certain time windowSuppose that the performing times ofS and R tasks of target j are separately tjS,tjR, the time window of target j is tjstart,tjend, the execution durations of S and R tasks are separately tΔ1,tΔ2; the time coupling constraints can be defined as follows.
(5)tjstart≤tjS<tjR≤tjend,(6)tjS+tΔ1≤tjR,(7)tjR+tΔ2≤tjend.


## 2.3. Task Assignment Model

The multi-UAV multitask assignment problem in the S&R scenarios is described asNU heterogeneous UAVs need to consecutively perform S and R tasks on NT stationary ground targets (total Nt=2NT tasks). The objective of the task assignment model is to find a conflict-free matching of tasks to UAVs that maximizes the global reward and simultaneously satisfies the time coupling constraints of tasks and heterogeneity of UAVs.
(8)max∑i=1NU∑j=1Ntcijxi,pixij,subject to
(9)∑j=1Ntxij≤Lti,(10)∑i=1NU∑j=1Ntxij≤Nmin≜Nt,∑i=1NULti,(11)∑i=1NUxij≤1,(12)∑i=1NUxij+NT≤1,(13)∑i=1NUxij+∑i=1NUxij+NT=0,2,(14)tjstart≤tj<tj+NT≤tjend,(15)tj+tΔ1≤tj+NT,(16)tj+NT+tΔ2≤tjend,∀i=1,2⋯,NU,j=1,2⋯,NT.According to (4), Tj,Tj+NT∈T separately represents S and R tasks of target j. xij,xij+NT∈0,1 is the decision variable. xij,xij+Nt/2=1 if and only if task Tj,Tj+Nt/2 is allocated to UAV Ui∈U. xi∈0,1Nt is the decision vector, whose jth element is xij. pi∈T∪∅Lti represents the ordered task sequence of UAV Ui, whose kth element is Tj if UAV Ui conducts task Tj at kth waypoint along its task path, and becomes ∅ (empty task) if UAV conducts less than k tasks. The scoring function cijxi,pi≥0 is assumed to be a certain nonnegative function of xi or its path pi. The summation term inside the first parenthesis represents the local reward for UAV Ui, which is the sum of the rewards of its assigned tasks in path pi.The multi-UAV multitask assignment problem described above satisfies the time coupling constraints of tasks and the heterogeneity of UAVs in the S&R scenarios.(1)
The decision variablexij,xij+NT should meet the constraint on different capabilities of UAVs. That is, only S-UAV can perform S task of target j, and only R-UAV can perform its R task(2)
The different kinematics parameters of UAVs reflect on different cruise speed and fuel consumption rate, thus reflect on the scoring functioncijxi,pi in the task assignment model. The scoring value of UAV Ui performing task Tj is defined as(17)cijxi,pixij=Rj0+e−λjtij−tjstartRjutij−fiΔDij,where Rj0,Rjj=1,2,⋯,Nt separately represents the fixed reward and initial reward associated with task Tj, λj is the value decrement factor, tij is the execution time of task Tj in UAV Ui’s path pi, uij is the binary variable that shows if the constraint of time window is satisfied (defined below), and ΔDij is the distance from UAV Ui’s initial location to task Tj’s location.
(18)utij=1iftjstart≤tij≤tjend0otherwise.(3)
Considering the limited payload of UAVs, each UAV has limited capacity (9). That is, UAV Ui can perform a maximum of Lti limited tasks(4)
We can see from (13) that the S and R tasks of each target should be both assigned; otherwise, the target cannot be effectively rescued. Thus, task completion constraint is well described(5)
The task precedence constraint and time-sensitive constraint are reflected on (14)–(16). That is, S and R tasks of target j should be performed in sequence, and both S and R tasks should be performed in certain time window


## 2.4. CBBA-TCC

To solve the multi-UAV multitask assignment problem with time coupling constraints of tasks and the heterogeneity of UAVs in the S&R scenarios, an extension of CBBA, named consensus-based bundle algorithm with task coupling constraints (CBBA-TCC), has been raised in [29]. The flow diagram of CBBA-TCC is given in Figure 1. Details about CBBA-TCC please see [29].Figure 1
CBBA-TCC.CBBA-TCC can realize conflict-free task assignment through the iterations between inner and outer consensus stages. The inner consensus stage can guarantee that the task assignment solution meets the task precedence constraint and time-sensitive constraint in (14)–(16), while the outer consensus stage is raised to ensure that the task completion constraint in (13) is satisfied. [29] proves that CBBA-TCC can produce feasible and conflict-free task assignment solution in the S&R scenarios. Therefore, the multi-UAV multitask assignment problem in Section 2.3 is properly solved.Take the communication topology of the multi-UAV system as an undirected graph, the shortest path between two UAVsUi,Uki,k=1,2,⋯,NU is dik<∝. Thus, the network diameter of the communication topology is defined as
(19)D=maxi,k=1,2,⋯,NUdik.Accordingly, each UAV needs to communicate a maximum ofD times to get consensus solution. Besides, the worse situation is that only one task is assigned in one iteration of communication and negotiation. Thus, multi-UAV system needs a maximum of Nmin iterations to get global task assignment result. Therefore, the maximum communication amount of CBBA-TCC to produce feasible and conflict-free task assignment solution is
(20)Y=NminD.


## 3. Hierarchical Task Assignment Strategy

In the large-scale S&R scenarios, survivors tend to gather in different locations. Due to potential problems of exponentially computational complexity and massive communication burden, it is impractical to use centralized or distributed task assignment algorithms to produce real-time task assignment solutions for the large-scale S&R scenarios. Thus, the hierarchical task assignment strategy is proposed for the large-scale S&R scenarios with dispersed clustering targets.Firstly, the hierarchical task assignment model of the large-scale S&R scenarios is discussed. The theoretical analysis about the communication amount of the hierarchical task assignment strategy is deduced to prove the effectiveness of the proposed algorithm in the large-scale S&R scenarios. Then, the proposed hierarchical task assignment strategy consists of three main innovations: model decoupling of the large-scale task assignment problem, cluster head selection ofNC submodels, and the task sharing scheme among multiple UAV teams. Thus, these three procedures of the proposed algorithm are also elaborated.


### 3.1. Hierarchical Task Assignment Model

Firstly, the large-scale task assignment model withNU UAVs and NT targets can be decomposed into NC submodels. The UAV set and target set in these submodels are defined as U1,U2,⋯,UNC and T1,T2,⋯,TNC.To produce conflict-free solution for the whole task assignment problem, UAVs and targets in these submodels should be nonintersection and complete.(21)Up∩Uq=∅,(22)U1∪U2∪⋯∪UNC=U,(23)U1+U2+⋯+UNC=U=NU,(24)Tp∩Tq=∅,(25)T1∪T2∪⋯∪TNC=T,(26)T1+T2+⋯+TNC=T=NT,∀p,q=1,2,⋯,NC.(22) and (23) and (25) and (26) reflect that the total number of UAVs (targets) in all submodels should equal to that of the whole task assignment model. (21) and (24) reflect that there is no overlap of UAVs (targets) among different subteams.Accordingly, the large-scale task assignment problem with dispersed clustering targets has been decomposed intoNC nonintersection and complete submodels.Then, suppose that the UAV set and task set inqthq=1,2,⋯,NC submodel are separately Uq=U1type,U2type,⋯,UNUqtype and Tq=T1S,T2S,⋯,TNTQS,T1R,T2R,⋯,TNTQR=T1,T2,⋯,TNTq, the corresponding multi-UAV multitask assignment model is shown below.
(27)max∑Ui∈Uq∑Tj∈Tqcijxi,pixij,subject to
(28)∑Tj∈Tqxij≤Lti,(29)∑Ui∈Uq∑Tj∈Tqxij≤Nq,min=NTq,∑Ui∈UqLti,(30)∑Ui∈Uqxij≤1,(31)∑Ui∈Uqxij+NTQ≤1,(32)∑Ui∈Uqxij+∑Ui∈Uqxij+NTQ=0,2,(33)tjstart≤tj<tj+NTQ≤tjend,(34)tj+tΔ1≤tj+NTQ,(35)tj+NTQ+tΔ2≤tend,∀i=1,2,⋯,NUq,j=1,2,⋯,NTQ, where NUq,NTQ, and NTq respectively denote the numbers of UAVs, targets, and tasks in qth submodel.Apparently, the multi-UAV multitask assignment model in submodel can be solved by CBBA-TCC.According to (20), the maximum communication amount of qth submodel is
(36)Yq=Nq,minDq.Then, the maximum communication amount of the hierarchical task assignment model is(37)Y′=∑q=1NCYq=∑q=1NCNq,minDq≤∑q=1NCNq,minD=∑q=1NCNq,min×D=NminD=Y.Obviously, through effective model decomposition, the hierarchical task assignment model has less communication requirements than the original task assignment model. Notably, whenNC is large, there will be a great deal of submodels. Under this circumstance, Y′≪Y; thus, the required communication amount is well reduced.


### 3.2. Model Decoupling Algorithm Based on Density Clustering and Negotiation Mechanism

Last section proves that the hierarchical task assignment model effectively reduces the required communication amount. Thus, the core is to study the dimensional reduction method that can break the large-scale task assignment model with dispersed clustering targets into several nonintersection and complete submodels. To address this issue, a model decoupling algorithm based on density clustering and negotiation mechanism (MDA-DCNM) is put forward. The schematic diagram of MDA-DCNM is given in Figure2.Figure 2
MDA-DCNM.According to Figure2, MDA-DCNM consists of two procedures. Firstly, the density clustering method is applied to effectively cluster these dispersed clustering targets. Then, according to UAVs’ limited resources and different task requirements of these clustered targets, negotiation mechanism is utilized to form heterogeneous UAV teams for these clustered targets. Therefore, the large-scale task assignment problem with dispersed clustering targets can be decomposed into several nonintersection and complete small-scale task assignment problems, which effectively reduces the required computational amount and communication cost.


#### 3.2.1. Density Clustering of Targets

According to the distribution of targets in the mission area, the central control station firstly introduces the density clustering method to divideNT targets into NC subclusters. Since density clustering method finds different clusters by constantly connecting high-density points in the neighborhood, there are only two parameters needed: neighborhood size MinPts and density threshold ε. Thus, different from K-mean clustering method, density clustering method can find clusters with different shapes and scales, which is suitable to divide these dispersed clustering targets into multiple different subteams [40, 41]. The algorithmic flow of density clustering method in this paper is shown in Algorithm 1.Algorithm 1: Density clustering of targets.
InputNT targets, clustered parameters MinPts,ε.OutputNC clustered target sets T1,T2,⋯,TNC.1:Ω=∅2: forj∈T do3: ifNεj≥MinPts do4:Ω=Ω∪j5: end if6: end for7:k=0,Γ=T8: whileΩ≠∅ do9:Γ~=T10:H=o, random choose o∈Ω11:Γ=Γ\o12:  whileH≠∅ do13:   ifNεh≥MinPts do, h∈H14:Δ=Nεh∩Γ15:H=H∪Δ16:Γ=Γ\Δ17:   end if18:  end while19:k=k+120:Tk=Γ~\T21:Ω=Ω\Tk22: end whileTherefore,NT targets have been clustered into NC target sets: T1,T2,⋯,TNC. The task sets in these target clusters are T¯1,T¯2,⋯,T¯NC, where q=1,2,⋯NC,T¯q=T1S,T2S,⋯,TNTQS,T1R,T2R,⋯,TNTQR.


#### 3.2.2. Negotiation-Based Assignment of UAVs

Different UAVs have different limited task capacities, and different subclusters have different number of targets. According to the different requirements of tasks in different subclusters, negotiation-based assignment algorithm is proposed to allocate different UAV teams to these subclusters.AsNT targets have been clustered to NC target sets: T1,T2,⋯,TNC, the requirements for S and R tasks in these subclusters are separately defined as
(38)ReS=Re1S,Re2S,⋯,ReNCS,(39)ReR=Re1R,Re2R,⋯,ReNCR.Suppose that there areNSS-UAVs and NRR-UAVs in the multi-UAV system, the UAV sets that can perform S and R tasks are separately defined as
(40)US=U1,U2,⋯,UNS,(41)UR=U1,U2,⋯,UNR.In this paper, assume thatS-UAV has unlimited capacity, while R-UAV has limited task capacity due to its limited goods payload. Thus, the negotiation mechanism is only applied to assign R-UAVs to these subclusters. After that, S-UAVs will be correspondingly allocated based on the assignment of R-UAVs.Firstly, the limited task capacities ofR-UAVs are respectively defined as
(42)LtR=Lt1,Lt2,⋯,LtNR.The negotiation-based assignment ofR-UAVs is given in Algorithm 2.Algorithm 2: Negotiation-based assignment of R-UAVs.
InputReR,LtR.OutputNC R-UAV teams: U1R,U2R,⋯,UNCR.1:U1=∅,U2=∅,⋯,UNC=∅2: whileLtR≠∅ do3:jT=argmaxReR4:jU=argmaxLtR5:RejT=RejT−LtjU6:LtjU=07:UjTR=UjTR∩jU8: end whileThen, the S-UAV teams ofNC submodels can be proportionally assigned based the assignment results of R-UAVs. The number of S-UAVs in qthq=1,2,⋯,NC submodel is
(43)NUqS=NUqR∑p=1NCNUpR×NS.An example is given to illustrate the negotiation-based assignment of UAVs.Suppose that the whole task assignment model withNU=14 UAVs and NT=40 dispersed clustering targets can be divided into NC=3 subclusters according to density clustering method, the number of targets in NC=3 subteams is T1=8,T2=12,TNC=20. Thus, the requirements of R tasks in NC=3 subclusters are
(44)ReR=Re1R,Re2R,Re3R=8,12,20.Assume that the multi-UAV system hasNS=7S-UAVs and NR=7R-UAVs, the UAV set is
(45)U=US1,US2,⋯,US7,UR1,UR2,⋯,UR7.Besides, the limited task capacities ofNR R-UAVs are
(46)LtR=Lt1,Lt2,⋯,Lt7=9,10,6,5,7,8,4.Table1 shows the demonstration of the negotiation-based assignment of R-UAVs.Table 1
Demonstration ofR-UAV allocation based on negotiation mechanism.
ProceduresAssignment informationStep 0ReR=8,12,20,LtR=9,10,6,5,7,8,4U1R=∅,U2R=∅,U3R=∅Step 1jT=3,jU=2ReR=8,12,10,LtR=9,0,6,5,7,8,4U1R=∅,U2R=∅,U3R=U2RStep 2jT=2,jU=1ReR=8,3,10,LtR=0,0,6,5,7,8,4U1R=∅,U2R=U1R,U3R=U2RStep 3jT=3,jU=6ReR=8,3,2,LtR=0,0,6,5,7,0,4U1R=∅,U2R=U1R,U3R=U2R,U6RStep 4jT=1,jU=5ReR=1,3,2,LtR=0,0,6,5,0,0,4U1R=U5R,U2R=U1R,U3R=U2R,U6RStep 5jT=2,jU=3ReR=1,−3,2,LtR=0,0,0,5,0,0,4U1R=U5R,U2R=U1R,U3RU3R=U2R,U6RStep 6jT=3,jU=4ReR=1,−3,−3,LtR=0,0,0,0,0,0,4U1R=U5R,U2R=U1R,U3RU3R=U2R,U6R,U4RStep 7jT=1,jU=7ReR=−3,−3,−3,LtR=0,0,0,0,0,0,0U1R=U5R,U7R,U2R=U1R,U3RU3R=U2R,U6R,U4RAccording to Table1, the assignment results of NC=3R-UAV teams are
(47)U1R=U5R,U7R,(48)U2R=U1R,U3R,(49)U3R=U2R,U6R,U4R,After that, theNC UAV teams can be derived as
(50)U1=U1S,U2S,U5R,U7R,(51)U2=U3S,U4S,U1R,U3R,(52)U3=U5S,U6S,U7S,U2R,U6R,U4R.In Table1, after 7th negotiation, ReR=−3,−3,−3, which means that the residual task capacities of NC UAV teams against targets’ requirements on R tasks all equal to 3. Accordingly, the negotiation-based assignment algorithm can form corresponding UAV teams when balancing the residual task capacities of different UAV teams.Besides, there is no overlap of UAVs (targets) among different subteams. Therefore, the proposed MDR-DCNM effectively divides the large-scale task assignment model with dispersed clustering targets into multiple small-scale and nonoverlapping task assignment problem.After that, CBBA-TCC is adopted to solve these small-scale task assignment problems. It is obvious that the solutions of these nonintersection and complete small-scale task assignment problems are conflict-free. Thus, MDR-DCNM can realize conflict-free task assignment for the large-scale S&R scenarios.


### 3.3. Cluster Head Selection Based on Multiattribute Decision

The local task assignment problem in these subclusters has been well solved. Then, the cluster head of each UAV team should send these local task assignment solutions back to central control station for further management. Apparently, the cluster head of each UAV team undertakes extracommunication burden. Besides, since CBBA-TCC depends on communications to generate consensus task assignment solution, the selection of cluster head in each UAV team affects the efficiency of local task assignment. To address this issue, a cluster head selection approach based on multiattribute decision (CHS-MAD) is put forward to choose the cluster head of each UAV team according to the overall analyses of UAVs’ four factors including the mission execution time, the number of undertaken tasks, the total score values, and the residual task capacities.Firstly, suppose that there areNUq UAVs assigned to qthq=1,2,⋯,NC submodel, where the number of S-UAVs and R-UAVs is respectively NNUqS and NNUqR, the UAV set can be defined as
(53)Uq=U1S,U2S,⋯,UNNUqSS,U1R,U2R,⋯,UNNUqRR=U1,U2,⋯,UNUq.According to the local task assignment solution inqth submodel, four attributes of NUq UAVs can be defined as
(54)tUq=t1,t2,⋯,tNUq,(55)nUq=n1,n2,⋯,nNUq,(56)cUq=c1,c2,⋯,cNUq,(57)γUq=γ1,γ2,⋯,γNUq.(54) denotes the mission execution time of NUq UAVs. If certain UAV has longer mission execution time, it means that the UAV has less unoccupied time; thus, its probability to be chosen as the cluster head is less.(55) denotes the number of UAVs' undertaken tasks. If certain UAV has larger number of undertaken tasks, it reflects that the UAV carries out more tasks; thus, its probability to be chosen as the cluster head is less.(56) denotes the total score value of UAVs. If certain UAV has bigger score value, it means that the UAV has greater roles in the sub-model; thus, its probability to be chosen as the cluster head is less.(57) denotes the residual task capacities of UAVs. If certain UAV has larger residual task capacity, it reflects that the UAV has stronger flexibility during the task execution; thus, its probability to be chosen as the cluster head is bigger.Then, DS evidence theory is adopted to form the multiattribute decision approach. DS evidence theory is a multisource fusion method with quick response and well measurement about uncertain information [42]. Multiattribute decision based on DS evidence theory can comprehensively consider the complementarity and redundancy of four attributes to select the suitable cluster head for each subteam [43]. The DS fusion equation is
(58)MUi=11−K∑∩H=Ui∏1≤f≤4mfH,where K is the conflict factor that defined as
(59)K=∑∩H=∅∏1≤f≤4mfH.The mass functionsmfH,f=1,2,3,4 respectively denote UAVs’ probabilities to be selected as the cluster-head according to four attributes in (54)–(57).
(60)m1Ui=t∧i−2∑p=1NUqt∧i−2,(61)m2Ui=n∧i−2∑p=1NUqn∧i−2,(62)m3Ui=c∧i−2∑p=1NUqc∧i−2,(63)m4Ui=γi∑p=1NUqγp,where
(64)t^i=timaxi=1,2,⋯,NUqti,(65)n^i=nimaxi=1,2,⋯,NUqni,(66)c^i=cimaxi=1,2,⋯,NUqci.Finally, the UAV with largest probability in the fusion resultMUi will be chosen as the cluster head of qth submodel.
(67)Ji=argmaxfMUf.


### 3.4. Auction-Based Task Sharing Scheme among UAV Teams

A problem occurs when a subteam is unable to perform all of its assigned tasks due to UAVs’ limited and unbalanced resources [44]. Thus, an auction-based task-sharing scheme among UAV teams (ATS-UT) is raised to allocate the unassigned tasks. In the proposed algorithm, the central control station and cluster heads of all UAV teams will participate in the auction process of the unallocated tasks to achieve the effective assignment of all tasks in the mission area and further guarantee the mission coverage of the multi-UAV system in the entire S&R scenarios. The algorithmic diagram of ATS-UT is shown in Figure 3.Figure 3
ATS-UT.In Figure3, CBBA-PR represents CBBA with partial replanning that raised in [45, 46]. CBBA-PR partially resets original task schedules to efficiently and quickly allocate the new task. Thus, CBBA-PR is adopted to solve the allocation of unassigned task in this paper.Firstly, the central control station will announce the unallocated tasks to all UAV teams once at a time. Then, cluster head of each UAV team will use CBBA-PR to calculate the score increment of the announced task and send it back to the central control station. Finally, the central control station will choose the UAV team with highest score increment to perform the announced task. After iterations of ATS-UT, all unallocated tasks can be well assigned.


## 3.1. Hierarchical Task Assignment Model

Firstly, the large-scale task assignment model withNU UAVs and NT targets can be decomposed into NC submodels. The UAV set and target set in these submodels are defined as U1,U2,⋯,UNC and T1,T2,⋯,TNC.To produce conflict-free solution for the whole task assignment problem, UAVs and targets in these submodels should be nonintersection and complete.(21)Up∩Uq=∅,(22)U1∪U2∪⋯∪UNC=U,(23)U1+U2+⋯+UNC=U=NU,(24)Tp∩Tq=∅,(25)T1∪T2∪⋯∪TNC=T,(26)T1+T2+⋯+TNC=T=NT,∀p,q=1,2,⋯,NC.(22) and (23) and (25) and (26) reflect that the total number of UAVs (targets) in all submodels should equal to that of the whole task assignment model. (21) and (24) reflect that there is no overlap of UAVs (targets) among different subteams.Accordingly, the large-scale task assignment problem with dispersed clustering targets has been decomposed intoNC nonintersection and complete submodels.Then, suppose that the UAV set and task set inqthq=1,2,⋯,NC submodel are separately Uq=U1type,U2type,⋯,UNUqtype and Tq=T1S,T2S,⋯,TNTQS,T1R,T2R,⋯,TNTQR=T1,T2,⋯,TNTq, the corresponding multi-UAV multitask assignment model is shown below.
(27)max∑Ui∈Uq∑Tj∈Tqcijxi,pixij,subject to
(28)∑Tj∈Tqxij≤Lti,(29)∑Ui∈Uq∑Tj∈Tqxij≤Nq,min=NTq,∑Ui∈UqLti,(30)∑Ui∈Uqxij≤1,(31)∑Ui∈Uqxij+NTQ≤1,(32)∑Ui∈Uqxij+∑Ui∈Uqxij+NTQ=0,2,(33)tjstart≤tj<tj+NTQ≤tjend,(34)tj+tΔ1≤tj+NTQ,(35)tj+NTQ+tΔ2≤tend,∀i=1,2,⋯,NUq,j=1,2,⋯,NTQ, where NUq,NTQ, and NTq respectively denote the numbers of UAVs, targets, and tasks in qth submodel.Apparently, the multi-UAV multitask assignment model in submodel can be solved by CBBA-TCC.According to (20), the maximum communication amount of qth submodel is
(36)Yq=Nq,minDq.Then, the maximum communication amount of the hierarchical task assignment model is(37)Y′=∑q=1NCYq=∑q=1NCNq,minDq≤∑q=1NCNq,minD=∑q=1NCNq,min×D=NminD=Y.Obviously, through effective model decomposition, the hierarchical task assignment model has less communication requirements than the original task assignment model. Notably, whenNC is large, there will be a great deal of submodels. Under this circumstance, Y′≪Y; thus, the required communication amount is well reduced.


## 3.2. Model Decoupling Algorithm Based on Density Clustering and Negotiation Mechanism

Last section proves that the hierarchical task assignment model effectively reduces the required communication amount. Thus, the core is to study the dimensional reduction method that can break the large-scale task assignment model with dispersed clustering targets into several nonintersection and complete submodels. To address this issue, a model decoupling algorithm based on density clustering and negotiation mechanism (MDA-DCNM) is put forward. The schematic diagram of MDA-DCNM is given in Figure2.Figure 2
MDA-DCNM.According to Figure2, MDA-DCNM consists of two procedures. Firstly, the density clustering method is applied to effectively cluster these dispersed clustering targets. Then, according to UAVs’ limited resources and different task requirements of these clustered targets, negotiation mechanism is utilized to form heterogeneous UAV teams for these clustered targets. Therefore, the large-scale task assignment problem with dispersed clustering targets can be decomposed into several nonintersection and complete small-scale task assignment problems, which effectively reduces the required computational amount and communication cost.


### 3.2.1. Density Clustering of Targets

According to the distribution of targets in the mission area, the central control station firstly introduces the density clustering method to divideNT targets into NC subclusters. Since density clustering method finds different clusters by constantly connecting high-density points in the neighborhood, there are only two parameters needed: neighborhood size MinPts and density threshold ε. Thus, different from K-mean clustering method, density clustering method can find clusters with different shapes and scales, which is suitable to divide these dispersed clustering targets into multiple different subteams [40, 41]. The algorithmic flow of density clustering method in this paper is shown in Algorithm 1.Algorithm 1: Density clustering of targets.
InputNT targets, clustered parameters MinPts,ε.OutputNC clustered target sets T1,T2,⋯,TNC.1:Ω=∅2: forj∈T do3: ifNεj≥MinPts do4:Ω=Ω∪j5: end if6: end for7:k=0,Γ=T8: whileΩ≠∅ do9:Γ~=T10:H=o, random choose o∈Ω11:Γ=Γ\o12:  whileH≠∅ do13:   ifNεh≥MinPts do, h∈H14:Δ=Nεh∩Γ15:H=H∪Δ16:Γ=Γ\Δ17:   end if18:  end while19:k=k+120:Tk=Γ~\T21:Ω=Ω\Tk22: end whileTherefore,NT targets have been clustered into NC target sets: T1,T2,⋯,TNC. The task sets in these target clusters are T¯1,T¯2,⋯,T¯NC, where q=1,2,⋯NC,T¯q=T1S,T2S,⋯,TNTQS,T1R,T2R,⋯,TNTQR.


### 3.2.2. Negotiation-Based Assignment of UAVs

Different UAVs have different limited task capacities, and different subclusters have different number of targets. According to the different requirements of tasks in different subclusters, negotiation-based assignment algorithm is proposed to allocate different UAV teams to these subclusters.AsNT targets have been clustered to NC target sets: T1,T2,⋯,TNC, the requirements for S and R tasks in these subclusters are separately defined as
(38)ReS=Re1S,Re2S,⋯,ReNCS,(39)ReR=Re1R,Re2R,⋯,ReNCR.Suppose that there areNSS-UAVs and NRR-UAVs in the multi-UAV system, the UAV sets that can perform S and R tasks are separately defined as
(40)US=U1,U2,⋯,UNS,(41)UR=U1,U2,⋯,UNR.In this paper, assume thatS-UAV has unlimited capacity, while R-UAV has limited task capacity due to its limited goods payload. Thus, the negotiation mechanism is only applied to assign R-UAVs to these subclusters. After that, S-UAVs will be correspondingly allocated based on the assignment of R-UAVs.Firstly, the limited task capacities ofR-UAVs are respectively defined as
(42)LtR=Lt1,Lt2,⋯,LtNR.The negotiation-based assignment ofR-UAVs is given in Algorithm 2.Algorithm 2: Negotiation-based assignment of R-UAVs.
InputReR,LtR.OutputNC R-UAV teams: U1R,U2R,⋯,UNCR.1:U1=∅,U2=∅,⋯,UNC=∅2: whileLtR≠∅ do3:jT=argmaxReR4:jU=argmaxLtR5:RejT=RejT−LtjU6:LtjU=07:UjTR=UjTR∩jU8: end whileThen, the S-UAV teams ofNC submodels can be proportionally assigned based the assignment results of R-UAVs. The number of S-UAVs in qthq=1,2,⋯,NC submodel is
(43)NUqS=NUqR∑p=1NCNUpR×NS.An example is given to illustrate the negotiation-based assignment of UAVs.Suppose that the whole task assignment model withNU=14 UAVs and NT=40 dispersed clustering targets can be divided into NC=3 subclusters according to density clustering method, the number of targets in NC=3 subteams is T1=8,T2=12,TNC=20. Thus, the requirements of R tasks in NC=3 subclusters are
(44)ReR=Re1R,Re2R,Re3R=8,12,20.Assume that the multi-UAV system hasNS=7S-UAVs and NR=7R-UAVs, the UAV set is
(45)U=US1,US2,⋯,US7,UR1,UR2,⋯,UR7.Besides, the limited task capacities ofNR R-UAVs are
(46)LtR=Lt1,Lt2,⋯,Lt7=9,10,6,5,7,8,4.Table1 shows the demonstration of the negotiation-based assignment of R-UAVs.Table 1
Demonstration ofR-UAV allocation based on negotiation mechanism.
ProceduresAssignment informationStep 0ReR=8,12,20,LtR=9,10,6,5,7,8,4U1R=∅,U2R=∅,U3R=∅Step 1jT=3,jU=2ReR=8,12,10,LtR=9,0,6,5,7,8,4U1R=∅,U2R=∅,U3R=U2RStep 2jT=2,jU=1ReR=8,3,10,LtR=0,0,6,5,7,8,4U1R=∅,U2R=U1R,U3R=U2RStep 3jT=3,jU=6ReR=8,3,2,LtR=0,0,6,5,7,0,4U1R=∅,U2R=U1R,U3R=U2R,U6RStep 4jT=1,jU=5ReR=1,3,2,LtR=0,0,6,5,0,0,4U1R=U5R,U2R=U1R,U3R=U2R,U6RStep 5jT=2,jU=3ReR=1,−3,2,LtR=0,0,0,5,0,0,4U1R=U5R,U2R=U1R,U3RU3R=U2R,U6RStep 6jT=3,jU=4ReR=1,−3,−3,LtR=0,0,0,0,0,0,4U1R=U5R,U2R=U1R,U3RU3R=U2R,U6R,U4RStep 7jT=1,jU=7ReR=−3,−3,−3,LtR=0,0,0,0,0,0,0U1R=U5R,U7R,U2R=U1R,U3RU3R=U2R,U6R,U4RAccording to Table1, the assignment results of NC=3R-UAV teams are
(47)U1R=U5R,U7R,(48)U2R=U1R,U3R,(49)U3R=U2R,U6R,U4R,After that, theNC UAV teams can be derived as
(50)U1=U1S,U2S,U5R,U7R,(51)U2=U3S,U4S,U1R,U3R,(52)U3=U5S,U6S,U7S,U2R,U6R,U4R.In Table1, after 7th negotiation, ReR=−3,−3,−3, which means that the residual task capacities of NC UAV teams against targets’ requirements on R tasks all equal to 3. Accordingly, the negotiation-based assignment algorithm can form corresponding UAV teams when balancing the residual task capacities of different UAV teams.Besides, there is no overlap of UAVs (targets) among different subteams. Therefore, the proposed MDR-DCNM effectively divides the large-scale task assignment model with dispersed clustering targets into multiple small-scale and nonoverlapping task assignment problem.After that, CBBA-TCC is adopted to solve these small-scale task assignment problems. It is obvious that the solutions of these nonintersection and complete small-scale task assignment problems are conflict-free. Thus, MDR-DCNM can realize conflict-free task assignment for the large-scale S&R scenarios.


## 3.2.1. Density Clustering of Targets

According to the distribution of targets in the mission area, the central control station firstly introduces the density clustering method to divideNT targets into NC subclusters. Since density clustering method finds different clusters by constantly connecting high-density points in the neighborhood, there are only two parameters needed: neighborhood size MinPts and density threshold ε. Thus, different from K-mean clustering method, density clustering method can find clusters with different shapes and scales, which is suitable to divide these dispersed clustering targets into multiple different subteams [40, 41]. The algorithmic flow of density clustering method in this paper is shown in Algorithm 1.Algorithm 1: Density clustering of targets.
InputNT targets, clustered parameters MinPts,ε.OutputNC clustered target sets T1,T2,⋯,TNC.1:Ω=∅2: forj∈T do3: ifNεj≥MinPts do4:Ω=Ω∪j5: end if6: end for7:k=0,Γ=T8: whileΩ≠∅ do9:Γ~=T10:H=o, random choose o∈Ω11:Γ=Γ\o12:  whileH≠∅ do13:   ifNεh≥MinPts do, h∈H14:Δ=Nεh∩Γ15:H=H∪Δ16:Γ=Γ\Δ17:   end if18:  end while19:k=k+120:Tk=Γ~\T21:Ω=Ω\Tk22: end whileTherefore,NT targets have been clustered into NC target sets: T1,T2,⋯,TNC. The task sets in these target clusters are T¯1,T¯2,⋯,T¯NC, where q=1,2,⋯NC,T¯q=T1S,T2S,⋯,TNTQS,T1R,T2R,⋯,TNTQR.


## 3.2.2. Negotiation-Based Assignment of UAVs

Different UAVs have different limited task capacities, and different subclusters have different number of targets. According to the different requirements of tasks in different subclusters, negotiation-based assignment algorithm is proposed to allocate different UAV teams to these subclusters.AsNT targets have been clustered to NC target sets: T1,T2,⋯,TNC, the requirements for S and R tasks in these subclusters are separately defined as
(38)ReS=Re1S,Re2S,⋯,ReNCS,(39)ReR=Re1R,Re2R,⋯,ReNCR.Suppose that there areNSS-UAVs and NRR-UAVs in the multi-UAV system, the UAV sets that can perform S and R tasks are separately defined as
(40)US=U1,U2,⋯,UNS,(41)UR=U1,U2,⋯,UNR.In this paper, assume thatS-UAV has unlimited capacity, while R-UAV has limited task capacity due to its limited goods payload. Thus, the negotiation mechanism is only applied to assign R-UAVs to these subclusters. After that, S-UAVs will be correspondingly allocated based on the assignment of R-UAVs.Firstly, the limited task capacities ofR-UAVs are respectively defined as
(42)LtR=Lt1,Lt2,⋯,LtNR.The negotiation-based assignment ofR-UAVs is given in Algorithm 2.Algorithm 2: Negotiation-based assignment of R-UAVs.
InputReR,LtR.OutputNC R-UAV teams: U1R,U2R,⋯,UNCR.1:U1=∅,U2=∅,⋯,UNC=∅2: whileLtR≠∅ do3:jT=argmaxReR4:jU=argmaxLtR5:RejT=RejT−LtjU6:LtjU=07:UjTR=UjTR∩jU8: end whileThen, the S-UAV teams ofNC submodels can be proportionally assigned based the assignment results of R-UAVs. The number of S-UAVs in qthq=1,2,⋯,NC submodel is
(43)NUqS=NUqR∑p=1NCNUpR×NS.An example is given to illustrate the negotiation-based assignment of UAVs.Suppose that the whole task assignment model withNU=14 UAVs and NT=40 dispersed clustering targets can be divided into NC=3 subclusters according to density clustering method, the number of targets in NC=3 subteams is T1=8,T2=12,TNC=20. Thus, the requirements of R tasks in NC=3 subclusters are
(44)ReR=Re1R,Re2R,Re3R=8,12,20.Assume that the multi-UAV system hasNS=7S-UAVs and NR=7R-UAVs, the UAV set is
(45)U=US1,US2,⋯,US7,UR1,UR2,⋯,UR7.Besides, the limited task capacities ofNR R-UAVs are
(46)LtR=Lt1,Lt2,⋯,Lt7=9,10,6,5,7,8,4.Table1 shows the demonstration of the negotiation-based assignment of R-UAVs.Table 1
Demonstration ofR-UAV allocation based on negotiation mechanism.
ProceduresAssignment informationStep 0ReR=8,12,20,LtR=9,10,6,5,7,8,4U1R=∅,U2R=∅,U3R=∅Step 1jT=3,jU=2ReR=8,12,10,LtR=9,0,6,5,7,8,4U1R=∅,U2R=∅,U3R=U2RStep 2jT=2,jU=1ReR=8,3,10,LtR=0,0,6,5,7,8,4U1R=∅,U2R=U1R,U3R=U2RStep 3jT=3,jU=6ReR=8,3,2,LtR=0,0,6,5,7,0,4U1R=∅,U2R=U1R,U3R=U2R,U6RStep 4jT=1,jU=5ReR=1,3,2,LtR=0,0,6,5,0,0,4U1R=U5R,U2R=U1R,U3R=U2R,U6RStep 5jT=2,jU=3ReR=1,−3,2,LtR=0,0,0,5,0,0,4U1R=U5R,U2R=U1R,U3RU3R=U2R,U6RStep 6jT=3,jU=4ReR=1,−3,−3,LtR=0,0,0,0,0,0,4U1R=U5R,U2R=U1R,U3RU3R=U2R,U6R,U4RStep 7jT=1,jU=7ReR=−3,−3,−3,LtR=0,0,0,0,0,0,0U1R=U5R,U7R,U2R=U1R,U3RU3R=U2R,U6R,U4RAccording to Table1, the assignment results of NC=3R-UAV teams are
(47)U1R=U5R,U7R,(48)U2R=U1R,U3R,(49)U3R=U2R,U6R,U4R,After that, theNC UAV teams can be derived as
(50)U1=U1S,U2S,U5R,U7R,(51)U2=U3S,U4S,U1R,U3R,(52)U3=U5S,U6S,U7S,U2R,U6R,U4R.In Table1, after 7th negotiation, ReR=−3,−3,−3, which means that the residual task capacities of NC UAV teams against targets’ requirements on R tasks all equal to 3. Accordingly, the negotiation-based assignment algorithm can form corresponding UAV teams when balancing the residual task capacities of different UAV teams.Besides, there is no overlap of UAVs (targets) among different subteams. Therefore, the proposed MDR-DCNM effectively divides the large-scale task assignment model with dispersed clustering targets into multiple small-scale and nonoverlapping task assignment problem.After that, CBBA-TCC is adopted to solve these small-scale task assignment problems. It is obvious that the solutions of these nonintersection and complete small-scale task assignment problems are conflict-free. Thus, MDR-DCNM can realize conflict-free task assignment for the large-scale S&R scenarios.


## 3.3. Cluster Head Selection Based on Multiattribute Decision

The local task assignment problem in these subclusters has been well solved. Then, the cluster head of each UAV team should send these local task assignment solutions back to central control station for further management. Apparently, the cluster head of each UAV team undertakes extracommunication burden. Besides, since CBBA-TCC depends on communications to generate consensus task assignment solution, the selection of cluster head in each UAV team affects the efficiency of local task assignment. To address this issue, a cluster head selection approach based on multiattribute decision (CHS-MAD) is put forward to choose the cluster head of each UAV team according to the overall analyses of UAVs’ four factors including the mission execution time, the number of undertaken tasks, the total score values, and the residual task capacities.Firstly, suppose that there areNUq UAVs assigned to qthq=1,2,⋯,NC submodel, where the number of S-UAVs and R-UAVs is respectively NNUqS and NNUqR, the UAV set can be defined as
(53)Uq=U1S,U2S,⋯,UNNUqSS,U1R,U2R,⋯,UNNUqRR=U1,U2,⋯,UNUq.According to the local task assignment solution inqth submodel, four attributes of NUq UAVs can be defined as
(54)tUq=t1,t2,⋯,tNUq,(55)nUq=n1,n2,⋯,nNUq,(56)cUq=c1,c2,⋯,cNUq,(57)γUq=γ1,γ2,⋯,γNUq.(54) denotes the mission execution time of NUq UAVs. If certain UAV has longer mission execution time, it means that the UAV has less unoccupied time; thus, its probability to be chosen as the cluster head is less.(55) denotes the number of UAVs' undertaken tasks. If certain UAV has larger number of undertaken tasks, it reflects that the UAV carries out more tasks; thus, its probability to be chosen as the cluster head is less.(56) denotes the total score value of UAVs. If certain UAV has bigger score value, it means that the UAV has greater roles in the sub-model; thus, its probability to be chosen as the cluster head is less.(57) denotes the residual task capacities of UAVs. If certain UAV has larger residual task capacity, it reflects that the UAV has stronger flexibility during the task execution; thus, its probability to be chosen as the cluster head is bigger.Then, DS evidence theory is adopted to form the multiattribute decision approach. DS evidence theory is a multisource fusion method with quick response and well measurement about uncertain information [42]. Multiattribute decision based on DS evidence theory can comprehensively consider the complementarity and redundancy of four attributes to select the suitable cluster head for each subteam [43]. The DS fusion equation is
(58)MUi=11−K∑∩H=Ui∏1≤f≤4mfH,where K is the conflict factor that defined as
(59)K=∑∩H=∅∏1≤f≤4mfH.The mass functionsmfH,f=1,2,3,4 respectively denote UAVs’ probabilities to be selected as the cluster-head according to four attributes in (54)–(57).
(60)m1Ui=t∧i−2∑p=1NUqt∧i−2,(61)m2Ui=n∧i−2∑p=1NUqn∧i−2,(62)m3Ui=c∧i−2∑p=1NUqc∧i−2,(63)m4Ui=γi∑p=1NUqγp,where
(64)t^i=timaxi=1,2,⋯,NUqti,(65)n^i=nimaxi=1,2,⋯,NUqni,(66)c^i=cimaxi=1,2,⋯,NUqci.Finally, the UAV with largest probability in the fusion resultMUi will be chosen as the cluster head of qth submodel.
(67)Ji=argmaxfMUf.


## 3.4. Auction-Based Task Sharing Scheme among UAV Teams

A problem occurs when a subteam is unable to perform all of its assigned tasks due to UAVs’ limited and unbalanced resources [44]. Thus, an auction-based task-sharing scheme among UAV teams (ATS-UT) is raised to allocate the unassigned tasks. In the proposed algorithm, the central control station and cluster heads of all UAV teams will participate in the auction process of the unallocated tasks to achieve the effective assignment of all tasks in the mission area and further guarantee the mission coverage of the multi-UAV system in the entire S&R scenarios. The algorithmic diagram of ATS-UT is shown in Figure 3.Figure 3
ATS-UT.In Figure3, CBBA-PR represents CBBA with partial replanning that raised in [45, 46]. CBBA-PR partially resets original task schedules to efficiently and quickly allocate the new task. Thus, CBBA-PR is adopted to solve the allocation of unassigned task in this paper.Firstly, the central control station will announce the unallocated tasks to all UAV teams once at a time. Then, cluster head of each UAV team will use CBBA-PR to calculate the score increment of the announced task and send it back to the central control station. Finally, the central control station will choose the UAV team with highest score increment to perform the announced task. After iterations of ATS-UT, all unallocated tasks can be well assigned.


## 4. Simulations

In this paper, MDA-DCNM is the main component of the hierarchical task assignment strategy, which is used to realize model decomposition. CHS-MAD is raised to achieve effective communications between the central control station and multiple UAV teams. ATS-UT in the hierarchical task assignment strategy is only applied when some tasks are not effectively assigned through MDA-DCNM. To prove the feasibility and superiority of the proposed hierarchical task assignment strategy, five simulations are conducted in various large-scale S&R scenarios.


### 4.1. Feasibility of MDA-DCNM

Suppose thatNT=40 targets randomly gather at different locations in 5km×5km mission area, NU=14 UAVs need to perform S&R mission on all targets within time window [0,200] s. The UAV set is
(68)U=U1S,U2S,⋯,U7S,U1R,U2R,⋯,U7R,where NS=7,NR=7.The simulation parameters of UAVs and tasks are separately shown in Tables2 and 3.Table 2
Simulation parameters of UAVs.
UAVsTask capacityLtiCruise speedvi (m/s)Fuel consumption ratefi (/km)Search UAVUnlimited808Rescue UAVRandom605Table 3
Simulation parameters of tasks.
TasksFixed rewardRj0Initial rewardRjValue decrement factorλjExecution duration(s)S10900.025R10900.0215The randomly distributed targets are shown in Figure4.Figure 4
NT=40 randomly distributed targets.The realization of MDA-DCNM is illustrated as follows.Firstly, the central control station uses density clustering to cluster the dispersed clustering targets in S&R mission area. Thus,NC=3 subclusters are generated. The target sets of NC=3 subclusters are
(69)T1=T1,T2,⋯,T12,(70)T2=T13,T14,⋯,T24,(71)T3=T25,T26,⋯,T40.Comparing the clustering results in (69)–(71) with target distribution in Figure 4, we can derive that the dispersed clustering targets have been properly clustered. Besides, we can see from (69) to (71) that:
(1)
The numbers of targets inNC=3 subclusters are separately T1=12, T2=12, and T3=16. Apparently, T1+T2+T3=NU, and T1∪T2∪T3=T(2)
The targets inNC=3 subclusters are nonintersection. That is, T1∩T2=∅, T1∩T3=∅, and T2∩T3=∅Thus, the targets inNC=3 subclusters satisfy the nonintersection and complete demands of the hierarchical task assignment model in (24)–(26).Then, the central control station applies negotiation mechanism to assign different UAV teams toNC=3 subclusters.Assume that the limited task capacities of R-UAVs are(72)LtR=Lt1,Lt2,⋯,Lt7=8,9,9,10,10,7,7.TheNC=3 UAV teams can be formed based on Algorithm 2.
(73)U1=U1S,U2S,U4R,U7R,(74)U2=U3S,U4S,U3R,U1R,(75)U3=U5S,U6S,U7S,U5R,U2R,U6R.Similarly, the UAVs inNC=3 subclusters satisfy the nonintersection and complete demands of the hierarchical task assignment model in (21)–(23).Therefore, MDA-DCNM decomposes theNU=14,NT=40 task assignment problem into NC=3 nonintersection and complete small-scale task assignment problems.The corresponding elements ofNC=3 subproblems are shown in Table 4, where Tq,Uqq=1,2,⋯,NC separately represents the target and UAV sets of qth submodel, ReqR represents the requirements for R tasks, LtR represents the limited capacity of R-UAVs, and γq,Chq separately represents the residual task capacities and cluster heads of NC=3 submodels.Table 4
Relevant elements ofNC=3 subproblems.
Elements1st subproblem2nd subproblem3rd subproblemTqT1,T2,⋯,T12T13,T14,⋯,T24T25,T26,⋯,T40ReqR121216UqU1S,U2S,U4R,U7RU3S,U4S,U3R,U1RU5S,U6S,U7S,U5R,U2R,U6RLtR{10,7}{9,8}{10,9,7}γq5510ChqU2SU3SU7SIn Table4, the large-scale task assignment model has been decomposed into NC=3 submodels. E.g., in the 1st submodel, UAVs U1S,U2S,U4R,U7R are assigned to perform tasks T1,T2,⋯,T12. The requirement of R tasks is T1=12; the task capacities of R-UAVs U4R,U7R are separately {10,7}. Apparently, the residual task capacities in the 1st submodel are γ1=10+7−12=5. Through the DS fusion method, U2S is selected as the cluster head of the 1st submodel.Accordingly,NC=3 submodels are established. Considering the time coupling constraints of tasks and the heterogeneity of UAVs in these subproblems, CBBA-TCC is adopted to produce effective and conflict-free task assignment solutions.Figure5 shows the task assignment results of MDA-DCNM. In Figure 5, NU=14 UAVs from the same base need to perform S&R mission on NT=40 targets. The x-axis and y-axis represent the locations of targets; the z-axis is the time. By contrast to Figure 4, the black “×” represents the locations of targets, the black dotted lines indicate the time windows of targets: [0,200] s. “Δ,◯” separately represent S and R tasks, and their corresponding z-axis values are their execution time. Blue and red segments separately represent the task performing process of S-UAVs and R-UAVs.Figure 5
Task assignment results.Figure6 shows the UAV schedules of MDA-DCNM. In Figure 6, the blue and red segments separately represent that the corresponding UAVs are performing S and R tasks, and the length of each segment indicates the execution duration of corresponding task.Figure 6
UAV schedules.We can see from Figures5 and 6 that:
(1)
Figure5 reveals that only S tasks (Δ) are assigned to S-UAVs (blue), while only R tasks (◯) are assigned to R-UAVs (red). That is, the constraint on different capabilities of UAVs is satisfied(2)
(72) shows that the limited task capacities of R-UAVs are LtR=Lt1,Lt2,⋯,Lt7=8,9,9,10,10,7,7. Figure 6 shows that for each R-UAV, the number of assigned tasks is less than its task capacity. Thus, the constraint on limited payloads of R-UAVs is satisfied(3)
Figure5 reflects that both S and R tasks of each target are effectively assigned. That is, the task completion constraint in (13) is satisfied(4)
Figure5 indicates that for each target, its R task is always performed after the completion of S task. Thus, the task precedence constraint in (14)–(16) is satisfied(5)
Figure6 directly reflects that all tasks are performed within time window [0,200] s. Thus, the time-sensitive constraint in (14)–(16) is satisfiedOverall, the proposed MDA-DCNM can produce effective and conflict-free solutions in the large-scale S&R scenarios with dispersed clustering targets.Besides, the multi-UAV system relies on communications and negotiations to produce feasible and conflict-free task assignment solution in S&R scenarios. We can derive from Figure5 that MDA-DCNM successfully decomposes the large-scale task assignment problem into several small-scale submodels, where UAVs only communication with corresponding UAVs in the same subteam to realize the assignment of tasks in corresponding submodel. Therefore, compared with direct task assignment strategy, the proposed MDA-DCNM greatly reduces the communication amount and cruise path of UAVs.


### 4.2. Different Distributions of Targets

Suppose thatNU=14,NS=7,NR=7, and NT=40 task assignment problem exists in 5km×5km mission area, and the randomly generated targets are dispersed clustering at NC=2−6 locations. Other simulation parameters are the same as Section 4.1. Based on 100 Monte Carlo simulations, the score values and convergence performance of MDA-DCNM and CBBA-TCC are respectively shown in Tables 5 and 6.Table 5
Scores of two algorithms under different target distributions.
Target distributionsAlgorithmsMDA-DCNMCBBA-TCCNC=22785.65752635.3650NC=33018.65222827.3469NC=42012.49581952.2485NC=52658.51162344.8481NC=62504.39992456.2380Table 6
Convergence performance of two algorithms under different target distributions.
Target distributionsAlgorithmsMDA-DCNMCBBA-TCCConvergence timeCommunication amountConvergence timeCommunication amountNC=21.1751 s354.7843 s40NC=30.4230 s254.8277 s47NC=40.1798 s232.7072 s36NC=50.0627 s143.8543 s42NC=60.0197 s94.4150 s40We can see from Table5 that under different target distribution situations, the proposed MDA-DCNM always produces solutions with higher score values than CBBA-TCC. Table 6 reveals that the proposed MDA-DCNM always has less convergence time and communication amount than CBBA-TCC. Therefore, compared with CBBA-TCC, the decomposition process of MDA-DCNM not only greatly reduces the cruise consumption of UAVs but also greatly reduces the required communication burden. That is, the proposed MDA-DCNM can produce feasible and conflict-free solution with higher scores and less convergence time.Besides, we can see from Table6 that for the same number of targetsNT=40, the more dispersed these targets are, the smaller these submodels are, and the less convergence time and communication amount the proposed MDA-DCNM needs. Thus, the decomposition process of the large-scale task assignment model can be strengthened by adjusting the parameters MinPts and ε of density clustering algorithm to obtain finer dimension reduction results, which can help the multi-UAV system get the task assignment solutions more quickly.


### 4.3. Different Size of Mission Area

Suppose that the randomly generatedNT=40 targets are dispersed clustering at NC=3 locations in different size of mission area, NU=14,NS=7, and NR=7 UAVs need to perform S&R mission on these targets. Based on 100 Monte Carlo simulations, the score values and convergence performance of MDA-DCNM and CBBA-TCC are respectively shown in Tables 7 and 8.Table 7
Scores of two algorithms under different mission sizes.
Size of mission areaAlgorithmsMDA-DCNMCBBA-TCC5km×5km5529.92295245.251210km×5km4917.32634513.846810km×10km4834.56324413.394020km×10km4335.35013958.501520km×20km3311.37693189.3496Table 8
Convergence performance of two algorithms under different mission sizes.
Size of mission areaAlgorithmsMDA-DCNMCBBA-TCCConvergence timeCommunication amountConvergence timeCommunication amount5km×5km0.9864 s2735.9210 s5910km×5km0.7505 s2540.3384 s5710km×10km0.6596 s2043.5121 s5920km×10km0.4255 s2128.6688 s6020km×20km0.8207 s26178.5785 s522We can see from Tables7 and 8 that under different size of mission area, the proposed MDA-DCNM always produces solutions with higher score, less convergence time, and less communication amount than CBBA-TCC.Besides, Table8 shows that the convergence time and communication amount of CBBA-TCC in 20km×20km mission area are separately 178 s and 522 times, which is not suitable for real-time task assignment requirement. The decomposition process of MDA-DCNM greatly reduces the required convergence time and communication amount to 0.8 s and 26 times, which effectively achieves the real-time requirement in S&R scenarios.


### 4.4. Different Model Scales

To further discuss the superiority of the proposed MDA-DCNM, 100 Monte Carlo simulations are conducted in different scales of mission models. The mission area is10km×10km, and targets are gathering at NC=3 locations. Tables 9 and 10 separately give the score values and convergence performance of MDA-DCNM and CBBA-TCC.Table 9
Scores of two algorithms under different model scales.
Model scalesAlgorithmsMDA-DCNMCBBA-TCCNU=10,NT=404339.11633861.5895NU=20,NT=404611.03054269.6223NU=20,NT=606427.36216167.5756NU=20,NT=808782.48907379.5571NU=30,NT=606987.24196544.5443NU=30,NT=808986.30128189.2356NU=30,NT=10010636.95599919.5550NU=40,NT=809286.56318527.9601NU=40,NT=10011108.080410466.3619Table 10
Convergence performance of two algorithms under different model scales.
Model scalesAlgorithmsMDA-DCNMCBBA-TCCConvergence timeCommunication amountConvergence timeCommunication amountNU=10,NT=400.3526 s2016.5170 s41NU=20,NT=400.9182 s2939.3825 s58NU=20,NT=603.3564 s36105.5134 s70NU=20,NT=808.5320 s42256.0116 s83NU=30,NT=605.2269 s41201.1032 s81NU=30,NT=8014.3678 s45303.2863 s90NU=30,NT=10025.5909 s51590.8205 s105NU=40,NT=8022.8850 s54467.8749 s117NU=40,NT=10036.1597 s58858.5061 s121Apparently, Tables9 and 10 show that under different S&R mission scales, the proposed MDA-DCNM always produces solutions with higher score, less convergence time, and less communication amount than CBBA-TCC.Besides, Table10 reveals that when the whole task assignment model is clustered as NC=3 sub-models, even the convergence time of MDA-DCNM cannot always meet the real-time task assignment requirement of S&R mission. E.g., when NU=40,NT=100, the average numbers of UAVs and targets in NC=3 submodels are separately 13 and 33. Under this circumstance, these submodels cannot be solved quickly. Accordingly, we can derive that further refinement of model decomposition process can increase the number of submodels, reduce the scale of submodels, and thus shorten the convergence time of MDA-DCNM. This just echoes the analyses of Table 6: the larger the whole task assignment model is decomposed (larger NC), the faster the proposed MDA-DCNM converges.


### 4.5.R-UAV Has Unbalanced Resources

The above simulations have proved the feasibility and superiority of MDA-DCNM. Under the circumstance of UAVs’ limited and unbalanced resources, a few tasks cannot be effectively allocated through their corresponding UAV teams. Thus, ATS-UT in hierarchical task assignment strategy is triggered to realize the mission coverage in the large-scale S&R scenarios.Suppose thatNT=40 targets randomly gather at NC=3 locations in 5km×5km mission area, NU=14 UAVs need to perform S&R mission on all targets within time window [0,200] s. The limited and unbalanced task capacities of R-UAVs are LtR=Lt1,Lt2,⋯,Lt7=4,7,8,6,7,6,4, and other relevant simulation parameters are the same as Section 4.1. Through the model decomposition process of MDA-DCNM, NC=3 submodels are obtained. The corresponding elements of these submodels are shown in Table 11.Table 11
NC=3 submodels with unbalanced capacities of R-UAVs.
Elements1st subproblem2nd subproblem3rd subproblemTqT1,T2,⋯,T12T13,T14,⋯,T24T25,T26,⋯,T40ReqR121216UqU1S,U2S,U4R,U5RU3S,U4S,U2R,U7RU5S,U6S,U7S,U3R,U6R,U1RLtR{6,7}{7,4}{8,6,4}γq1-12ChqU2SU3SU6SIn Table11, the large-scale task assignment model has been decomposed into NC=3 submodels.In the1st and 3rd submodels, the residual task capacities are separately γ1=6+7−12=1 and γ3=8+6+4−16=2. Obviously, the small-scale task assignment problems in the 1st and 3rd models can be handled well.In the2nd submodel, the residual task capacity is γ2=7+4−12=−1. That is, in the 2nd submodel, the task capacity of UAV team is less than the requirement for R tasks. Thus, due to limited and unbalanced task capacities of R-UAVs, the UAV team in the 2nd submodel cannot guarantee the effective assignment of all tasks in the subcluster.Under this circumstance, the task assignment results and UAV schedules of MDA-DCNM are respectively shown in Figures7 and 8.Figure 7
Task assignment results of MDA-DCNM with unbalanced capacities ofR-UAVs.Figure 8
UAV schedules of MDA-DCNM with unbalanced capacities ofR-UAVs.Similarly to Figures5 and 6, we can derive from Figures 7 and 8 that the task assignment solutions of MDA-DCNM satisfy the constraint on different capabilities of UAVs, constraint on limited payloads of R-UAVs, the task completion constraint, task precedence constraint, and time-sensitive constraint. Hence, MDA-DCNM can produce feasible and conflict-free task assignment solutions in the large-scale S&R scenarios.Table11 reflects that the residual task capacity of the 2nd submodel is γ2=−1. Obviously, due to unbalanced task capacities of R-UAVs, the R-UAVs in the 2nd submodel do not have sufficient resources to perform all corresponding R tasks.Then, in Figure7, the purple “∗” represents the unallocated target T14; the purple segment indicates its time window. Figure 7 reveals that due to the limited task capacities of R-UAVs in the 2nd submodel, the target T14 in the 2nd submodel is not assigned.After the central control station receives the feedback information from cluster headsU2S,U3S,U6S of NC=3 submodels, ATS-UT is triggered to assign the unallocated target T14 and further achieve the mission coverage of S&R scenarios.After receiving the task announcement from the central control station, the1st and 3rd UAV teams will apply CBBA-PR to assign the unallocated target T14. Based on CBBA-PR, the score increments will be sent to the central control station as the biddings for the unallocated target T14.The auction information of the1st and 3rd UAV teams are respectively shown in Figures 9 and 10.Figure 9
CBBA-PR auction information of the1st UAV team.Figure 10
CBBA-PR auction information of the3rd UAV team.Figure9 only gives the task performing information of the 1st UAV team. On the basis of its original task assignment solution in Figure 7, the 1st UAV team will apply CBBA-PR to realize the effective assignment of the unallocated target T14. Figure 9 shows that for the 1st UAV team, the score increment of T14 is 140.5928. Then, the cluster head of the 1st UAV team U2S will send the score increment 140.5928 to the central control station as its auction value for T14.Figure10 only gives the task performing information of the 3rd UAV team. Similarly, Figure 10 reveals that for the 3rd UAV team, the score increment of T14 is 261.9860. Then, the cluster head of the 3rd UAV team U3S will send the score increment 261.9860 to the central control station as its auction value for T14.Finally, as the objective of the task assignment model is to maximize the global reward when satisfying multiple constraints, the central control station will chose the3rd UAV team with higher bidding to perform the S and R tasks of the unallocated target T14.Accordingly, the unallocated targetT14 has been well assigned through ATS-UT. Hence, ATS-UT successfully guarantees the mission coverage in the large-scale S&R scenarios even UAVs has limited and unbalanced sources.Overall, MDA-DCNM can realize the feasible decomposition of the large-scale task assignment model, which availably reduces the required communication amount and computational burden of the multi-UAV system. When UAVs have limited and unbalanced sources, a few task cannot be effectively assigned. Then, ATS-UT is triggered to guarantee the efficient assignment of unallocated tasks. Therefore, the effectiveness of the proposed hierarchical task assignment strategy has been well illustrated.


## 4.1. Feasibility of MDA-DCNM

Suppose thatNT=40 targets randomly gather at different locations in 5km×5km mission area, NU=14 UAVs need to perform S&R mission on all targets within time window [0,200] s. The UAV set is
(68)U=U1S,U2S,⋯,U7S,U1R,U2R,⋯,U7R,where NS=7,NR=7.The simulation parameters of UAVs and tasks are separately shown in Tables2 and 3.Table 2
Simulation parameters of UAVs.
UAVsTask capacityLtiCruise speedvi (m/s)Fuel consumption ratefi (/km)Search UAVUnlimited808Rescue UAVRandom605Table 3
Simulation parameters of tasks.
TasksFixed rewardRj0Initial rewardRjValue decrement factorλjExecution duration(s)S10900.025R10900.0215The randomly distributed targets are shown in Figure4.Figure 4
NT=40 randomly distributed targets.The realization of MDA-DCNM is illustrated as follows.Firstly, the central control station uses density clustering to cluster the dispersed clustering targets in S&R mission area. Thus,NC=3 subclusters are generated. The target sets of NC=3 subclusters are
(69)T1=T1,T2,⋯,T12,(70)T2=T13,T14,⋯,T24,(71)T3=T25,T26,⋯,T40.Comparing the clustering results in (69)–(71) with target distribution in Figure 4, we can derive that the dispersed clustering targets have been properly clustered. Besides, we can see from (69) to (71) that:
(1)
The numbers of targets inNC=3 subclusters are separately T1=12, T2=12, and T3=16. Apparently, T1+T2+T3=NU, and T1∪T2∪T3=T(2)
The targets inNC=3 subclusters are nonintersection. That is, T1∩T2=∅, T1∩T3=∅, and T2∩T3=∅Thus, the targets inNC=3 subclusters satisfy the nonintersection and complete demands of the hierarchical task assignment model in (24)–(26).Then, the central control station applies negotiation mechanism to assign different UAV teams toNC=3 subclusters.Assume that the limited task capacities of R-UAVs are(72)LtR=Lt1,Lt2,⋯,Lt7=8,9,9,10,10,7,7.TheNC=3 UAV teams can be formed based on Algorithm 2.
(73)U1=U1S,U2S,U4R,U7R,(74)U2=U3S,U4S,U3R,U1R,(75)U3=U5S,U6S,U7S,U5R,U2R,U6R.Similarly, the UAVs inNC=3 subclusters satisfy the nonintersection and complete demands of the hierarchical task assignment model in (21)–(23).Therefore, MDA-DCNM decomposes theNU=14,NT=40 task assignment problem into NC=3 nonintersection and complete small-scale task assignment problems.The corresponding elements ofNC=3 subproblems are shown in Table 4, where Tq,Uqq=1,2,⋯,NC separately represents the target and UAV sets of qth submodel, ReqR represents the requirements for R tasks, LtR represents the limited capacity of R-UAVs, and γq,Chq separately represents the residual task capacities and cluster heads of NC=3 submodels.Table 4
Relevant elements ofNC=3 subproblems.
Elements1st subproblem2nd subproblem3rd subproblemTqT1,T2,⋯,T12T13,T14,⋯,T24T25,T26,⋯,T40ReqR121216UqU1S,U2S,U4R,U7RU3S,U4S,U3R,U1RU5S,U6S,U7S,U5R,U2R,U6RLtR{10,7}{9,8}{10,9,7}γq5510ChqU2SU3SU7SIn Table4, the large-scale task assignment model has been decomposed into NC=3 submodels. E.g., in the 1st submodel, UAVs U1S,U2S,U4R,U7R are assigned to perform tasks T1,T2,⋯,T12. The requirement of R tasks is T1=12; the task capacities of R-UAVs U4R,U7R are separately {10,7}. Apparently, the residual task capacities in the 1st submodel are γ1=10+7−12=5. Through the DS fusion method, U2S is selected as the cluster head of the 1st submodel.Accordingly,NC=3 submodels are established. Considering the time coupling constraints of tasks and the heterogeneity of UAVs in these subproblems, CBBA-TCC is adopted to produce effective and conflict-free task assignment solutions.Figure5 shows the task assignment results of MDA-DCNM. In Figure 5, NU=14 UAVs from the same base need to perform S&R mission on NT=40 targets. The x-axis and y-axis represent the locations of targets; the z-axis is the time. By contrast to Figure 4, the black “×” represents the locations of targets, the black dotted lines indicate the time windows of targets: [0,200] s. “Δ,◯” separately represent S and R tasks, and their corresponding z-axis values are their execution time. Blue and red segments separately represent the task performing process of S-UAVs and R-UAVs.Figure 5
Task assignment results.Figure6 shows the UAV schedules of MDA-DCNM. In Figure 6, the blue and red segments separately represent that the corresponding UAVs are performing S and R tasks, and the length of each segment indicates the execution duration of corresponding task.Figure 6
UAV schedules.We can see from Figures5 and 6 that:
(1)
Figure5 reveals that only S tasks (Δ) are assigned to S-UAVs (blue), while only R tasks (◯) are assigned to R-UAVs (red). That is, the constraint on different capabilities of UAVs is satisfied(2)
(72) shows that the limited task capacities of R-UAVs are LtR=Lt1,Lt2,⋯,Lt7=8,9,9,10,10,7,7. Figure 6 shows that for each R-UAV, the number of assigned tasks is less than its task capacity. Thus, the constraint on limited payloads of R-UAVs is satisfied(3)
Figure5 reflects that both S and R tasks of each target are effectively assigned. That is, the task completion constraint in (13) is satisfied(4)
Figure5 indicates that for each target, its R task is always performed after the completion of S task. Thus, the task precedence constraint in (14)–(16) is satisfied(5)
Figure6 directly reflects that all tasks are performed within time window [0,200] s. Thus, the time-sensitive constraint in (14)–(16) is satisfiedOverall, the proposed MDA-DCNM can produce effective and conflict-free solutions in the large-scale S&R scenarios with dispersed clustering targets.Besides, the multi-UAV system relies on communications and negotiations to produce feasible and conflict-free task assignment solution in S&R scenarios. We can derive from Figure5 that MDA-DCNM successfully decomposes the large-scale task assignment problem into several small-scale submodels, where UAVs only communication with corresponding UAVs in the same subteam to realize the assignment of tasks in corresponding submodel. Therefore, compared with direct task assignment strategy, the proposed MDA-DCNM greatly reduces the communication amount and cruise path of UAVs.


## 4.2. Different Distributions of Targets

Suppose thatNU=14,NS=7,NR=7, and NT=40 task assignment problem exists in 5km×5km mission area, and the randomly generated targets are dispersed clustering at NC=2−6 locations. Other simulation parameters are the same as Section 4.1. Based on 100 Monte Carlo simulations, the score values and convergence performance of MDA-DCNM and CBBA-TCC are respectively shown in Tables 5 and 6.Table 5
Scores of two algorithms under different target distributions.
Target distributionsAlgorithmsMDA-DCNMCBBA-TCCNC=22785.65752635.3650NC=33018.65222827.3469NC=42012.49581952.2485NC=52658.51162344.8481NC=62504.39992456.2380Table 6
Convergence performance of two algorithms under different target distributions.
Target distributionsAlgorithmsMDA-DCNMCBBA-TCCConvergence timeCommunication amountConvergence timeCommunication amountNC=21.1751 s354.7843 s40NC=30.4230 s254.8277 s47NC=40.1798 s232.7072 s36NC=50.0627 s143.8543 s42NC=60.0197 s94.4150 s40We can see from Table5 that under different target distribution situations, the proposed MDA-DCNM always produces solutions with higher score values than CBBA-TCC. Table 6 reveals that the proposed MDA-DCNM always has less convergence time and communication amount than CBBA-TCC. Therefore, compared with CBBA-TCC, the decomposition process of MDA-DCNM not only greatly reduces the cruise consumption of UAVs but also greatly reduces the required communication burden. That is, the proposed MDA-DCNM can produce feasible and conflict-free solution with higher scores and less convergence time.Besides, we can see from Table6 that for the same number of targetsNT=40, the more dispersed these targets are, the smaller these submodels are, and the less convergence time and communication amount the proposed MDA-DCNM needs. Thus, the decomposition process of the large-scale task assignment model can be strengthened by adjusting the parameters MinPts and ε of density clustering algorithm to obtain finer dimension reduction results, which can help the multi-UAV system get the task assignment solutions more quickly.


## 4.3. Different Size of Mission Area

Suppose that the randomly generatedNT=40 targets are dispersed clustering at NC=3 locations in different size of mission area, NU=14,NS=7, and NR=7 UAVs need to perform S&R mission on these targets. Based on 100 Monte Carlo simulations, the score values and convergence performance of MDA-DCNM and CBBA-TCC are respectively shown in Tables 7 and 8.Table 7
Scores of two algorithms under different mission sizes.
Size of mission areaAlgorithmsMDA-DCNMCBBA-TCC5km×5km5529.92295245.251210km×5km4917.32634513.846810km×10km4834.56324413.394020km×10km4335.35013958.501520km×20km3311.37693189.3496Table 8
Convergence performance of two algorithms under different mission sizes.
Size of mission areaAlgorithmsMDA-DCNMCBBA-TCCConvergence timeCommunication amountConvergence timeCommunication amount5km×5km0.9864 s2735.9210 s5910km×5km0.7505 s2540.3384 s5710km×10km0.6596 s2043.5121 s5920km×10km0.4255 s2128.6688 s6020km×20km0.8207 s26178.5785 s522We can see from Tables7 and 8 that under different size of mission area, the proposed MDA-DCNM always produces solutions with higher score, less convergence time, and less communication amount than CBBA-TCC.Besides, Table8 shows that the convergence time and communication amount of CBBA-TCC in 20km×20km mission area are separately 178 s and 522 times, which is not suitable for real-time task assignment requirement. The decomposition process of MDA-DCNM greatly reduces the required convergence time and communication amount to 0.8 s and 26 times, which effectively achieves the real-time requirement in S&R scenarios.


## 4.4. Different Model Scales

To further discuss the superiority of the proposed MDA-DCNM, 100 Monte Carlo simulations are conducted in different scales of mission models. The mission area is10km×10km, and targets are gathering at NC=3 locations. Tables 9 and 10 separately give the score values and convergence performance of MDA-DCNM and CBBA-TCC.Table 9
Scores of two algorithms under different model scales.
Model scalesAlgorithmsMDA-DCNMCBBA-TCCNU=10,NT=404339.11633861.5895NU=20,NT=404611.03054269.6223NU=20,NT=606427.36216167.5756NU=20,NT=808782.48907379.5571NU=30,NT=606987.24196544.5443NU=30,NT=808986.30128189.2356NU=30,NT=10010636.95599919.5550NU=40,NT=809286.56318527.9601NU=40,NT=10011108.080410466.3619Table 10
Convergence performance of two algorithms under different model scales.
Model scalesAlgorithmsMDA-DCNMCBBA-TCCConvergence timeCommunication amountConvergence timeCommunication amountNU=10,NT=400.3526 s2016.5170 s41NU=20,NT=400.9182 s2939.3825 s58NU=20,NT=603.3564 s36105.5134 s70NU=20,NT=808.5320 s42256.0116 s83NU=30,NT=605.2269 s41201.1032 s81NU=30,NT=8014.3678 s45303.2863 s90NU=30,NT=10025.5909 s51590.8205 s105NU=40,NT=8022.8850 s54467.8749 s117NU=40,NT=10036.1597 s58858.5061 s121Apparently, Tables9 and 10 show that under different S&R mission scales, the proposed MDA-DCNM always produces solutions with higher score, less convergence time, and less communication amount than CBBA-TCC.Besides, Table10 reveals that when the whole task assignment model is clustered as NC=3 sub-models, even the convergence time of MDA-DCNM cannot always meet the real-time task assignment requirement of S&R mission. E.g., when NU=40,NT=100, the average numbers of UAVs and targets in NC=3 submodels are separately 13 and 33. Under this circumstance, these submodels cannot be solved quickly. Accordingly, we can derive that further refinement of model decomposition process can increase the number of submodels, reduce the scale of submodels, and thus shorten the convergence time of MDA-DCNM. This just echoes the analyses of Table 6: the larger the whole task assignment model is decomposed (larger NC), the faster the proposed MDA-DCNM converges.


## 4.5.R-UAV Has Unbalanced Resources

The above simulations have proved the feasibility and superiority of MDA-DCNM. Under the circumstance of UAVs’ limited and unbalanced resources, a few tasks cannot be effectively allocated through their corresponding UAV teams. Thus, ATS-UT in hierarchical task assignment strategy is triggered to realize the mission coverage in the large-scale S&R scenarios.Suppose thatNT=40 targets randomly gather at NC=3 locations in 5km×5km mission area, NU=14 UAVs need to perform S&R mission on all targets within time window [0,200] s. The limited and unbalanced task capacities of R-UAVs are LtR=Lt1,Lt2,⋯,Lt7=4,7,8,6,7,6,4, and other relevant simulation parameters are the same as Section 4.1. Through the model decomposition process of MDA-DCNM, NC=3 submodels are obtained. The corresponding elements of these submodels are shown in Table 11.Table 11
NC=3 submodels with unbalanced capacities of R-UAVs.
Elements1st subproblem2nd subproblem3rd subproblemTqT1,T2,⋯,T12T13,T14,⋯,T24T25,T26,⋯,T40ReqR121216UqU1S,U2S,U4R,U5RU3S,U4S,U2R,U7RU5S,U6S,U7S,U3R,U6R,U1RLtR{6,7}{7,4}{8,6,4}γq1-12ChqU2SU3SU6SIn Table11, the large-scale task assignment model has been decomposed into NC=3 submodels.In the1st and 3rd submodels, the residual task capacities are separately γ1=6+7−12=1 and γ3=8+6+4−16=2. Obviously, the small-scale task assignment problems in the 1st and 3rd models can be handled well.In the2nd submodel, the residual task capacity is γ2=7+4−12=−1. That is, in the 2nd submodel, the task capacity of UAV team is less than the requirement for R tasks. Thus, due to limited and unbalanced task capacities of R-UAVs, the UAV team in the 2nd submodel cannot guarantee the effective assignment of all tasks in the subcluster.Under this circumstance, the task assignment results and UAV schedules of MDA-DCNM are respectively shown in Figures7 and 8.Figure 7
Task assignment results of MDA-DCNM with unbalanced capacities ofR-UAVs.Figure 8
UAV schedules of MDA-DCNM with unbalanced capacities ofR-UAVs.Similarly to Figures5 and 6, we can derive from Figures 7 and 8 that the task assignment solutions of MDA-DCNM satisfy the constraint on different capabilities of UAVs, constraint on limited payloads of R-UAVs, the task completion constraint, task precedence constraint, and time-sensitive constraint. Hence, MDA-DCNM can produce feasible and conflict-free task assignment solutions in the large-scale S&R scenarios.Table11 reflects that the residual task capacity of the 2nd submodel is γ2=−1. Obviously, due to unbalanced task capacities of R-UAVs, the R-UAVs in the 2nd submodel do not have sufficient resources to perform all corresponding R tasks.Then, in Figure7, the purple “∗” represents the unallocated target T14; the purple segment indicates its time window. Figure 7 reveals that due to the limited task capacities of R-UAVs in the 2nd submodel, the target T14 in the 2nd submodel is not assigned.After the central control station receives the feedback information from cluster headsU2S,U3S,U6S of NC=3 submodels, ATS-UT is triggered to assign the unallocated target T14 and further achieve the mission coverage of S&R scenarios.After receiving the task announcement from the central control station, the1st and 3rd UAV teams will apply CBBA-PR to assign the unallocated target T14. Based on CBBA-PR, the score increments will be sent to the central control station as the biddings for the unallocated target T14.The auction information of the1st and 3rd UAV teams are respectively shown in Figures 9 and 10.Figure 9
CBBA-PR auction information of the1st UAV team.Figure 10
CBBA-PR auction information of the3rd UAV team.Figure9 only gives the task performing information of the 1st UAV team. On the basis of its original task assignment solution in Figure 7, the 1st UAV team will apply CBBA-PR to realize the effective assignment of the unallocated target T14. Figure 9 shows that for the 1st UAV team, the score increment of T14 is 140.5928. Then, the cluster head of the 1st UAV team U2S will send the score increment 140.5928 to the central control station as its auction value for T14.Figure10 only gives the task performing information of the 3rd UAV team. Similarly, Figure 10 reveals that for the 3rd UAV team, the score increment of T14 is 261.9860. Then, the cluster head of the 3rd UAV team U3S will send the score increment 261.9860 to the central control station as its auction value for T14.Finally, as the objective of the task assignment model is to maximize the global reward when satisfying multiple constraints, the central control station will chose the3rd UAV team with higher bidding to perform the S and R tasks of the unallocated target T14.Accordingly, the unallocated targetT14 has been well assigned through ATS-UT. Hence, ATS-UT successfully guarantees the mission coverage in the large-scale S&R scenarios even UAVs has limited and unbalanced sources.Overall, MDA-DCNM can realize the feasible decomposition of the large-scale task assignment model, which availably reduces the required communication amount and computational burden of the multi-UAV system. When UAVs have limited and unbalanced sources, a few task cannot be effectively assigned. Then, ATS-UT is triggered to guarantee the efficient assignment of unallocated tasks. Therefore, the effectiveness of the proposed hierarchical task assignment strategy has been well illustrated.


## 5. Conclusions

To solve the multi-UAV multitask assignment problem in the large-scale S&R scenarios with dispersed clustering targets, this paper proposes a hierarchical task assignment strategy. Firstly, the model decoupling algorithm based on density clustering and negotiation mechanism is proposed to decompose the large-scale task assignment model with dispersed clustering targets into several nonintersection and complete small-scale task assignment models. The model decomposition process greatly reduces the required computational amount and communication cost. Then, a cluster head selection based on DS fusion decision is raised to select rational cluster head for each UAV team according to the overall analyses of UAVs’ four attributes including the mission execution time, the number of undertaken tasks, the total score values, and the residual task capacities. At last, considering the unallocated targets caused by UAVs’ limited and unbalanced resources, an auction-based task-sharing scheme among UAV teams is raised to achieve the effective assignment of unallocated tasks and further guarantee the mission coverage in the large-scale S&R scenarios. Simulation results comprehensively prove that under the large-scale task assignment model with dispersed clustering targets, the proposed hierarchical task assignment strategy can quickly generate effective, reliable, and conflict-free task assignment solutions that conform to multiple constraints.In the future research, we will study the application of the proposed hierarchical task assignment strategy in the urban S&R scenarios. There are many buildings, trees, and other obstacles in urban environment. Thus, the next study will focus on how to ensure the effectiveness of the hierarchical task assignment strategy under complex urban environment.



---

*Source: 7353697-2021-07-16.xml*