# A Two-Layer Task Assignment Algorithm for UAV Swarm Based on Feature Weight Clustering

Authors: Xiaowei Fu; Peng Feng; Bin Li; Xiaoguang Gao
Journal: International Journal of Aerospace Engineering
 (2019)

---

## Abstract

For the large-scale operations of unmanned aerial vehicle (UAV) swarm and the large number of UAVs, this paper proposes a two-layer task and resource assignment algorithm based on feature weight clustering. According to the numbers and types of task resources of each UAV and the distances between different UAVs, the UAV swarm is divided into multiple UAV clusters, and the large-scale allocation problem is transformed into several related small-scale problems. A two-layer task assignment algorithm based on the consensus-based bundle algorithm (CBBA) is proposed, and this algorithm uses different consensus rules between clusters and within clusters, which ensures that the UAV swarm gets a conflict-free task assignment solution in real time. The simulation results show that the algorithm can assign tasks effectively and efficiently when the number of UAVs and targets is large.


---

## Body

## 1. Introduction

UAV swarm consists of a large number of small UAVs [1], and the cooperative task and resource assignment of UAV swarm is to real-time coordinate the UAV swarm in order to achieve an overall mission objective. A mission can be divided into different tasks, and a number of specialized UAVs are then assigned to solve each task cooperatively [2–4].The CBBA algorithm is a kind of the distributed auction-based algorithms to resolve multiple agent task assignment problem [5], and it is a multiassignment decentralized auction approach with a consensus protocol that guarantees a conflict-free solution despite possible inconsistencies in situational awareness. An extension to CBBA [6] has enabled incorporation of heterogeneity in the UAV capabilities and task time windows, which significantly extends the mission characteristics that can be handled. Coupled CBBA is designed to create feasible assignments for a network of autonomous UAVs in the presence of the temporal coupling constraints [7], and temporal constraints include several specified relationships between the chosen visit times for a subset of tasks. The consensus phase of the CBBA algorithm relies on coordinated communication between all UAVs, which is achieved by propagating UAVs’ bid information through the communication links. As the number of UAVs in the network increases, this consensus approach may overflow the network bandwidth. But in these works, the communication links between all UAVs have high bandwidth, low latency, low cost, and high reliability. However, the real communication links between UAVs do not possess all of these characteristics. Asynchronous CBBA extends CBBA to account for more realistic asynchronous communication protocols by minimizing communication load while preserving the convergence properties [8], and it produces consistent task assignments using relatively little bandwidth and without requiring artificial time delays. The comparisons between global and local convergence in asynchronous consensus algorithms are discussed in [9]. Bid warped consensus-based bundle algorithm deals with the task assignment problems that global information consistency assumptions are difficult to enforce [10], and it relies only on a local best estimate of the global information state, which is referred to as local information consistency. CBBA with partial replanning (CBBA-PR) extends the CBBA algorithm to allocate new appeared tasks quickly without a full reallocation of existing tasks [11], and it enables multi-UAV team to trade-off between convergence time and increased coordination by resetting a portion of their previous allocation at every round of bidding on tasks.For the task assignment problem of the UAV swarm, the existing CBBA algorithm will need more communication times as the number of UAVs increases; moreover, each UAV of the swarm may have different capacity and number of resources, which are not considered in the existing CBBA algorithms.Although the aforementioned works have made some improvements of the CBBA algorithm, they still cannot adapt to the characteristics of large number of UAVs in the UAV swarm. The computational complexity of task assignment is still a crucial problem in the use of the UAV swarm. The hierarchical method is a feasible approach to reduce the computation cost of complex optimization problems, which divides the problem into several levels of subproblems. Each level of subproblem has its own objectives and constraints. The output of one level becomes the input of the next level. By solving the subproblems on different levels in order, the original problem can be solved. Although this approach may miss the best solution, it can produce satisfactory solutions in much less time than other methods.This paper proposes a two-layer task assignment algorithm based on feature weight clustering, which could decompose the large-scale task assignment problem of the UAV swarm effectively, and the efficiency of task assignment is greatly improved.


## 2. Task Assignment Model of the UAV Swarm

In a prior work [12], the task resource, task reward, and task assignment models are presented as follows.


### 2.1. Task Resource Model

Given a swarm ofN heterogeneous UAVs U=U1,U2,⋯,UN and a set of M targets T=T1,T2,⋯,TM, the UAV swarm is divided into two subsets U=UI,UA according to the task resource type of each UAV; UI is the set of electronic interfering UAVs and UA is the set of attack UAVs. Each UAV belongs to only one of the two subsets, and it carries n kinds of task resources. The task resource vector of the attack UAV Ui is represented by resSuiA=resSui,1A,resSui,2A,⋯,resSui,nA, where resSui,qA, q=1,⋯,n, indicates the quantity of qth type of weapons carried by UAV Ui; and the task resource vector of the electronic interfering UAV Uj is represented by resSujI=resSuj,1I,resSuj,2I,⋯,resSuj,mI, where resSuj,qI, q=1,⋯,m, indicates the quantity of qth type of electronic interfering resources carried by UAV Uj.To attack targetTj, the required type and quantity of weapons are resRejA=resRej,1A,resRej,2A,⋯,resRej,nA, where resRej,qA, q=1,⋯,n, indicates the required quantity of qth type of weapons to attack target Tj. To interfere target Tj, the required type and quantity of electronic interfering resources are resRejI=resRej,1I,resRej,2I,⋯,resRej,mI, where resRej,qI, q=1,⋯,m, indicates the required quantity of qth type of resources to interfere target Tj.To interfere and attack targetTx, the total amount of task resources carried by UAVs must meet the task requirements.
(1)∑Ui∈IAxi,kA⋅resSui,kA≥resRex,kA,∀k∈1,2,⋯,n,∑Ui∈IAxi,kI⋅resSui,kI≥resRex,kI,∀k∈1,2,⋯,n,where xi,kA and xi,kI, respectively, indicate whether the kth weapon resource or interference payload of Ui is used to the tasks on the target; resSui,kA and resSui,kI indicate the number of the kth weapon resources or interference payload of Ui, respectively.


### 2.2. Task Reward Model

Definition 1 (the initial reward of attack task).
Suppose the damage probability ofUi to one target is pi,a, the initial reward of attack task is defined as
(2)Gi,jA=Vjpi,a−Dj,where Vj and Dj are the value and threat level of target Tj.
The attack task reduces the threat level of the target; therefore, the threat level of targetTj that has been attacked is
(3)Dj∗=1−pi,aDj.Definition 2 (the initial reward of electronic interference task).
As shown in Figure1, the electronic interference task is related to the attack task, and it should be performed before attack task a certain period of time. The UAV swarm assigns an attack task to a target at first and then estimates the start time of electronic interference task according to the time of the attack task.Figure 1
Schematic diagram of electronic interference process [12].The maximum interference distanceRt is a function of Rj and the angle θ, which is
(4)Rt=fRj,θ.The reward of the electronic interference task is defined as(5)Gi,jI=0,Ra<Rt,δGi,jA,Ra≥Rt,where Rt indicates the maximum interference distance of UAV Ui and Ra represents the distance between the UAV Ui and the target Tj.


### 2.3. Task Assignment Model

The task and resource assignment model of the UAV swarm is described as(6)maxJ=∑i=1N∑j=1MXi,j⋅Ci,jpi∑i=1NXi,j⋅Lenipis.t.∑j=1MXi,j≤L,∀Ui∈UXi,jk⋅resSui,jk≤resSuik∑i=1NXi,jk⋅resSui,jk≥resRejkXi,j∈0,1,∀i,j∈U×T,where Xi,j denotes whether UAV Ui is assigned to target j. L represents the maximum number of tasks of each UAV. Vector pi∈T∪∅L represents an ordered sequence of task path of Ui. Lenipi indicates the length of the path that the UAV performs the current task sequence. The fractional function Ci,jpi represents the total task reward that is calculated as described in equations (2) and (5). Xi,jk denotes whether UAV Ui with kth resource is assigned to target j. resSui,jk indicates the number of the kth resources of Ui that is assigned to target j, and resSuik indicates the number of the kth resources of Ui. resRejk indicates the required number of the kth resources for the tasks on target j.


## 2.1. Task Resource Model

Given a swarm ofN heterogeneous UAVs U=U1,U2,⋯,UN and a set of M targets T=T1,T2,⋯,TM, the UAV swarm is divided into two subsets U=UI,UA according to the task resource type of each UAV; UI is the set of electronic interfering UAVs and UA is the set of attack UAVs. Each UAV belongs to only one of the two subsets, and it carries n kinds of task resources. The task resource vector of the attack UAV Ui is represented by resSuiA=resSui,1A,resSui,2A,⋯,resSui,nA, where resSui,qA, q=1,⋯,n, indicates the quantity of qth type of weapons carried by UAV Ui; and the task resource vector of the electronic interfering UAV Uj is represented by resSujI=resSuj,1I,resSuj,2I,⋯,resSuj,mI, where resSuj,qI, q=1,⋯,m, indicates the quantity of qth type of electronic interfering resources carried by UAV Uj.To attack targetTj, the required type and quantity of weapons are resRejA=resRej,1A,resRej,2A,⋯,resRej,nA, where resRej,qA, q=1,⋯,n, indicates the required quantity of qth type of weapons to attack target Tj. To interfere target Tj, the required type and quantity of electronic interfering resources are resRejI=resRej,1I,resRej,2I,⋯,resRej,mI, where resRej,qI, q=1,⋯,m, indicates the required quantity of qth type of resources to interfere target Tj.To interfere and attack targetTx, the total amount of task resources carried by UAVs must meet the task requirements.
(1)∑Ui∈IAxi,kA⋅resSui,kA≥resRex,kA,∀k∈1,2,⋯,n,∑Ui∈IAxi,kI⋅resSui,kI≥resRex,kI,∀k∈1,2,⋯,n,where xi,kA and xi,kI, respectively, indicate whether the kth weapon resource or interference payload of Ui is used to the tasks on the target; resSui,kA and resSui,kI indicate the number of the kth weapon resources or interference payload of Ui, respectively.


## 2.2. Task Reward Model

Definition 1 (the initial reward of attack task).
Suppose the damage probability ofUi to one target is pi,a, the initial reward of attack task is defined as
(2)Gi,jA=Vjpi,a−Dj,where Vj and Dj are the value and threat level of target Tj.
The attack task reduces the threat level of the target; therefore, the threat level of targetTj that has been attacked is
(3)Dj∗=1−pi,aDj.Definition 2 (the initial reward of electronic interference task).
As shown in Figure1, the electronic interference task is related to the attack task, and it should be performed before attack task a certain period of time. The UAV swarm assigns an attack task to a target at first and then estimates the start time of electronic interference task according to the time of the attack task.Figure 1
Schematic diagram of electronic interference process [12].The maximum interference distanceRt is a function of Rj and the angle θ, which is
(4)Rt=fRj,θ.The reward of the electronic interference task is defined as(5)Gi,jI=0,Ra<Rt,δGi,jA,Ra≥Rt,where Rt indicates the maximum interference distance of UAV Ui and Ra represents the distance between the UAV Ui and the target Tj.


## 2.3. Task Assignment Model

The task and resource assignment model of the UAV swarm is described as(6)maxJ=∑i=1N∑j=1MXi,j⋅Ci,jpi∑i=1NXi,j⋅Lenipis.t.∑j=1MXi,j≤L,∀Ui∈UXi,jk⋅resSui,jk≤resSuik∑i=1NXi,jk⋅resSui,jk≥resRejkXi,j∈0,1,∀i,j∈U×T,where Xi,j denotes whether UAV Ui is assigned to target j. L represents the maximum number of tasks of each UAV. Vector pi∈T∪∅L represents an ordered sequence of task path of Ui. Lenipi indicates the length of the path that the UAV performs the current task sequence. The fractional function Ci,jpi represents the total task reward that is calculated as described in equations (2) and (5). Xi,jk denotes whether UAV Ui with kth resource is assigned to target j. resSui,jk indicates the number of the kth resources of Ui that is assigned to target j, and resSuik indicates the number of the kth resources of Ui. resRejk indicates the required number of the kth resources for the tasks on target j.


## 3. UAV Clustering Based on Distance and Task Resources

### 3.1. Mathematical Model of Cluster Analysis

Cluster analysis is the process of partitioning a set of data objects into subsets. Each subset is a cluster, such that objects in a cluster are similar to one another yet dissimilar to objects in other clusters [13].Given a set of data pointsS=X1,X2,⋯,Xn in Rm space, the position with the smallest distance from point Xjj=1,2,⋯,n to the k positions V1,V2,⋯,Vk is called the nearest position of the point Xj. The distance measure to the nearest position is recorded as dj=min∑i=1,⋯,kdji, where dji is called as the distance measure from point Xj to position Vi. The sum of the minimum distance metrics for n points is ∑j=1ndj.According to the above description, the clustering problem can be converted into an optimization problem, which is described asInput. n data points in Rm;Output. k positions in Rm so that the sum of the minimum distance measures of n points is minimized.


### 3.2.k-Medoids Clustering Algorithm

Generally, compared tok-means clustering algorithm, k-medoids clustering algorithm showed its superiority in execution time, sensitivity towards outlier data, and reduction of noise since it employs the method of minimization of the sum of dissimilarities of datasets [14]. Although there are many enhanced k-means algorithms [15, 16], we still choose the k-medoids algorithm for clustering from the aspects of computational complexity and algorithm efficiency.The optimization objective function of thek-medoids clustering algorithm can be generally defined as follows:
(7)E=∑i=1k∑X∈CiX−Vip,where E represents the sum of the deviations between each data point in the data point set and its cluster center point; X represents the points in Rm; Vi represents the center point of cluster Ci (both X and Vi are m-dimensional); X−Vip represents the p-order metric between X and Vi, typically the square of the Euclidean distance in the distance space (p=2) is used.Thek-medoids clustering algorithm is described as [17]Input. The number of clusters k, a set of data points containing n pointsOutput. k clusters and the subset of data points they contain.Step 1.
From the data point set,k data points are randomly selected to form a current cluster center point set. Each of the k data point represents the initial center point of a cluster.Step 2.
Calculate the objective function value according to equation (10) and assign all data points to the cluster represented by the nearest center point.Step 3.
For each pointXjj=1,2,⋯,n of the data point set, the following procedure is performed. Try to replace each existing center point Vii=1,2,⋯,k with the current point Xj, and calculate the objective function value according to equation (10). Compare the objective function values of all candidate alternatives, and the center point of the cluster with the minimum value is replaced by Xj.Step 4.
Finally, thek clusters and their center points are obtained; the optimized clustering results of the data points contained therein are collected.


### 3.3. Clustering Model Based on Feature Weight

In the cluster analysis, in order to reflect the different effects of each attribute pair on forming a good structural clustering subset and to describe the difference between pointXi and point Xj, a weighted “distance” metric can be defined (Norm), i.e., [18]
(8)DXi,Xj=∑k=1mwk⋅dk2xik,xjk1/2,where the specific definition of kth attribute is determined according to its characteristics. If the kth attribute is an unordered category attribute, it is defined as
(9)dkxik,xjk=0,xik=xjk,1,xik≠xjk.If thekth attribute is an ordered attribute, it is defined as
(10)dkxik,xjk=xik−xjk.For the feature weight assignment problem, the optimal assignment of feature weight parametersW=w1,w2,⋯,wmT should be determined by using the distribution of data point sets S=X1,X2,⋯,Xn and class attribution. Feature weights must meet the following constraints:
(11)∑j=1mwj=m,0≤wj≤m,j=1,2,⋯,m.The optimization objective function of the algorithm is(12)PL,V,W=∑i=1n∑j=1k∑s=1mlij⋅ws⋅ds2xis,vjs,where L represents a hard-divided membership matrix; V represents a cluster center point set; W represents feature weight parameters. When the data point Xi belongs to a cluster with a cluster center Vj, lij=1; otherwise, lij=0.


### 3.4. UAV Clustering Based on Distance and Task Resources

To measure the similarity between UAVs, two attributes are used to build the objective function model. In addition to the distance attribute, the balance of task resource of each UAV cluster is also taken as the optimization objective. The UAV swarm hasn types of different task resources, and the UAV resource vector is expressed as
(13)resSu=resSu1,resSu2,⋯,resSun.All task resources in UAV clusterCj is described as
(14)resSuj=resSu1j,resSu2j,⋯,resSunj.Then, the balance of task resource of UAV clusterCj is evaluated by the variance of various task resources:
(15)Balance_resSuj=∑k=1nresSukj−resSuj¯n,where
(16)resSuj¯=∑k=1nresSukjn.In addition, the distance measurement of UAVs is(17)di,j=xi−xvj2+yi−yvj2+zi−zvj2,where xi,yi,zi is the position of Ui and xvj,yvj,zvj is the position of center point Vj of UAV cluster Cj.In summary, the final objective function is(18)P=w1⋅∑i=1n∑j=1kuij⋅di,j+w2⋅∑j=1kBalance_resSuj,where w1 is the feature weight of the distance metric, and w2 is the feature weight of the balance of task resource. Choosing a reasonable feature weight matrix can ensure that the task resources in the UAV cluster are relatively balanced on the basis of the smallest distance.


## 3.1. Mathematical Model of Cluster Analysis

Cluster analysis is the process of partitioning a set of data objects into subsets. Each subset is a cluster, such that objects in a cluster are similar to one another yet dissimilar to objects in other clusters [13].Given a set of data pointsS=X1,X2,⋯,Xn in Rm space, the position with the smallest distance from point Xjj=1,2,⋯,n to the k positions V1,V2,⋯,Vk is called the nearest position of the point Xj. The distance measure to the nearest position is recorded as dj=min∑i=1,⋯,kdji, where dji is called as the distance measure from point Xj to position Vi. The sum of the minimum distance metrics for n points is ∑j=1ndj.According to the above description, the clustering problem can be converted into an optimization problem, which is described asInput. n data points in Rm;Output. k positions in Rm so that the sum of the minimum distance measures of n points is minimized.


## 3.2.k-Medoids Clustering Algorithm

Generally, compared tok-means clustering algorithm, k-medoids clustering algorithm showed its superiority in execution time, sensitivity towards outlier data, and reduction of noise since it employs the method of minimization of the sum of dissimilarities of datasets [14]. Although there are many enhanced k-means algorithms [15, 16], we still choose the k-medoids algorithm for clustering from the aspects of computational complexity and algorithm efficiency.The optimization objective function of thek-medoids clustering algorithm can be generally defined as follows:
(7)E=∑i=1k∑X∈CiX−Vip,where E represents the sum of the deviations between each data point in the data point set and its cluster center point; X represents the points in Rm; Vi represents the center point of cluster Ci (both X and Vi are m-dimensional); X−Vip represents the p-order metric between X and Vi, typically the square of the Euclidean distance in the distance space (p=2) is used.Thek-medoids clustering algorithm is described as [17]Input. The number of clusters k, a set of data points containing n pointsOutput. k clusters and the subset of data points they contain.Step 1.
From the data point set,k data points are randomly selected to form a current cluster center point set. Each of the k data point represents the initial center point of a cluster.Step 2.
Calculate the objective function value according to equation (10) and assign all data points to the cluster represented by the nearest center point.Step 3.
For each pointXjj=1,2,⋯,n of the data point set, the following procedure is performed. Try to replace each existing center point Vii=1,2,⋯,k with the current point Xj, and calculate the objective function value according to equation (10). Compare the objective function values of all candidate alternatives, and the center point of the cluster with the minimum value is replaced by Xj.Step 4.
Finally, thek clusters and their center points are obtained; the optimized clustering results of the data points contained therein are collected.


## 3.3. Clustering Model Based on Feature Weight

In the cluster analysis, in order to reflect the different effects of each attribute pair on forming a good structural clustering subset and to describe the difference between pointXi and point Xj, a weighted “distance” metric can be defined (Norm), i.e., [18]
(8)DXi,Xj=∑k=1mwk⋅dk2xik,xjk1/2,where the specific definition of kth attribute is determined according to its characteristics. If the kth attribute is an unordered category attribute, it is defined as
(9)dkxik,xjk=0,xik=xjk,1,xik≠xjk.If thekth attribute is an ordered attribute, it is defined as
(10)dkxik,xjk=xik−xjk.For the feature weight assignment problem, the optimal assignment of feature weight parametersW=w1,w2,⋯,wmT should be determined by using the distribution of data point sets S=X1,X2,⋯,Xn and class attribution. Feature weights must meet the following constraints:
(11)∑j=1mwj=m,0≤wj≤m,j=1,2,⋯,m.The optimization objective function of the algorithm is(12)PL,V,W=∑i=1n∑j=1k∑s=1mlij⋅ws⋅ds2xis,vjs,where L represents a hard-divided membership matrix; V represents a cluster center point set; W represents feature weight parameters. When the data point Xi belongs to a cluster with a cluster center Vj, lij=1; otherwise, lij=0.


## 3.4. UAV Clustering Based on Distance and Task Resources

To measure the similarity between UAVs, two attributes are used to build the objective function model. In addition to the distance attribute, the balance of task resource of each UAV cluster is also taken as the optimization objective. The UAV swarm hasn types of different task resources, and the UAV resource vector is expressed as
(13)resSu=resSu1,resSu2,⋯,resSun.All task resources in UAV clusterCj is described as
(14)resSuj=resSu1j,resSu2j,⋯,resSunj.Then, the balance of task resource of UAV clusterCj is evaluated by the variance of various task resources:
(15)Balance_resSuj=∑k=1nresSukj−resSuj¯n,where
(16)resSuj¯=∑k=1nresSukjn.In addition, the distance measurement of UAVs is(17)di,j=xi−xvj2+yi−yvj2+zi−zvj2,where xi,yi,zi is the position of Ui and xvj,yvj,zvj is the position of center point Vj of UAV cluster Cj.In summary, the final objective function is(18)P=w1⋅∑i=1n∑j=1kuij⋅di,j+w2⋅∑j=1kBalance_resSuj,where w1 is the feature weight of the distance metric, and w2 is the feature weight of the balance of task resource. Choosing a reasonable feature weight matrix can ensure that the task resources in the UAV cluster are relatively balanced on the basis of the smallest distance.


## 4. Two-Layer Task Assignment Algorithm Based on Feature Weight Clustering

### 4.1. Algorithm Description

According to the objective function (equation (18)), the UAV swarm is partitioned into p UAV clusters represented by M=M1,M2,⋯,Mp. For UAV cluster Mt, Ut=Ut,1,Ut,2,⋯,Ut,n⊆U.Each UAV cluster initially assigns tasks of the target setT based on the CBBA algorithm, and Bt, Zt, and Yt represent the task bundle, the list of winning UAVs, and the list of winning scores of UAV cluster Mt, respectively. The consensus rule between UAV clusters is shown as Table 1.Table 1
The consensus rules between UAV clusters.
ClusterMk (sender) thinks zkjc is
ClusterMi (receiver) thinks zijc is
Receiver’s action (default: leave)
1
k
i
IFykj>yij, Update
2
k
Update
3
m∉i,k
IFykj>yij OR skm>sim, Update
4
∅
Update
5
i
i
Leave
6
k
Reset
7
m∉i,k
IFskm>sim, Reset
8
∅
Leave
9
m∉i,k
i
IFykj>yij AND skm>sim, Update
10
k
IFskm>sim, Update
11
Reset
12
m∉i,k
IFskm>sim, Update
13
n∉i,k,p
IFskm>sim AND skn>sin, Update
14
IFskm>sim AND ykj>yij, Update
15
IFskn>sin AND skm>sim, Reset
16
∅
IFskm>sim, Update
17
∅
i
Leave
18
k
Update
19
m∉i,k
IFskm>sim, Update
20
∅
LeaveIn Table1, zkjc and zijc represent the winning cluster that should be assigned to target Tj from the view of the sender cluster Mk and the receiver cluster Mi, respectively.According to the results of the consensus between UAV clusters, UAVs in the same cluster will negotiate to get a conflict-free task assignment solution. In this process, the successful bidders of some tasks may come from other clusters, so the consensus rules need to be modified, as shown in Table2, zkj and zij represent the winning UAV that should be assigned to target Tj from the view of the sender UAV Uk and the receiver UAV Ui, respectively.Table 2
The consensus rules between UAVs within a UAV cluster.
UAVUk (sender) thinks zkj is
UAVUi (receiver) thinks zij is
Receiver’s action (default: leave)
1
k
i
IFykj>yij, Update
2
k
Update
3
m∉i,k
IFykj>yij OR skm>sim, Update
4
Other clusters
IFykj>yij, Update
5
∅
Update
6
i
i
Leave
7
k
Reset
8
m∉i,k
IFskm>sim, Reset
9
Other clusters
Reset
10
∅
Leave
11
m∉i,k
i
IFykj>yij AND skm>sim, Update
12
k
IFskm>sim, Update
13
Reset
14
m∉i,k
IFskm>sim, Update
15
n∉i,k,p
IFskm>sim AND skn>sin, Update
17
IFskm>sim AND ykj>yij, Update
18
IFskn>sin AND skm>sim, Reset
19
Other clusters
IFskm>sim AND ykj>yij, Update
20
∅
IFskm>sim, Update
21
Other clusters
i
IFykj>yij, Update
22
k
Reset
23
m∉i,k
IFskm>sim, Update
24
Other clusters
IFskm>sim AND skn>sin, Update
25
IFskm>sim AND ykj>yij, Update
26
IFskn>sin AND skm>sim, Reset
27
∅
i
Leave
28
k
Update
29
m∉i,k
IFskm>sim, Update
30
Other clusters
Update
31
∅
Leave


### 4.2. Fault Tolerance Analysis

One of the advantages of the UAV swarm is its high fault tolerance. This algorithm can successfully assign tasks for a certain UAV that cannot communicate with others at a certain time.It is assumed that a UAVUi cannot communicate with others at a certain time. If the task assignment procedure has not been triggered, the tasks will be assigned between UAVs that can communicate with each other after the procedure triggered. The proposed algorithm does not need to know the number of UAVs prior to the procedure. If Ui has been assigned some tasks, maybe it will affect the effectiveness of the UAV swarm. The UAV swarm will redistribute the remaining tasks as needed after tasks are finished.


### 4.3. Performance Analysis

Compared with the baseline CBBA algorithm, the proposed two-layer algorithm can significantly reduce the number of communication times and the corresponding iteration round required to achieve task consensus, thus improving the computational efficiency. This performance improvement is mainly due to the communication mode in consensus process of the two-layer structure.In the consensus of the baseline CBBA algorithm, each UAV must send local task assignment information to all other UAVs while receiving task assignment information from them. Figure2 shows the communication mode of U1 in the consensus process in the baseline CBBA algorithm. U1 sends its local task assignment information to other drones in the UAV swarm and updates the local information according to the consensus rules after receiving the information from other UAVs.Figure 2
The communication mode in the consensus process in the baseline CBBA algorithm.The proposed two-layer algorithm divides the UAV swarm into a two-layer structure, which separates the consensus process into the consensus process between clusters and within each cluster, and reduces the complexity of consensus. As shown in Figure3, U1 that belongs to cluster M1 only needs to transmit the local task assignment information to the other 3 UAVs in cluster M1 to achieve local consensus within the cluster. Cluster M1 then communicates with other UAV clusters, which in turn achieves global task assignment consensus.Figure 3
The communication mode in the consensus process in the two-layer algorithm.Extending the above comparison to all UAVs among the UAV swarm, it can be seen from this comparison that the number of communication times to achieve task consensus is significantly reduced. Through the two-layer structure, the complexity of the consensus process is significantly reduced, thereby improving the computational efficiency.


## 4.1. Algorithm Description

According to the objective function (equation (18)), the UAV swarm is partitioned into p UAV clusters represented by M=M1,M2,⋯,Mp. For UAV cluster Mt, Ut=Ut,1,Ut,2,⋯,Ut,n⊆U.Each UAV cluster initially assigns tasks of the target setT based on the CBBA algorithm, and Bt, Zt, and Yt represent the task bundle, the list of winning UAVs, and the list of winning scores of UAV cluster Mt, respectively. The consensus rule between UAV clusters is shown as Table 1.Table 1
The consensus rules between UAV clusters.
ClusterMk (sender) thinks zkjc is
ClusterMi (receiver) thinks zijc is
Receiver’s action (default: leave)
1
k
i
IFykj>yij, Update
2
k
Update
3
m∉i,k
IFykj>yij OR skm>sim, Update
4
∅
Update
5
i
i
Leave
6
k
Reset
7
m∉i,k
IFskm>sim, Reset
8
∅
Leave
9
m∉i,k
i
IFykj>yij AND skm>sim, Update
10
k
IFskm>sim, Update
11
Reset
12
m∉i,k
IFskm>sim, Update
13
n∉i,k,p
IFskm>sim AND skn>sin, Update
14
IFskm>sim AND ykj>yij, Update
15
IFskn>sin AND skm>sim, Reset
16
∅
IFskm>sim, Update
17
∅
i
Leave
18
k
Update
19
m∉i,k
IFskm>sim, Update
20
∅
LeaveIn Table1, zkjc and zijc represent the winning cluster that should be assigned to target Tj from the view of the sender cluster Mk and the receiver cluster Mi, respectively.According to the results of the consensus between UAV clusters, UAVs in the same cluster will negotiate to get a conflict-free task assignment solution. In this process, the successful bidders of some tasks may come from other clusters, so the consensus rules need to be modified, as shown in Table2, zkj and zij represent the winning UAV that should be assigned to target Tj from the view of the sender UAV Uk and the receiver UAV Ui, respectively.Table 2
The consensus rules between UAVs within a UAV cluster.
UAVUk (sender) thinks zkj is
UAVUi (receiver) thinks zij is
Receiver’s action (default: leave)
1
k
i
IFykj>yij, Update
2
k
Update
3
m∉i,k
IFykj>yij OR skm>sim, Update
4
Other clusters
IFykj>yij, Update
5
∅
Update
6
i
i
Leave
7
k
Reset
8
m∉i,k
IFskm>sim, Reset
9
Other clusters
Reset
10
∅
Leave
11
m∉i,k
i
IFykj>yij AND skm>sim, Update
12
k
IFskm>sim, Update
13
Reset
14
m∉i,k
IFskm>sim, Update
15
n∉i,k,p
IFskm>sim AND skn>sin, Update
17
IFskm>sim AND ykj>yij, Update
18
IFskn>sin AND skm>sim, Reset
19
Other clusters
IFskm>sim AND ykj>yij, Update
20
∅
IFskm>sim, Update
21
Other clusters
i
IFykj>yij, Update
22
k
Reset
23
m∉i,k
IFskm>sim, Update
24
Other clusters
IFskm>sim AND skn>sin, Update
25
IFskm>sim AND ykj>yij, Update
26
IFskn>sin AND skm>sim, Reset
27
∅
i
Leave
28
k
Update
29
m∉i,k
IFskm>sim, Update
30
Other clusters
Update
31
∅
Leave


## 4.2. Fault Tolerance Analysis

One of the advantages of the UAV swarm is its high fault tolerance. This algorithm can successfully assign tasks for a certain UAV that cannot communicate with others at a certain time.It is assumed that a UAVUi cannot communicate with others at a certain time. If the task assignment procedure has not been triggered, the tasks will be assigned between UAVs that can communicate with each other after the procedure triggered. The proposed algorithm does not need to know the number of UAVs prior to the procedure. If Ui has been assigned some tasks, maybe it will affect the effectiveness of the UAV swarm. The UAV swarm will redistribute the remaining tasks as needed after tasks are finished.


## 4.3. Performance Analysis

Compared with the baseline CBBA algorithm, the proposed two-layer algorithm can significantly reduce the number of communication times and the corresponding iteration round required to achieve task consensus, thus improving the computational efficiency. This performance improvement is mainly due to the communication mode in consensus process of the two-layer structure.In the consensus of the baseline CBBA algorithm, each UAV must send local task assignment information to all other UAVs while receiving task assignment information from them. Figure2 shows the communication mode of U1 in the consensus process in the baseline CBBA algorithm. U1 sends its local task assignment information to other drones in the UAV swarm and updates the local information according to the consensus rules after receiving the information from other UAVs.Figure 2
The communication mode in the consensus process in the baseline CBBA algorithm.The proposed two-layer algorithm divides the UAV swarm into a two-layer structure, which separates the consensus process into the consensus process between clusters and within each cluster, and reduces the complexity of consensus. As shown in Figure3, U1 that belongs to cluster M1 only needs to transmit the local task assignment information to the other 3 UAVs in cluster M1 to achieve local consensus within the cluster. Cluster M1 then communicates with other UAV clusters, which in turn achieves global task assignment consensus.Figure 3
The communication mode in the consensus process in the two-layer algorithm.Extending the above comparison to all UAVs among the UAV swarm, it can be seen from this comparison that the number of communication times to achieve task consensus is significantly reduced. Through the two-layer structure, the complexity of the consensus process is significantly reduced, thereby improving the computational efficiency.


## 5. Simulation

In order to prove the validity and efficiency of the two-layer task assignment algorithm for the UAV swarm with feature weight clustering, several sets of simulation experiments were designed and compared with the CBBA algorithm in [5].In this study, the energy consumption is not considered, after the mission objective is achieved, and the operator in the ground control station will send return to base command to the swarm. We assumed that each UAV flies autonomous and can communicate information with others of the UAV swarm as necessary.


### 5.1. Algorithm Validation

Six attack UAVs are markedU1‐U6, 6 electronic interference UAVs are marked U7‐U12, and 6 targets are in a 10km∗10km rectangular area. The speed of each UAV is 50 m/s, and the maximum detection distance is 300 m. Assume that the UAV swarm is set to form four equal-sized UAV clusters.The initial positions and task resource vectors of all UAVs and targets are generated in a random manner. Each UAV has three kinds of task resources, that is, attack UAVs have three kinds of weapons, and electronic interference UAVs have three kinds of interference payloads. Correspondingly, each target’s attack task and electronic interference task also require three kinds of task resources. The initial states of the attack UAVs and the electronic interference UAVs are shown in Tables3 and 4, respectively. The initial state of the target is shown in Table 5.Table 3
The initial state of attack UAVs.
Ui
Initial positionxi,yi/m
Vector of weaponsresSuiA
U1
(3063, 6368)
(3, 0, 5)
U2
(5983, 8653)
(4, 2, 0)
U3
(6345, 2777)
(3, 1, 0)
U4
(890, 8834)
(0, 1, 3)
U5
(1498, 3374)
(3, 3, 0)
U6
(5404, 1473)
(0, 2, 3)Table 4
The initial state of electronic interference UAVs.
Ui
Initial positionxi,yi/m
Vector of interferenceresSuiI
U7
(3577, 5476)
(3, 2, 0)
U8
(3280, 2221)
(2, 0, 3)
U9
(4873, 5475)
(0, 2, 4)
U10
(8436, 5592)
(3, 4, 0)
U11
(4903, 8890)
(3, 3, 0)
U12
(6826, 8614)
(0, 1, 4)Table 5
The initial state of targets.
Tj
Initial positionxj,yj/m
Requirement for attackingresRejA
Requirement for interferingresRejI
T1
(4191, 6167)
(1, 3, 2)
(1, 1, 1)
T2
(5675, 7621)
(1, 0, 2)
(1, 1, 2)
T3
(3084, 3843)
(1, 2, 2)
(1, 2, 1)
T4
(7194, 5519)
(2, 1, 1)
(2, 1, 0)
T5
(3358, 8378)
(2, 1, 1)
(1, 1, 2)
T6
(5138, 3959)
(1, 1, 1)
(1, 2, 1)


#### 5.1.1. Feature Weight Clustering Validity Verification

If the UAV swarm is clustered according to the distance measure, the clustering results obtained are shown in Figure4. The clustering results based on the distance and task resource feature weights proposed in this paper are shown in Figure 5. In these figures, Ui denotes UAV ID, and Mi indicates the cluster ID to which the UAV belongs. The attack UAVs are denoted by a triangle, and the electronic interference UAVs are denoted by a circle. Each UAV cluster is denoted by a different color. Table 6 shows the comparison of cluster members and task resources between the two clustering results.Figure 4
The clustering result obtained by normal cluster.Figure 5
The clustering result obtained by the feature weight cluster.Table 6
The cluster member and task resource obtained by two kinds of clustering.
Mi
Normal cluster
Feature weight cluster
Attack UAVs
Weapons
EI UAVs
Interference
Attack UAVs
Weapons
EI UAVs
Interference
M1
U1,U4
(3, 1, 8)
U7,U9
(3, 4, 4)
U1,U5
(6, 3, 5)
U7,U9
(3, 4, 4)
M2
U2
(4, 2, 0)
U10,U11,U12
(6, 8, 4)
U2,U4
(4, 3, 3)
U11,U12
(3, 4, 4)
M3
U3,U5,U6
(6, 6, 3)
U8
(2, 0, 3)
U3,U6
(3, 3, 3)
U8,U10
(5, 4, 3)It can be seen from Figure4 and Table 6 that the task resources of the clusters that are partitioned according to distance are completely unbalanced. For example, the weapon resource of cluster M1 is seriously unbalanced; cluster M2 contains only one attack UAV and there is no third type of weapon resource; M3 contains only one interference UAV and there is no second type of interference payload. This unbalance will seriously affect the task resource assignment process and greatly increase the difficulty of achieving consensus distribution results.It can be seen from Figure5 and Table 6 that the clusters that are partitioned according to the feature weight clustering not only maintain the relatively close spatial distance between the UAVs among clusters but also achieve the balance of task resources. All three clusters have all types of task resources, and the number of various task resources is relatively balanced.


#### 5.1.2. Algorithm Effectiveness Verification

To verify the effectiveness of the proposed algorithm, the task and resource assignment results obtained by the basic CBBA algorithm of [5] and the two-layer task assignment algorithm proposed in this paper are compared in the same scenario and initial state (as described in Tables 3–5). Figures 6 and 7 show the task sequence of the UAV swarm obtained by the CBBA algorithm of [5] and the two-layer assignment algorithm proposed in this paper, respectively. In these figures, the horizontal axis represents the timeline, and 12 rows on the vertical axis represent the task sequence of 12 UAVs. On the time axis, different color cylinders are used to represent the time intervals of UAV’s tasks.Figure 6
The task assignment obtained by the CBBA algorithm of [5].Figure 7
The task sequence obtained by the two-layer algorithm.From the comparison of the two figures, the following can be seen. (1) The basic CBBA algorithm cannot fully utilize the resources of all the UAVs in the swarm, and the task assignment is unbalanced. For example,U1 and U9 are assigned 4 tasks, while U2 only has one task, and U12 is not assigned any task. The two-layer assignment algorithm makes full use of the resources of each UAV, and the task assignment solution is balanced.(2) Due to the unbalanced results of CBBA task allocation, the task completion time of the UAV swarm will increase correspondingly. Because the two-layer assignment algorithm can make full use of the performance and resources of each UAV, the UAV swarm can complete the task earlier. Under the scenario, the task completion time of the CBBA algorithm is 106 s, while the two-layer assignment algorithm is only 84 s.Task assignment results for the UAV swarm was shown in Table7.Table 7
The task assignment result obtained by the two-layer algorithm.
Tj
Task time
Task squad
T1
(32, 42)
U2,U4,U7,U11
T2
(5, 15)
U2,U4,U9,U12
T3
(59, 69)
U1,U2,U6,U8U12
T4
(74, 84)
U1,U3,U5,U9U10
T5
(30, 40)
U1,U9,U12
T6
(16, 26)
U1,U3,U5,U8,U10


### 5.2. Performance Analysis of the Two-Layer Task Assignment Algorithm

In order to comprehensively explore and compare the performance of the two-layer task assignment algorithm and the CBBA algorithm, this section takes the number of targets and UAVs as independent variables and compares the algorithm time, total task score, task completion rate, task completion time, and the number of communication times. The initial positions and task resource vectors for all UAVs and targets are generated in a random manner.


#### 5.2.1. Number of UAVs

In order to explore the adaptability of the algorithm to the number of UAVs, the number of targets is set to 12, and the number of UAVs in the swarm is set to 5, 10, 15, 20, and 25, respectively. Among the swarm, the number of attack UAVs and electronic interference UAVs is equal (or approximately equal). The UAV swarm is partitioned into different number of clusters, shown in Table8.Table 8
The clustering form of the two-layer algorithm.
Number of UAVs
Clustering form
5
2 UAV clusters, 2 or 3 UAVs each cluster
10
2 UAV clusters, 5 UAVs each cluster
15
3 UAV clusters, 5 UAVs each cluster
20
4 UAV clusters, 5 UAVs each cluster
25
5 UAV clusters, 5 UAVs each clusterThe statistical results of task completion rate, algorithm calculation time, and communication times are shown in Figures8–10. From the statistical results presented, the following can be seen:
(1)
When the number of UAVs is small (for example, 5 UAVs perform tasks on 12 targets), the task completion rates of the two algorithms are lower. The reason is that the resources of the UAV swarm are too insufficient to meet the need of tasks for all targets. Even in this situation, the task completion rate of the two-layer assignment algorithm is still higher than that of the CBBA algorithm. This is due to fact that the two-layer assignment algorithm can make full use of the resources of each UAV to ensure the balance of task assignment
(2)
With the increase of the number of UAVs, the calculation time of the two algorithms increases correspondingly. However, the CBBA algorithm increases exponentially, while the two-layer assignment algorithm grows slowly. The reason is that the two-layer assignment algorithm divides large-scale cooperative problems into several small-scale problems
(3)
With the increase of the number of UAVs, the communication times increase correspondingly. The two-layer assignment algorithm increases slowly due to the fact that each UAV only needs to communicate with other UAVs in the same cluster in most situations, while in the CBBA algorithm, each UAV theoretically needs to communicate with all the UAVs in the whole swarmFigure 8
The comparison of task completion rate obtained by two types of algorithm.Figure 9
The comparison of calculation time obtained by two types of algorithm.Figure 10
The comparison of communication processing times obtained by two types of algorithm.


#### 5.2.2. Number of Targets

In order to explore the adaptability of the algorithm to the number of targets, the number of targets is set to 5, 10, 15, 20, and 25, respectively. The UAV swarm consists of 12 UAVs, including 6 attack UAVs and 6 electronic interference UAVs. Four sets of simulation examples are set up, as shown in Table9. For each set of examples, the algorithm calculation time, total task score, and task completion rate are compared and analyzed.Table 9
Simulation examples.
Examples
UAV swarm task assignment algorithm
1
CBBA algorithm, 12 UAVs, no cluster
2
Two-layer algorithm, 2 UAV clusters, 6 UAVs each cluster
3
Two-layer algorithm, 3 UAV clusters, 3 UAVs each cluster
4
Two-layer algorithm, 4 UAV clusters, 3 UAVs each clusterThe statistical results of task completion rate, algorithm calculation time, and total task score for are shown in Figures11–13, respectively. From the statistical results presented, the following can be seen:
(1)
As the number of targets increases, the task completion rates of both algorithms decrease accordingly. Overall, the two-layer assignment algorithm has a higher task completion rate than the CBBA algorithm. As mentioned above, the two-layer assignment algorithm can make full use of the resources of each UAV to ensure the balance of task assignment. From the three examples of the two-layer task assignment algorithm, it can be seen that when the number of targets is not particularly large (within 20), the third case (4 UAV clusters) has the best effect; but when the number of targets increases to 25, the difference in task completion rates of the three samples is small. This is due to the fact that the number of tasks exceeds the upper limit of what the UAV swarm can accomplish
(2)
With the increase of the number of targets, the calculation time of the CBBA algorithm increases exponentially, while that of the two-layer assignment algorithm increases relatively slowly. From the three examples of the two-layer task assignment algorithm, it can be seen that when the swarm is grouped into four UAV clusters, the calculation time of the algorithm is relatively short, but the advantage is not obvious
(3)
As the number of targets increases, the total task scores of the two algorithms increase accordingly. This is due to the fact that the more the number of targets, the more tasks are assigned and the higher the total task score obtained. Overall, the total task score obtained by the two-layer assignment algorithm is smaller than the CBBA algorithm. This is due to the fact that the CBBA algorithm assigns tasks from a global perspective at the expense of longer computation time and more complex consensus processes and achieves an approximate optimal solution for the entire UAV swarm. The two-layer algorithm sacrifices some task rewards and achieves the real-time and high efficiency of task assignment when the number of targets is large. It can be seen from the three examples of the two-layer task assignment algorithm that the smaller the number of UAV clusters, the greater is the task rewardFigure 11
The comparison of total completion rate obtained by two types of algorithm.Figure 12
The comparison of calculation time obtained by two types of algorithm.Figure 13
The comparison of total task score obtained by two types of algorithm.In summary, the proposed two-layer task assignment algorithm can make full use of task resources and has better real-time performance with the sacrifice of the global task reward. The two-layer task assignment algorithm has better adaptability to the number of UAVs and targets and is more suitable for the high real-time requirements of the UAV swarm task assignment problem. Different numbers of UAV clusters have a certain impact on the performance of the two-layer task assignment algorithm. The smaller number of UAV clusters does not reflect the advantages of the two-layer structure. The larger number of clusters leads to too many iterations of intercluster consensus. It can be seen from the simulation verification that when the number of UAV clusters is approximately equal to the number of UAVs among each cluster, the best comprehensive performance can be obtained.


## 5.1. Algorithm Validation

Six attack UAVs are markedU1‐U6, 6 electronic interference UAVs are marked U7‐U12, and 6 targets are in a 10km∗10km rectangular area. The speed of each UAV is 50 m/s, and the maximum detection distance is 300 m. Assume that the UAV swarm is set to form four equal-sized UAV clusters.The initial positions and task resource vectors of all UAVs and targets are generated in a random manner. Each UAV has three kinds of task resources, that is, attack UAVs have three kinds of weapons, and electronic interference UAVs have three kinds of interference payloads. Correspondingly, each target’s attack task and electronic interference task also require three kinds of task resources. The initial states of the attack UAVs and the electronic interference UAVs are shown in Tables3 and 4, respectively. The initial state of the target is shown in Table 5.Table 3
The initial state of attack UAVs.
Ui
Initial positionxi,yi/m
Vector of weaponsresSuiA
U1
(3063, 6368)
(3, 0, 5)
U2
(5983, 8653)
(4, 2, 0)
U3
(6345, 2777)
(3, 1, 0)
U4
(890, 8834)
(0, 1, 3)
U5
(1498, 3374)
(3, 3, 0)
U6
(5404, 1473)
(0, 2, 3)Table 4
The initial state of electronic interference UAVs.
Ui
Initial positionxi,yi/m
Vector of interferenceresSuiI
U7
(3577, 5476)
(3, 2, 0)
U8
(3280, 2221)
(2, 0, 3)
U9
(4873, 5475)
(0, 2, 4)
U10
(8436, 5592)
(3, 4, 0)
U11
(4903, 8890)
(3, 3, 0)
U12
(6826, 8614)
(0, 1, 4)Table 5
The initial state of targets.
Tj
Initial positionxj,yj/m
Requirement for attackingresRejA
Requirement for interferingresRejI
T1
(4191, 6167)
(1, 3, 2)
(1, 1, 1)
T2
(5675, 7621)
(1, 0, 2)
(1, 1, 2)
T3
(3084, 3843)
(1, 2, 2)
(1, 2, 1)
T4
(7194, 5519)
(2, 1, 1)
(2, 1, 0)
T5
(3358, 8378)
(2, 1, 1)
(1, 1, 2)
T6
(5138, 3959)
(1, 1, 1)
(1, 2, 1)


### 5.1.1. Feature Weight Clustering Validity Verification

If the UAV swarm is clustered according to the distance measure, the clustering results obtained are shown in Figure4. The clustering results based on the distance and task resource feature weights proposed in this paper are shown in Figure 5. In these figures, Ui denotes UAV ID, and Mi indicates the cluster ID to which the UAV belongs. The attack UAVs are denoted by a triangle, and the electronic interference UAVs are denoted by a circle. Each UAV cluster is denoted by a different color. Table 6 shows the comparison of cluster members and task resources between the two clustering results.Figure 4
The clustering result obtained by normal cluster.Figure 5
The clustering result obtained by the feature weight cluster.Table 6
The cluster member and task resource obtained by two kinds of clustering.
Mi
Normal cluster
Feature weight cluster
Attack UAVs
Weapons
EI UAVs
Interference
Attack UAVs
Weapons
EI UAVs
Interference
M1
U1,U4
(3, 1, 8)
U7,U9
(3, 4, 4)
U1,U5
(6, 3, 5)
U7,U9
(3, 4, 4)
M2
U2
(4, 2, 0)
U10,U11,U12
(6, 8, 4)
U2,U4
(4, 3, 3)
U11,U12
(3, 4, 4)
M3
U3,U5,U6
(6, 6, 3)
U8
(2, 0, 3)
U3,U6
(3, 3, 3)
U8,U10
(5, 4, 3)It can be seen from Figure4 and Table 6 that the task resources of the clusters that are partitioned according to distance are completely unbalanced. For example, the weapon resource of cluster M1 is seriously unbalanced; cluster M2 contains only one attack UAV and there is no third type of weapon resource; M3 contains only one interference UAV and there is no second type of interference payload. This unbalance will seriously affect the task resource assignment process and greatly increase the difficulty of achieving consensus distribution results.It can be seen from Figure5 and Table 6 that the clusters that are partitioned according to the feature weight clustering not only maintain the relatively close spatial distance between the UAVs among clusters but also achieve the balance of task resources. All three clusters have all types of task resources, and the number of various task resources is relatively balanced.


### 5.1.2. Algorithm Effectiveness Verification

To verify the effectiveness of the proposed algorithm, the task and resource assignment results obtained by the basic CBBA algorithm of [5] and the two-layer task assignment algorithm proposed in this paper are compared in the same scenario and initial state (as described in Tables 3–5). Figures 6 and 7 show the task sequence of the UAV swarm obtained by the CBBA algorithm of [5] and the two-layer assignment algorithm proposed in this paper, respectively. In these figures, the horizontal axis represents the timeline, and 12 rows on the vertical axis represent the task sequence of 12 UAVs. On the time axis, different color cylinders are used to represent the time intervals of UAV’s tasks.Figure 6
The task assignment obtained by the CBBA algorithm of [5].Figure 7
The task sequence obtained by the two-layer algorithm.From the comparison of the two figures, the following can be seen. (1) The basic CBBA algorithm cannot fully utilize the resources of all the UAVs in the swarm, and the task assignment is unbalanced. For example,U1 and U9 are assigned 4 tasks, while U2 only has one task, and U12 is not assigned any task. The two-layer assignment algorithm makes full use of the resources of each UAV, and the task assignment solution is balanced.(2) Due to the unbalanced results of CBBA task allocation, the task completion time of the UAV swarm will increase correspondingly. Because the two-layer assignment algorithm can make full use of the performance and resources of each UAV, the UAV swarm can complete the task earlier. Under the scenario, the task completion time of the CBBA algorithm is 106 s, while the two-layer assignment algorithm is only 84 s.Task assignment results for the UAV swarm was shown in Table7.Table 7
The task assignment result obtained by the two-layer algorithm.
Tj
Task time
Task squad
T1
(32, 42)
U2,U4,U7,U11
T2
(5, 15)
U2,U4,U9,U12
T3
(59, 69)
U1,U2,U6,U8U12
T4
(74, 84)
U1,U3,U5,U9U10
T5
(30, 40)
U1,U9,U12
T6
(16, 26)
U1,U3,U5,U8,U10


## 5.1.1. Feature Weight Clustering Validity Verification

If the UAV swarm is clustered according to the distance measure, the clustering results obtained are shown in Figure4. The clustering results based on the distance and task resource feature weights proposed in this paper are shown in Figure 5. In these figures, Ui denotes UAV ID, and Mi indicates the cluster ID to which the UAV belongs. The attack UAVs are denoted by a triangle, and the electronic interference UAVs are denoted by a circle. Each UAV cluster is denoted by a different color. Table 6 shows the comparison of cluster members and task resources between the two clustering results.Figure 4
The clustering result obtained by normal cluster.Figure 5
The clustering result obtained by the feature weight cluster.Table 6
The cluster member and task resource obtained by two kinds of clustering.
Mi
Normal cluster
Feature weight cluster
Attack UAVs
Weapons
EI UAVs
Interference
Attack UAVs
Weapons
EI UAVs
Interference
M1
U1,U4
(3, 1, 8)
U7,U9
(3, 4, 4)
U1,U5
(6, 3, 5)
U7,U9
(3, 4, 4)
M2
U2
(4, 2, 0)
U10,U11,U12
(6, 8, 4)
U2,U4
(4, 3, 3)
U11,U12
(3, 4, 4)
M3
U3,U5,U6
(6, 6, 3)
U8
(2, 0, 3)
U3,U6
(3, 3, 3)
U8,U10
(5, 4, 3)It can be seen from Figure4 and Table 6 that the task resources of the clusters that are partitioned according to distance are completely unbalanced. For example, the weapon resource of cluster M1 is seriously unbalanced; cluster M2 contains only one attack UAV and there is no third type of weapon resource; M3 contains only one interference UAV and there is no second type of interference payload. This unbalance will seriously affect the task resource assignment process and greatly increase the difficulty of achieving consensus distribution results.It can be seen from Figure5 and Table 6 that the clusters that are partitioned according to the feature weight clustering not only maintain the relatively close spatial distance between the UAVs among clusters but also achieve the balance of task resources. All three clusters have all types of task resources, and the number of various task resources is relatively balanced.


## 5.1.2. Algorithm Effectiveness Verification

To verify the effectiveness of the proposed algorithm, the task and resource assignment results obtained by the basic CBBA algorithm of [5] and the two-layer task assignment algorithm proposed in this paper are compared in the same scenario and initial state (as described in Tables 3–5). Figures 6 and 7 show the task sequence of the UAV swarm obtained by the CBBA algorithm of [5] and the two-layer assignment algorithm proposed in this paper, respectively. In these figures, the horizontal axis represents the timeline, and 12 rows on the vertical axis represent the task sequence of 12 UAVs. On the time axis, different color cylinders are used to represent the time intervals of UAV’s tasks.Figure 6
The task assignment obtained by the CBBA algorithm of [5].Figure 7
The task sequence obtained by the two-layer algorithm.From the comparison of the two figures, the following can be seen. (1) The basic CBBA algorithm cannot fully utilize the resources of all the UAVs in the swarm, and the task assignment is unbalanced. For example,U1 and U9 are assigned 4 tasks, while U2 only has one task, and U12 is not assigned any task. The two-layer assignment algorithm makes full use of the resources of each UAV, and the task assignment solution is balanced.(2) Due to the unbalanced results of CBBA task allocation, the task completion time of the UAV swarm will increase correspondingly. Because the two-layer assignment algorithm can make full use of the performance and resources of each UAV, the UAV swarm can complete the task earlier. Under the scenario, the task completion time of the CBBA algorithm is 106 s, while the two-layer assignment algorithm is only 84 s.Task assignment results for the UAV swarm was shown in Table7.Table 7
The task assignment result obtained by the two-layer algorithm.
Tj
Task time
Task squad
T1
(32, 42)
U2,U4,U7,U11
T2
(5, 15)
U2,U4,U9,U12
T3
(59, 69)
U1,U2,U6,U8U12
T4
(74, 84)
U1,U3,U5,U9U10
T5
(30, 40)
U1,U9,U12
T6
(16, 26)
U1,U3,U5,U8,U10


## 5.2. Performance Analysis of the Two-Layer Task Assignment Algorithm

In order to comprehensively explore and compare the performance of the two-layer task assignment algorithm and the CBBA algorithm, this section takes the number of targets and UAVs as independent variables and compares the algorithm time, total task score, task completion rate, task completion time, and the number of communication times. The initial positions and task resource vectors for all UAVs and targets are generated in a random manner.


### 5.2.1. Number of UAVs

In order to explore the adaptability of the algorithm to the number of UAVs, the number of targets is set to 12, and the number of UAVs in the swarm is set to 5, 10, 15, 20, and 25, respectively. Among the swarm, the number of attack UAVs and electronic interference UAVs is equal (or approximately equal). The UAV swarm is partitioned into different number of clusters, shown in Table8.Table 8
The clustering form of the two-layer algorithm.
Number of UAVs
Clustering form
5
2 UAV clusters, 2 or 3 UAVs each cluster
10
2 UAV clusters, 5 UAVs each cluster
15
3 UAV clusters, 5 UAVs each cluster
20
4 UAV clusters, 5 UAVs each cluster
25
5 UAV clusters, 5 UAVs each clusterThe statistical results of task completion rate, algorithm calculation time, and communication times are shown in Figures8–10. From the statistical results presented, the following can be seen:
(1)
When the number of UAVs is small (for example, 5 UAVs perform tasks on 12 targets), the task completion rates of the two algorithms are lower. The reason is that the resources of the UAV swarm are too insufficient to meet the need of tasks for all targets. Even in this situation, the task completion rate of the two-layer assignment algorithm is still higher than that of the CBBA algorithm. This is due to fact that the two-layer assignment algorithm can make full use of the resources of each UAV to ensure the balance of task assignment
(2)
With the increase of the number of UAVs, the calculation time of the two algorithms increases correspondingly. However, the CBBA algorithm increases exponentially, while the two-layer assignment algorithm grows slowly. The reason is that the two-layer assignment algorithm divides large-scale cooperative problems into several small-scale problems
(3)
With the increase of the number of UAVs, the communication times increase correspondingly. The two-layer assignment algorithm increases slowly due to the fact that each UAV only needs to communicate with other UAVs in the same cluster in most situations, while in the CBBA algorithm, each UAV theoretically needs to communicate with all the UAVs in the whole swarmFigure 8
The comparison of task completion rate obtained by two types of algorithm.Figure 9
The comparison of calculation time obtained by two types of algorithm.Figure 10
The comparison of communication processing times obtained by two types of algorithm.


### 5.2.2. Number of Targets

In order to explore the adaptability of the algorithm to the number of targets, the number of targets is set to 5, 10, 15, 20, and 25, respectively. The UAV swarm consists of 12 UAVs, including 6 attack UAVs and 6 electronic interference UAVs. Four sets of simulation examples are set up, as shown in Table9. For each set of examples, the algorithm calculation time, total task score, and task completion rate are compared and analyzed.Table 9
Simulation examples.
Examples
UAV swarm task assignment algorithm
1
CBBA algorithm, 12 UAVs, no cluster
2
Two-layer algorithm, 2 UAV clusters, 6 UAVs each cluster
3
Two-layer algorithm, 3 UAV clusters, 3 UAVs each cluster
4
Two-layer algorithm, 4 UAV clusters, 3 UAVs each clusterThe statistical results of task completion rate, algorithm calculation time, and total task score for are shown in Figures11–13, respectively. From the statistical results presented, the following can be seen:
(1)
As the number of targets increases, the task completion rates of both algorithms decrease accordingly. Overall, the two-layer assignment algorithm has a higher task completion rate than the CBBA algorithm. As mentioned above, the two-layer assignment algorithm can make full use of the resources of each UAV to ensure the balance of task assignment. From the three examples of the two-layer task assignment algorithm, it can be seen that when the number of targets is not particularly large (within 20), the third case (4 UAV clusters) has the best effect; but when the number of targets increases to 25, the difference in task completion rates of the three samples is small. This is due to the fact that the number of tasks exceeds the upper limit of what the UAV swarm can accomplish
(2)
With the increase of the number of targets, the calculation time of the CBBA algorithm increases exponentially, while that of the two-layer assignment algorithm increases relatively slowly. From the three examples of the two-layer task assignment algorithm, it can be seen that when the swarm is grouped into four UAV clusters, the calculation time of the algorithm is relatively short, but the advantage is not obvious
(3)
As the number of targets increases, the total task scores of the two algorithms increase accordingly. This is due to the fact that the more the number of targets, the more tasks are assigned and the higher the total task score obtained. Overall, the total task score obtained by the two-layer assignment algorithm is smaller than the CBBA algorithm. This is due to the fact that the CBBA algorithm assigns tasks from a global perspective at the expense of longer computation time and more complex consensus processes and achieves an approximate optimal solution for the entire UAV swarm. The two-layer algorithm sacrifices some task rewards and achieves the real-time and high efficiency of task assignment when the number of targets is large. It can be seen from the three examples of the two-layer task assignment algorithm that the smaller the number of UAV clusters, the greater is the task rewardFigure 11
The comparison of total completion rate obtained by two types of algorithm.Figure 12
The comparison of calculation time obtained by two types of algorithm.Figure 13
The comparison of total task score obtained by two types of algorithm.In summary, the proposed two-layer task assignment algorithm can make full use of task resources and has better real-time performance with the sacrifice of the global task reward. The two-layer task assignment algorithm has better adaptability to the number of UAVs and targets and is more suitable for the high real-time requirements of the UAV swarm task assignment problem. Different numbers of UAV clusters have a certain impact on the performance of the two-layer task assignment algorithm. The smaller number of UAV clusters does not reflect the advantages of the two-layer structure. The larger number of clusters leads to too many iterations of intercluster consensus. It can be seen from the simulation verification that when the number of UAV clusters is approximately equal to the number of UAVs among each cluster, the best comprehensive performance can be obtained.


## 5.2.1. Number of UAVs

In order to explore the adaptability of the algorithm to the number of UAVs, the number of targets is set to 12, and the number of UAVs in the swarm is set to 5, 10, 15, 20, and 25, respectively. Among the swarm, the number of attack UAVs and electronic interference UAVs is equal (or approximately equal). The UAV swarm is partitioned into different number of clusters, shown in Table8.Table 8
The clustering form of the two-layer algorithm.
Number of UAVs
Clustering form
5
2 UAV clusters, 2 or 3 UAVs each cluster
10
2 UAV clusters, 5 UAVs each cluster
15
3 UAV clusters, 5 UAVs each cluster
20
4 UAV clusters, 5 UAVs each cluster
25
5 UAV clusters, 5 UAVs each clusterThe statistical results of task completion rate, algorithm calculation time, and communication times are shown in Figures8–10. From the statistical results presented, the following can be seen:
(1)
When the number of UAVs is small (for example, 5 UAVs perform tasks on 12 targets), the task completion rates of the two algorithms are lower. The reason is that the resources of the UAV swarm are too insufficient to meet the need of tasks for all targets. Even in this situation, the task completion rate of the two-layer assignment algorithm is still higher than that of the CBBA algorithm. This is due to fact that the two-layer assignment algorithm can make full use of the resources of each UAV to ensure the balance of task assignment
(2)
With the increase of the number of UAVs, the calculation time of the two algorithms increases correspondingly. However, the CBBA algorithm increases exponentially, while the two-layer assignment algorithm grows slowly. The reason is that the two-layer assignment algorithm divides large-scale cooperative problems into several small-scale problems
(3)
With the increase of the number of UAVs, the communication times increase correspondingly. The two-layer assignment algorithm increases slowly due to the fact that each UAV only needs to communicate with other UAVs in the same cluster in most situations, while in the CBBA algorithm, each UAV theoretically needs to communicate with all the UAVs in the whole swarmFigure 8
The comparison of task completion rate obtained by two types of algorithm.Figure 9
The comparison of calculation time obtained by two types of algorithm.Figure 10
The comparison of communication processing times obtained by two types of algorithm.


## 5.2.2. Number of Targets

In order to explore the adaptability of the algorithm to the number of targets, the number of targets is set to 5, 10, 15, 20, and 25, respectively. The UAV swarm consists of 12 UAVs, including 6 attack UAVs and 6 electronic interference UAVs. Four sets of simulation examples are set up, as shown in Table9. For each set of examples, the algorithm calculation time, total task score, and task completion rate are compared and analyzed.Table 9
Simulation examples.
Examples
UAV swarm task assignment algorithm
1
CBBA algorithm, 12 UAVs, no cluster
2
Two-layer algorithm, 2 UAV clusters, 6 UAVs each cluster
3
Two-layer algorithm, 3 UAV clusters, 3 UAVs each cluster
4
Two-layer algorithm, 4 UAV clusters, 3 UAVs each clusterThe statistical results of task completion rate, algorithm calculation time, and total task score for are shown in Figures11–13, respectively. From the statistical results presented, the following can be seen:
(1)
As the number of targets increases, the task completion rates of both algorithms decrease accordingly. Overall, the two-layer assignment algorithm has a higher task completion rate than the CBBA algorithm. As mentioned above, the two-layer assignment algorithm can make full use of the resources of each UAV to ensure the balance of task assignment. From the three examples of the two-layer task assignment algorithm, it can be seen that when the number of targets is not particularly large (within 20), the third case (4 UAV clusters) has the best effect; but when the number of targets increases to 25, the difference in task completion rates of the three samples is small. This is due to the fact that the number of tasks exceeds the upper limit of what the UAV swarm can accomplish
(2)
With the increase of the number of targets, the calculation time of the CBBA algorithm increases exponentially, while that of the two-layer assignment algorithm increases relatively slowly. From the three examples of the two-layer task assignment algorithm, it can be seen that when the swarm is grouped into four UAV clusters, the calculation time of the algorithm is relatively short, but the advantage is not obvious
(3)
As the number of targets increases, the total task scores of the two algorithms increase accordingly. This is due to the fact that the more the number of targets, the more tasks are assigned and the higher the total task score obtained. Overall, the total task score obtained by the two-layer assignment algorithm is smaller than the CBBA algorithm. This is due to the fact that the CBBA algorithm assigns tasks from a global perspective at the expense of longer computation time and more complex consensus processes and achieves an approximate optimal solution for the entire UAV swarm. The two-layer algorithm sacrifices some task rewards and achieves the real-time and high efficiency of task assignment when the number of targets is large. It can be seen from the three examples of the two-layer task assignment algorithm that the smaller the number of UAV clusters, the greater is the task rewardFigure 11
The comparison of total completion rate obtained by two types of algorithm.Figure 12
The comparison of calculation time obtained by two types of algorithm.Figure 13
The comparison of total task score obtained by two types of algorithm.In summary, the proposed two-layer task assignment algorithm can make full use of task resources and has better real-time performance with the sacrifice of the global task reward. The two-layer task assignment algorithm has better adaptability to the number of UAVs and targets and is more suitable for the high real-time requirements of the UAV swarm task assignment problem. Different numbers of UAV clusters have a certain impact on the performance of the two-layer task assignment algorithm. The smaller number of UAV clusters does not reflect the advantages of the two-layer structure. The larger number of clusters leads to too many iterations of intercluster consensus. It can be seen from the simulation verification that when the number of UAV clusters is approximately equal to the number of UAVs among each cluster, the best comprehensive performance can be obtained.


## 6. Conclusion

In this paper, the feature weight clustering algorithm is applied to UAV swarm clustering, and a two-layer task assignment algorithm based on the basic CBBA algorithm is proposed. The feature weight clustering algorithm can make the two-layer task assignment algorithm more effectively. The algorithm uses different consistency rules between clusters and within clusters and can achieve task assignment consensus quickly and efficiently. The simulation results show that compared with the basic CBBA algorithm, the proposed algorithm can assign tasks effectively in real time when the number of UAVs and targets is large.



---

*Source: 3504248-2019-11-26.xml*