# Real-Time Task Allocation of Heterogeneous Unmanned Aerial Vehicles for Search and Prosecute Mission

Authors: Xiangping Bryce Zhai; Li Li; Xuedong Zhao; Yunlong Zhao; Kai Liu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

In recent years, the Internet of Things (IoT) has developed rapidly after the era of computers and smart phones, which is expected to be applied to cities to improve the quality of life and realize the intelligence of smart cities. In particular, with the outbreak of coronavirus disease 2019 (COVID-19) last year, in order to reduce contact, some IoT devices, such as robots, unmanned aerial vehicles (UAVs), and unmanned vehicles, have played a great role in temperature monitoring, goods delivery, and so on. In this paper, we study the real-time task allocation problem of heterogeneous UAVs searching and delivering goods in the city. Considering the resource requirement of task and resource constraints of the UAV, when the resource of a single UAV cannot meet the requirement of the task, we propose a method of forming a UAV coalition based on contract net protocol. We analyze the coalition formation problem from two aspects: mission completion time and UAV’s energy consumption. Firstly, the mathematical model is established according to the optimization objective and condition constraints. Then, according to the established mathematical model, different coalition formation algorithms are proposed. To minimize the mission completion time, we propose a two-stage coalition formation algorithm. Aiming at minimizing the UAV’s energy consumption, it is transformed into a zero-one integer programming problem, which can be solved by the existing solver. Then, considering both mission completion time and energy consumption, we propose a coalition formation algorithm based on a resource tree. Finally, we design some simulation experiments and compare with the task allocation algorithm based on resource welfare. The simulation results show that our proposed algorithms are feasible and effective.


---

## Body

## 1. Introduction

We are stepping into the era of IoT from the information age with computers and smart phones. In particular, with the development of the fifth-generation (5G) technology, 5G network not only brings us faster network speed, more importantly, but it also promotes the faster arrival of the IoT era and lays the foundation for the development of IoT applications [1–5], such as smart home, smart agriculture, and smart city. Wearable equipments, smart cars, and UAVs are also members of the extended family in the next generation of wireless networks. Among them, UAVs have attracted more and more attention due to its own advantages such as low cost, strong maneuverability, and no risk of casualties. It can be used for surveillance and reconnaissance [6], communication relay [7], and detection and localization [8]. During the COVID-19 epidemic, in order to reduce contact and ease the pressure of material transportation, Shunfeng UAV was used to transport medical and epidemic prevention materials, such as protective clothing, gloves, and masks. Due to the increasingly complex mission environment and the increasing difficulty of the mission, using a single UAV to perform the mission has low efficiency and poor robustness. Therefore, multiple UAVs cooperative mission execution has become a main way of applying the UAV [9, 10].In the multi-UAVs cooperative search and prosecute mission, a key problem is the mission planning of multiple UAVs, that is, to allocate task and plan path for multiple UAVs under multiple constraints, so as to maximize the system efficiency [11]. According to the hierarchical control method [12], this problem can be divided into two subproblems: task allocation and path planning, but these two subproblems are coupled with each other [13]. To get the task allocation scheme, it is necessary to obtain the path cost of each UAV, and the accurate path cost depends on the result of task allocation [14]. Task allocation is the basis of mission planning, and it will affect the quality of mission completion.At present, some scholars at home and abroad have done a lot of research on the problem of multi-UAVs task allocation. Gerkey et al. [15] categorized multiagents task allocation along with three scenarios: (1) each agent can execute only one task at a time or multiple tasks simultaneously, (2) each task requires multiple agents or only one agent to prosecute it, and (3) only the current allocation or both the current and future allocation are considered. In this paper, our problem belongs to the multiagents-multitasks instantaneous assignment problem, because the UAV can perform target search and prosecute simultaneously, and the target execution may require multiple UAVs. There also have been lots of algorithms to solve the multi-UAVs task allocation problem, which can be divided into two types: centralized and distributed. The centralized algorithm is that a control center is responsible for collecting mission information, performing calculation, and obtaining an appropriate task allocation scheme. The UAVs act on orders, without any independent decision-making. The advantage of a centralized algorithm is that it can guarantee better global optimality, but if some unexpected situations are encountered during task execution, the task may fail, such as integer linear programming algorithm, graph theory, genetic algorithm [16], and particle swarm optimization algorithm [17]. Compared with centralized task allocation, the distributed algorithm is more flexible. Its decision-maker is not a control center, but the UAV itself. Multiple UAVs together form an intelligent body, which can communicate with each other. Each UAV can perform independent calculation, autonomous analysis, and decision-making, such as auction algorithm [18], consensus theory, and contract network algorithm [19].Most of the work cited above have some common assumptions: (1) the UAVs are homogeneous and have sufficient resource, (2) the requirement and location of targets are all known beforehand, and (3) each task can be fulfilled by a single UAV. However, in the real mission environment, these assumptions may not be satisfied. For example, due to the limitation of technology and its size, the type and amount of resources that UAV can carry are limited. Due to the weather or equipment limitation, we cannot obtain target information in advance through some means such as radar or satellite. The execution of the target may require multiple UAVs at the same time, and it happens that a single UAV has insufficient resources to prosecute target. Therefore, in this paper, we study the real-time task allocation problem of heterogeneous UAVs with limited resources. We analyze it from two aspects: mission completion time and energy consumption, and propose a task allocation algorithm using contract network algorithm and resource tree. The main contributions of this paper are summarized as follows:(1)
We introduce a theoretical model for the propulsion energy consumption of fixed-wing UAVs. Then, two special energy consumption models are derived, namely, uniform linear motion and uniform circular motion. Through this model, we can accurately calculate the energy consumption of UAV to prosecute the target, instead of using Euclidean distance to represent the cost. Even if the task distance is the same, if the UAV heading angle is different, the energy consumption to complete the task may be different(2)
Considering the turning constraint of the UAV, we introduce the Dubins curve to plan the flight path for the UAV. Combined with the derived UAV energy consumption model, we can calculate the mission time and energy consumption, which is close to the real flight environment(3)
We analyze the task allocation problem from two aspects of mission time and energy consumption and establish mathematical models under different objectives. For minimizing mission time, we propose a two-stage task allocation algorithm. We transform the task allocation problem into zero-one integer programming to minimize energy consumption. Considering both, we use the linear weighted sum method to transform it into a single objective optimization problem and propose a solution algorithm using a resource treeThe rest of the paper is organized as follows. Section2 describes the related works of online task allocation. Section 3 introduces the problem formulation. In Section 4, Dubins curve is presented, and the UAV energy consumption model is derived. Section 5 describes the coalition formation algorithm. Simulation results are shown in Section 6. Lastly, we conclude the paper in Section 7.


## 2. Related Works

In this paper, we consider the task allocation problem of heterogeneous UAVs online cooperative target search and prosecute. In our scenario, UAVs are heterogeneous, carrying different types and quantities of material resources which will be depleted with use. The targets are of various types, and each target requires multiple types and amounts of material resource. When the UAV detects a target, a single UAV may have insufficient resources to distribute. At this time, it is necessary to form a subteam of UAVs, which is also called the coalition formation game [20]. This subteam is called a coalition, and each UAV in the coalition is called a coalition member. The UAV that detects the target is regarded as a coalition leader.The coalition formation problem is an NP-hard combinatorial optimization problem, and it is computationally intensive. Because the UAVs are always moving, the algorithm needs to have low computational complexity and give a feasible coalition formation result in a short time. Manathara et al. [21] proposed a distributed polynomial time coalition formation algorithm (PTCFA). The algorithm first sorts the candidate UAVs according to their time to reach the target, selects the minimum time coalition, and then removes the unnecessary members in turn. Sujit et al. [22] considered the influence of time-varying communication network on the formation process of UAV coalition. Zhu et al. [23] considered the influence of communication constraints and built a multinode dynamic network model for modern aerial combat based on the concept of “time to live” (TTL) to identify the potential coalition members in a dynamic network and realized coalition formation using the improved PSO algorithm. When multiple UAVs perform a search and attack mission, the search and attack tasks are coupled, and their strategies jointly determine the performance of the mission. Therefore, for a given task allocation strategy, it is necessary to design an effective search strategy. George et al. [24] proposed three different search strategies: random search strategy, lanes-based search strategy, and grid-based search strategy. Kim et al. [25], inspired by the concept of social welfare in economics, proposed a distributed coalition formation algorithm based on resource welfare, which realized a balanced resource consumption among UAV. Ma et al. [26] proposed an improved multiobjective genetic algorithm (VC-NSGA-II) to form the task coalition by adding validity check and correction rules and used clustering algorithm and VC-NSGA-II algorithm to solve the coalition problem with large task volume. However, the objective function in the above-cited literature only considers the maximum target profit and does not consider UAV’s cost, which usually leads to a large number of UAVs in the coalition, thus increasing the price of our UAV group. Yan et al. [27] considered both the target benefit and UAV’s cost in the system function and proposed a distributed particle swarm optimization algorithm to plan flyable and safe Pythagorean hodograph curve trajectories for UAVs to achieve simultaneous arrival. However, they used path length as the UAV’s cost and did not establish an accurate fuel consumption model of UAV.If a UAV coalition is assigned to distribute medical materials, they should reach the target at the same time, thus reducing the waiting time of the staff. Currently, for the simultaneous arrival problem, there are two main ways to solve it. The first method is to plan the path for each UAV and, then, achieve simultaneous arrival by adjusting the speed [28]. This method is easy to cause speed saturation. The second method is to plan an equal length flight path for each UAV, and each UAV flies at the same speed, such as directly planning an equal length flight path [29], short flight path, and maneuver [30]. In this paper, we use the second method to achieve simultaneous arrival.In this paper, we study the task allocation problem of heterogeneous UAVs cooperative real-time target search and material distribution. Considering the UAV resource constraints and target resource requirements, when the resource of a single UAV cannot meet the target requirements, we use a way of forming a UAV coalition to complete material transportation. Then, for the coalition formation problem, we study it from three aspects: minimizing mission completion time, minimizing UAV energy consumption, and minimizing mission completion time and UAV energy consumption. In order to accurately calculate the UAV energy consumption, we derive the energy consumption model of the fixed-wing UAV based on the aerodynamic theory. To minimize the mission completion time, we propose a two-stage coalition formation method. For the goal of minimizing UAV energy consumption, we express the coalition formation problem as a zero-one integer programming problem and, then, use the solver to solve it. Then, considering both the mission completion time and UAV energy consumption, we use the linear weighted sum method to transform it into a single objective optimization problem and solve it using a resource tree.


## 3. System Model

Consider a search and prosecute mission in an unknown environment, forN heterogeneous fixed-wing UAVs carrying a variety of limited material resources, such as masks, protective clothing, and thermometers. The requirement and location of all targets are unknown beforehand. The UAVs first perform the target search task. When the target is found, according to the target’s resource requirements, a suitable UAV coalition is assigned to distribute the required materials as shown in Figure 1. To simplify the problem, we make the following assumptions:(1)
The UAV’s take-off and landing process are not considered(2)
The UAVs fly at different altitudes to avoid collision(3)
In the process of task allocation, due to the high data transmission rate and low latency characteristics of the next generation-enabled IoT, we consider that the network communication topology remains unchanged(4)
The velocity of the UAVs is constant and equalFigure 1
In the unexplored area, red triangles denote UAVs and blue squares denote targets.


### 3.1. Targets and UAVs

Assuming thatT=T1,T2,⋯,TL are L targets in the mission region, the location and resource requirement are unknown at the beginning. There are Q different material resources in total. The resource requirement of target Tl is expressed as a vector:(1)rTl=r1Tl,r2Tl,⋯,rQTl⊤,l=1,2,⋯,L,whererqTl,q=1,2,⋯,Q denotes the quantity of q-type resource required by Tl.LetU=U1,U2,⋯,UN be the set of N heterogeneous UAVs. Each UAV carries different material resources, which is written as a vector:(2)rUn=r1Un,r2Un,⋯,rQUn⊤,n=1,2,⋯,N,whererqUn,q=1,2,⋯,Q denotes the quantity of q-type resources carried by Un.It is assumed that multiple UAVs use random search strategy [24] to perform search task in the mission area, and their sense range is limited, denoted as Rs. Regardless of the take-off and landing process of UAVs, each UAV is considered as flying in a two-dimensional plane. The kinematics model of UAV Un is expressed as follows:(3)ẋnẏnφ̇n=cosφn0sinφn001Vnωn,where (xn, yn) is the coordinates of Un, φn represents the UAV’s heading angle, and ωn and Vn are the UAV’s turn rate and speed, respectively.


### 3.2. Objective Function and Constraints

In this paper, we study the task allocation problem of multiple UAVs cooperative real-time target search and material resources distribution and analyze it from two aspects: mission completion time and UAV energy consumption. Consider a scenario where the UAVUn detects target Tl, but cannot meet the material requirements of Tl, then U acts as a leader and broadcasts Tl’s location and required resource information. All the N UAVs have the required resources and respond to Un, denoted as set A. Let Dnl=D1l,D2l,⋯,DNl and εnl=ε1l,ε2l,⋯,εNl represent the arrival time and energy consumption to Tl for the N UAVs, respectively. The set IA represents a subset of candidate coalition A, and ΠA is all nonempty subsets of A. The objective function is as follows:(1)
Minimum mission time(4)min∑j=1LTTj,whereTTj represents the execution time of the target Tj. Since the location and resource requirements of each target are unknown, task allocation is an online and real-time process. Therefore, in this paper, we adopt a greedy strategy to minimize the mission completion time, that is, minimize the completion time of each target. For the target Tl, the objective function can be expressed as follows:(5)minIA∈ΠAmaxn∈IADnl.(2)
Minimum energy consumption(6)min∑j=1LεTj,whereεTj is the UAV’s energy consumption of prosecuting the target Tj. Similarly, we use a greedy strategy and achieve objective (6) by minimizing the energy consumption of each target. For the target Tl, the objective function can be written as follows:(7)min∑j=1∣IA∣εjl,whereI_A represents the number of UAVs in set I_A and εjl is the energy consumption of the jth UAV in I_A to prosecute Tl.(3)
Minimum mission time and energy consumptionIf only the mission time is considered, the UAV that is closest to the target will be given priority every time. There may be a situation in which UAVs that are closer to the target have fewer remaining resources, so in order to meet the target resource requirements, a lot of UAVs will be needed, resulting in greater energy consumption. Similarly, if only the UAV’s energy consumption is considered, the mission completion time cannot be guaranteed. In order to maximize the system utility, we consider both mission time and energy consumption and use the linear weighted sum method to transform the multiobjectives optimization problem into a single objective. The objective function is as follows:(8)min∑j=1Lω·TTj+1−ω·εTj,whereω0≤ω≤1 is the weight coefficient. Similarly, we achieve objective (8) by minimizing the utility of each target. That is,(9)minIA∈ΠAω⋅maxn∈IADnl+1−ω⋅∑j=1IAεjl.In the calculation process, the dimension of time and energy consumption is different, so it is not easy to compare them. Therefore, we convert the target execution time into the energy consumption of the corresponding UAV, namely,(10)minIA∈ΠAω⋅ετl+1−ω⋅∑j=1∣IA∣εjl,where(11)τ=argmaxn∈IADnl,represents the UAV that arrives atTl the latest in candidate coalition IA.To successfully complete the task, the total resource of the candidate coalitionIA should be greater than the Tl’s demand, namely,(12)∑n=1∣IA∣rqUn≥rqTl,q=1,2,⋯,Q.


## 3.1. Targets and UAVs

Assuming thatT=T1,T2,⋯,TL are L targets in the mission region, the location and resource requirement are unknown at the beginning. There are Q different material resources in total. The resource requirement of target Tl is expressed as a vector:(1)rTl=r1Tl,r2Tl,⋯,rQTl⊤,l=1,2,⋯,L,whererqTl,q=1,2,⋯,Q denotes the quantity of q-type resource required by Tl.LetU=U1,U2,⋯,UN be the set of N heterogeneous UAVs. Each UAV carries different material resources, which is written as a vector:(2)rUn=r1Un,r2Un,⋯,rQUn⊤,n=1,2,⋯,N,whererqUn,q=1,2,⋯,Q denotes the quantity of q-type resources carried by Un.It is assumed that multiple UAVs use random search strategy [24] to perform search task in the mission area, and their sense range is limited, denoted as Rs. Regardless of the take-off and landing process of UAVs, each UAV is considered as flying in a two-dimensional plane. The kinematics model of UAV Un is expressed as follows:(3)ẋnẏnφ̇n=cosφn0sinφn001Vnωn,where (xn, yn) is the coordinates of Un, φn represents the UAV’s heading angle, and ωn and Vn are the UAV’s turn rate and speed, respectively.


## 3.2. Objective Function and Constraints

In this paper, we study the task allocation problem of multiple UAVs cooperative real-time target search and material resources distribution and analyze it from two aspects: mission completion time and UAV energy consumption. Consider a scenario where the UAVUn detects target Tl, but cannot meet the material requirements of Tl, then U acts as a leader and broadcasts Tl’s location and required resource information. All the N UAVs have the required resources and respond to Un, denoted as set A. Let Dnl=D1l,D2l,⋯,DNl and εnl=ε1l,ε2l,⋯,εNl represent the arrival time and energy consumption to Tl for the N UAVs, respectively. The set IA represents a subset of candidate coalition A, and ΠA is all nonempty subsets of A. The objective function is as follows:(1)
Minimum mission time(4)min∑j=1LTTj,whereTTj represents the execution time of the target Tj. Since the location and resource requirements of each target are unknown, task allocation is an online and real-time process. Therefore, in this paper, we adopt a greedy strategy to minimize the mission completion time, that is, minimize the completion time of each target. For the target Tl, the objective function can be expressed as follows:(5)minIA∈ΠAmaxn∈IADnl.(2)
Minimum energy consumption(6)min∑j=1LεTj,whereεTj is the UAV’s energy consumption of prosecuting the target Tj. Similarly, we use a greedy strategy and achieve objective (6) by minimizing the energy consumption of each target. For the target Tl, the objective function can be written as follows:(7)min∑j=1∣IA∣εjl,whereI_A represents the number of UAVs in set I_A and εjl is the energy consumption of the jth UAV in I_A to prosecute Tl.(3)
Minimum mission time and energy consumptionIf only the mission time is considered, the UAV that is closest to the target will be given priority every time. There may be a situation in which UAVs that are closer to the target have fewer remaining resources, so in order to meet the target resource requirements, a lot of UAVs will be needed, resulting in greater energy consumption. Similarly, if only the UAV’s energy consumption is considered, the mission completion time cannot be guaranteed. In order to maximize the system utility, we consider both mission time and energy consumption and use the linear weighted sum method to transform the multiobjectives optimization problem into a single objective. The objective function is as follows:(8)min∑j=1Lω·TTj+1−ω·εTj,whereω0≤ω≤1 is the weight coefficient. Similarly, we achieve objective (8) by minimizing the utility of each target. That is,(9)minIA∈ΠAω⋅maxn∈IADnl+1−ω⋅∑j=1IAεjl.In the calculation process, the dimension of time and energy consumption is different, so it is not easy to compare them. Therefore, we convert the target execution time into the energy consumption of the corresponding UAV, namely,(10)minIA∈ΠAω⋅ετl+1−ω⋅∑j=1∣IA∣εjl,where(11)τ=argmaxn∈IADnl,represents the UAV that arrives atTl the latest in candidate coalition IA.To successfully complete the task, the total resource of the candidate coalitionIA should be greater than the Tl’s demand, namely,(12)∑n=1∣IA∣rqUn≥rqTl,q=1,2,⋯,Q.


## 4. Path Planning and Energy Consumption Model

In this paper, although we study the task allocation problem of multi-UAVs, in order to accurately calculate the UAV’s flight time and energy consumption, we also consider the path planning of UAV. We model the UAV as a Dubins model and derive the calculation formula of the UAV’s energy consumption.


### 4.1. Dubins Curve

Dubins [31] considered the influence of the vehicle’s minimum turning radius and used a geometric method to give the vehicle’s shortest path formula between any two points (including coordinates and directions). It is composed of the maximum curvature arc and straight line segment, which is also called the Dubins path. As shown in Figure 2, assuming that the UAV’s initial position, flight direction, and the target location are known, there are two Dubins paths that can reach the target, namely, the shortest path (SP) and the longest path (LP). SP has the shortest distance to reach the target. If we use the SP to plan the path for the UAV, when the distance between the UAV and the target is less than the minimum turning radius, the UAV will be unable to reach the target. Compared with SP, LP has a longer path length, but it will not fail to reach the target. Therefore, in this paper, we use the LP. Its length calculation method can refer to literature [32].Figure 2
Dubins longest and shortest path.


### 4.2. Energy Consumption Model

We focus on the UAV’s propulsion energy consumption which is used to maintain aloft and support its maneuverability. Based on the classic aircraft consumption model in aerodynamic theory, the required propulsion energy can be expressed as a function of the locationpt for fixed-wing UAVs with a constant altitude [33]:(13)Ept=12mvT2−v02+∫0Tc1vt3+c2g2+at2−aTtvt2/vt2g2vtdt,where(14)vt≜ṗt,at≜p¨t,represent the UAV’s instantaneous velocity and acceleration, respectively, andc1 and c2 denote two parameters related with aircraft mass, wing area, aircraft shape, air density, and so on. The parameter g is the acceleration of gravity, and m represents the UAV’s total mass. T is the UAV’s flight time.In the Dubins model, the UAV’s flight path consists of arc and straight line. Therefore, we consider the energy consumption model in two special cases. One is that the UAV flies along a straight horizontal line at a constant speedV, i.e., at=0 and vt=V for all t. (13) can be simplified as(15)EV=Tc1V3+c2V.According to formula (15), the relationship between energy consumption and speed is depicted in Figure 3. As can be seen from Figure 3, given the required parameters, we can calculate an optimal speed, which has the lowest energy consumption.Figure 3
An illustration of the speedV versus required power for a UAV in a straight level flight.The other is that the UAV makes uniform circular motion, i.e.,vt=V and aΤtvt=0 for all t. At any moment, the UAV’s acceleration direction is always perpendicular to the speed direction. The magnitude of the acceleration is at=at=V2/r for all t. Therefore, (13) can be simplified as(16)EV,r=Tc1V3+c2g2r2V3+c2V,wherer denotes the radius of the circular trajectory. We can find that, compared with uniform linear motion, additional energy consumption is generated when the UAV’s flight direction is changed.


## 4.1. Dubins Curve

Dubins [31] considered the influence of the vehicle’s minimum turning radius and used a geometric method to give the vehicle’s shortest path formula between any two points (including coordinates and directions). It is composed of the maximum curvature arc and straight line segment, which is also called the Dubins path. As shown in Figure 2, assuming that the UAV’s initial position, flight direction, and the target location are known, there are two Dubins paths that can reach the target, namely, the shortest path (SP) and the longest path (LP). SP has the shortest distance to reach the target. If we use the SP to plan the path for the UAV, when the distance between the UAV and the target is less than the minimum turning radius, the UAV will be unable to reach the target. Compared with SP, LP has a longer path length, but it will not fail to reach the target. Therefore, in this paper, we use the LP. Its length calculation method can refer to literature [32].Figure 2
Dubins longest and shortest path.


## 4.2. Energy Consumption Model

We focus on the UAV’s propulsion energy consumption which is used to maintain aloft and support its maneuverability. Based on the classic aircraft consumption model in aerodynamic theory, the required propulsion energy can be expressed as a function of the locationpt for fixed-wing UAVs with a constant altitude [33]:(13)Ept=12mvT2−v02+∫0Tc1vt3+c2g2+at2−aTtvt2/vt2g2vtdt,where(14)vt≜ṗt,at≜p¨t,represent the UAV’s instantaneous velocity and acceleration, respectively, andc1 and c2 denote two parameters related with aircraft mass, wing area, aircraft shape, air density, and so on. The parameter g is the acceleration of gravity, and m represents the UAV’s total mass. T is the UAV’s flight time.In the Dubins model, the UAV’s flight path consists of arc and straight line. Therefore, we consider the energy consumption model in two special cases. One is that the UAV flies along a straight horizontal line at a constant speedV, i.e., at=0 and vt=V for all t. (13) can be simplified as(15)EV=Tc1V3+c2V.According to formula (15), the relationship between energy consumption and speed is depicted in Figure 3. As can be seen from Figure 3, given the required parameters, we can calculate an optimal speed, which has the lowest energy consumption.Figure 3
An illustration of the speedV versus required power for a UAV in a straight level flight.The other is that the UAV makes uniform circular motion, i.e.,vt=V and aΤtvt=0 for all t. At any moment, the UAV’s acceleration direction is always perpendicular to the speed direction. The magnitude of the acceleration is at=at=V2/r for all t. Therefore, (13) can be simplified as(16)EV,r=Tc1V3+c2g2r2V3+c2V,wherer denotes the radius of the circular trajectory. We can find that, compared with uniform linear motion, additional energy consumption is generated when the UAV’s flight direction is changed.


## 5. Coalition Formation

When the UAV finds a target, it decides its next action based on its current status. As shown in Figure4, the UAV Un detects the target Tl which requires rTl resource. If Un has the required resources of Tl, it will prosecute Tl.Figure 4
Sequence of actions in the process of coalition formation.IfUn has insufficient resources for the target Tl, Un becomes a coalition leader and broadcasts the requirement and location of Tl to the other UAVs. The UAVs, which have required resources, will respond to Un with their resource vector and cost to prosecute Tl. After receiving all the responses, Un uses the coalition formation algorithm to obtain a suitable coalition for Tl. If there is no suitable coalition, U will broadcast a rejection message to all responders. Otherwise, it broadcasts coalition information to all the selected UAVs. The selected UAVs will replan their path to achieve simultaneous arrival to the Tl. The rejected UAVs will continue to perform their original operation. When forming a coalition, the coalition leader has to solve an optimization problem which is computationally intensive. We propose different coalition formation algorithms according to different optimization objectives.


### 5.1. Minimum Mission Time

To achieve the minimum mission time goal, the coalition leader has to solve the optimization problem given by formula (5) and (12). The traditional exhaustive method is not suitable for real-time task assignment problem because of its large search space and high time complexity. In this paper, we propose a two-stage mechanism which has low computational complexity. The specific process is given in Algorithm 1.Algorithm 1: The two-stage coalition formation algorithm.
Input: potential coalition members PUn,Tl and their earliest arrival time DUn,TlOutput: coalition CUn,Tl1: Initialize:2: Sort the setPUn,Tl in ascending order according to arrival time DUn,Tl.3:Dsorted,Psorted = sortDUn,Tl,PUn,Tl4:CUn,Tl=∅ and rCUn,Tl=05:fori = 1 to PUn,Tldo6:Uk⟵Pisorted7:  AppendUk to CUn,Tl8:rCUn,Tl⟵rCUn,Tl+rUk9:ifrqCUn,Tl≥rqTl, q=1,2,⋯,Qthen10:break11:else12:continue13:end if14:end for15:ifrqCUn,Tl≥rqTl, q=1,2,⋯,Qthen16:  Select the last member fromCUn,Tl as the root of the tree, denote as nc17:nc=rUnc18:j=119:whilenc<rTldo20:j=j+121:   Select a member fromCUn,Tl except for the current node and its parent, all grandparents, and left brother nodes, and add it to the tree, denote as nj22:np is nj's parent node23:nj=rUnj+rUnp24:nc=nj25:end while26:CUn,Tl=∅27:  Append current node, its parent node, and all grandparent nodes toCUn,Tl28:returnCUn,Tl29:else30:return No feasible coalition31:end ifIn the first stage, we decide on a minimum time coalition which satisfies the target resource requirements. Then, we build a resource tree to prune some unnecessary UAVs to achieve the minimum coalition size. Suppose thatUn has detected Tl but has insufficient resources. Therefore, Un broadcasts the information of Tl to other UAVs. After receiving all the responses, Un sorts the responders in ascending order of their cost, i.e., the earliest arrival time to Tl (line 2 in Algorithm 1). Starting with the first UAV after sorting, only one UAV is taken at a time until the requirement of Tl is met (line 3-14 in Algorithm 1). After the above step, if there has a feasible coalition, its time must be minimum to prosecute Tl. Then, for the obtained minimum time coalition CUn,Tl, we build a resource tree to remove some members whose resources are not necessary. Since the resource of the last member of CUn,Tl is necessary, we take it as the root node. Then, we select a member from CUn,Tl and add it to the current node. The value of new node is its resource vector plus the value of its parent node. This process is repeated until the value of the current node meets the target demand. The final coalition is made up of the current node, its parent node, and all grandfather nodes. To illustrate the pruning process, we give a hypothetical example as shown in Figure 5 where the selected minimum time coalition CUn,Tl is U1,U2,U3,U4,U5.Figure 5
Resource tree.


### 5.2. Minimum Energy Consumption

Due to the limitation of UAV's size and technology, its energy is limited. Therefore, in order to maximize the efficiency of the UAV team, we need to consider the UAV’s energy consumption when assigning tasks. To minimize the UAV’s energy consumption, we model the task allocation problem as a zero-one integer programming problem. Assuming that the UAVUn is a coalition leader for the target Tl and the set of candidate coalition members is CUn,Tl=U1,U2,⋯,UN. We first define the following binary variable:(17)xi=1iftheUAVUiisselected,0otherwise.Then, a general scheme of the zero-one integer linear programming formulation of the task allocation problem can be expressed as follows:(18)min∑i=1CUn,Tlxiεil,(19)s.t.∑i=1CUn,TlrqUixi≥rqTl,q=1,2,⋯,Q,(20)xi∈0,1,∀i∈1,2,⋯,CUn,Tl,where (19) is the resource constraint, which is used to ensure that the selected UAVs meet the target resource requirement. CUn,Tl represents the number of the UAV in the set CUn,Tl. εil is the energy consumption of the ith UAV in the set CUn,Tl to prosecute Tl.


### 5.3. Minimum Mission Time and Energy Consumption

Considering both the mission time and energy consumption, the coalition leader needs to tackle the optimization problem (10). Meanwhile, the number of UAVs in the coalition also needs to be considered, because it implicitly assists in fast completing mission. To solve it, we develop a resource tree and use it to get a suitable task allocation solution in an acceptable time.The detailed process is shown in Algorithm2. Similarly, we assume that the UAV Un detects the target Tl and has insufficient resource. CUn,Tl is the candidate UAV set for Tl. Firstly, we initialize a cell structure Cf to be empty, which stores some feasible coalitions that meet the Tl’s resource requirement. Then, we take Tl as the root node of the tree. When we add a new node, we select a UAV from CUn,Tl except for the current node and its parent, grandfather, and left brother nodes and, then, add it to the current node. The value of the new node is the value of its parent node minus its resource vector. If the value of the new node is less than 0, the current node, its parent node, and all grandfather nodes except the root node form a feasible coalition. If the first feasible coalition is found, the process ends when there is no node that can be added to the current layer. Otherwise, the above process is repeated. Then, Un selects a optimal coalition from Cf based on (10).Algorithm 2: The resource tree-based coalition formation algorithm.
Input: potential coalition members CUn,Tl, and their arrival time DUn,Tl, energy consumption εUn,TlOutput: Cl1:Cf=∅, Cl=∅, flag=02: Take the targetTl as the root node, denote as nc.3:nc=rTl4:whileflag==0do5:  Select a member fromCUn,Tl except for the current node and its parent, all grandparents, and left brother nodes, and add it to the current node, denote as ns.6:np is ns’s parent node7:ns=rUnp−rUns8:ifns≤0then9:Cf⟵ current node, its parent node, and all grandparent nodes except for the root node10:flag=111:end if12:ifflag==1 and no nodes can be added to this layer then13:break14:else15:flag=016:end if17:if no nodes can be added to the tree. then18:break19:end if20:end while21:ifCf≠∅then22:Cl⟵ select an optimal coalition from Cf23:end ifWe give a simple example to better understand Algorithm 5.3. Assuming thatU1 has detected T1 and the set of candidate UAV is CU1,T1=U1,U2,U3,U4,U5. Their resource vector is given in Table 1, and the resource requirement of T1 is rT1=5,3⊤. According to Algorithm 2, the final result is shown in Figure 6. 1:5,3 represents a key-value pair, where the key is the number of a tree node, and the value is the value of its parent node minus its resource vector. The value of the root node T1 is its resource requirement. Since the values of node 7, 11, 12, 13, 14, and 16 are less than 0, the feasible coalition set Cf is U1,U2,U2,U3,U2,U4,U2,U5,U3,U4,U4,U5. The above process ensures that the size of feasible coalition is the smallest. Then, U1 selects an optimal coalition C1 among Cf based on (10).Table 1
The resource of the candidate coalitionCU1,T1.
UAVsResource vectorU1(2,1)⊤U2(3,3)⊤U3(2,2)⊤U4(3,1)⊤U5(2,3)⊤Figure 6
Resource tree of the targetT1.


## 5.1. Minimum Mission Time

To achieve the minimum mission time goal, the coalition leader has to solve the optimization problem given by formula (5) and (12). The traditional exhaustive method is not suitable for real-time task assignment problem because of its large search space and high time complexity. In this paper, we propose a two-stage mechanism which has low computational complexity. The specific process is given in Algorithm 1.Algorithm 1: The two-stage coalition formation algorithm.
Input: potential coalition members PUn,Tl and their earliest arrival time DUn,TlOutput: coalition CUn,Tl1: Initialize:2: Sort the setPUn,Tl in ascending order according to arrival time DUn,Tl.3:Dsorted,Psorted = sortDUn,Tl,PUn,Tl4:CUn,Tl=∅ and rCUn,Tl=05:fori = 1 to PUn,Tldo6:Uk⟵Pisorted7:  AppendUk to CUn,Tl8:rCUn,Tl⟵rCUn,Tl+rUk9:ifrqCUn,Tl≥rqTl, q=1,2,⋯,Qthen10:break11:else12:continue13:end if14:end for15:ifrqCUn,Tl≥rqTl, q=1,2,⋯,Qthen16:  Select the last member fromCUn,Tl as the root of the tree, denote as nc17:nc=rUnc18:j=119:whilenc<rTldo20:j=j+121:   Select a member fromCUn,Tl except for the current node and its parent, all grandparents, and left brother nodes, and add it to the tree, denote as nj22:np is nj's parent node23:nj=rUnj+rUnp24:nc=nj25:end while26:CUn,Tl=∅27:  Append current node, its parent node, and all grandparent nodes toCUn,Tl28:returnCUn,Tl29:else30:return No feasible coalition31:end ifIn the first stage, we decide on a minimum time coalition which satisfies the target resource requirements. Then, we build a resource tree to prune some unnecessary UAVs to achieve the minimum coalition size. Suppose thatUn has detected Tl but has insufficient resources. Therefore, Un broadcasts the information of Tl to other UAVs. After receiving all the responses, Un sorts the responders in ascending order of their cost, i.e., the earliest arrival time to Tl (line 2 in Algorithm 1). Starting with the first UAV after sorting, only one UAV is taken at a time until the requirement of Tl is met (line 3-14 in Algorithm 1). After the above step, if there has a feasible coalition, its time must be minimum to prosecute Tl. Then, for the obtained minimum time coalition CUn,Tl, we build a resource tree to remove some members whose resources are not necessary. Since the resource of the last member of CUn,Tl is necessary, we take it as the root node. Then, we select a member from CUn,Tl and add it to the current node. The value of new node is its resource vector plus the value of its parent node. This process is repeated until the value of the current node meets the target demand. The final coalition is made up of the current node, its parent node, and all grandfather nodes. To illustrate the pruning process, we give a hypothetical example as shown in Figure 5 where the selected minimum time coalition CUn,Tl is U1,U2,U3,U4,U5.Figure 5
Resource tree.


## 5.2. Minimum Energy Consumption

Due to the limitation of UAV's size and technology, its energy is limited. Therefore, in order to maximize the efficiency of the UAV team, we need to consider the UAV’s energy consumption when assigning tasks. To minimize the UAV’s energy consumption, we model the task allocation problem as a zero-one integer programming problem. Assuming that the UAVUn is a coalition leader for the target Tl and the set of candidate coalition members is CUn,Tl=U1,U2,⋯,UN. We first define the following binary variable:(17)xi=1iftheUAVUiisselected,0otherwise.Then, a general scheme of the zero-one integer linear programming formulation of the task allocation problem can be expressed as follows:(18)min∑i=1CUn,Tlxiεil,(19)s.t.∑i=1CUn,TlrqUixi≥rqTl,q=1,2,⋯,Q,(20)xi∈0,1,∀i∈1,2,⋯,CUn,Tl,where (19) is the resource constraint, which is used to ensure that the selected UAVs meet the target resource requirement. CUn,Tl represents the number of the UAV in the set CUn,Tl. εil is the energy consumption of the ith UAV in the set CUn,Tl to prosecute Tl.


## 5.3. Minimum Mission Time and Energy Consumption

Considering both the mission time and energy consumption, the coalition leader needs to tackle the optimization problem (10). Meanwhile, the number of UAVs in the coalition also needs to be considered, because it implicitly assists in fast completing mission. To solve it, we develop a resource tree and use it to get a suitable task allocation solution in an acceptable time.The detailed process is shown in Algorithm2. Similarly, we assume that the UAV Un detects the target Tl and has insufficient resource. CUn,Tl is the candidate UAV set for Tl. Firstly, we initialize a cell structure Cf to be empty, which stores some feasible coalitions that meet the Tl’s resource requirement. Then, we take Tl as the root node of the tree. When we add a new node, we select a UAV from CUn,Tl except for the current node and its parent, grandfather, and left brother nodes and, then, add it to the current node. The value of the new node is the value of its parent node minus its resource vector. If the value of the new node is less than 0, the current node, its parent node, and all grandfather nodes except the root node form a feasible coalition. If the first feasible coalition is found, the process ends when there is no node that can be added to the current layer. Otherwise, the above process is repeated. Then, Un selects a optimal coalition from Cf based on (10).Algorithm 2: The resource tree-based coalition formation algorithm.
Input: potential coalition members CUn,Tl, and their arrival time DUn,Tl, energy consumption εUn,TlOutput: Cl1:Cf=∅, Cl=∅, flag=02: Take the targetTl as the root node, denote as nc.3:nc=rTl4:whileflag==0do5:  Select a member fromCUn,Tl except for the current node and its parent, all grandparents, and left brother nodes, and add it to the current node, denote as ns.6:np is ns’s parent node7:ns=rUnp−rUns8:ifns≤0then9:Cf⟵ current node, its parent node, and all grandparent nodes except for the root node10:flag=111:end if12:ifflag==1 and no nodes can be added to this layer then13:break14:else15:flag=016:end if17:if no nodes can be added to the tree. then18:break19:end if20:end while21:ifCf≠∅then22:Cl⟵ select an optimal coalition from Cf23:end ifWe give a simple example to better understand Algorithm 5.3. Assuming thatU1 has detected T1 and the set of candidate UAV is CU1,T1=U1,U2,U3,U4,U5. Their resource vector is given in Table 1, and the resource requirement of T1 is rT1=5,3⊤. According to Algorithm 2, the final result is shown in Figure 6. 1:5,3 represents a key-value pair, where the key is the number of a tree node, and the value is the value of its parent node minus its resource vector. The value of the root node T1 is its resource requirement. Since the values of node 7, 11, 12, 13, 14, and 16 are less than 0, the feasible coalition set Cf is U1,U2,U2,U3,U2,U4,U2,U5,U3,U4,U4,U5. The above process ensures that the size of feasible coalition is the smallest. Then, U1 selects an optimal coalition C1 among Cf based on (10).Table 1
The resource of the candidate coalitionCU1,T1.
UAVsResource vectorU1(2,1)⊤U2(3,3)⊤U3(2,2)⊤U4(3,1)⊤U5(2,3)⊤Figure 6
Resource tree of the targetT1.


## 6. Simulation Results

In this section, three groups of numerical simulation are carried out to evaluate the performance of our proposed algorithms. In the first example, we give a general scenario to illustrate the entire search and prosecute process. In the second example, we show the difference between the proposed three coalition formation algorithms. Finally, we show the effects of changing the number of UAVs on the mission completion time and energy consumption through the Monte Carlo simulation. In addition, we compare our proposed algorithms with the task allocation algorithm based on resource welfare [25].


### 6.1. General Scenario

Considering a general scenario with six UAVs and two targets in a bounded region3200m×3200m, we analyze the whole process of heterogeneous UAVs cooperative target search and execution. If the UAV flies out of the mission area, it will take the minimum turning radius to return to the mission area. Table 2 shows the initial information of each UAV, and Table 3 lists the location and resource requirement of each target. Note that the UAVs do not have any information about the location and required resource of the target at the initial moment. The information of the target can be obtained only when the UAV detects the target. The control parameters are shown in Table 4 where V is the flight speed, Rs denotes the sensor radius of the UAV, and Rmin denotes the UAV's minimum turning radius. Figure 7 illustrates the initial environment.Table 2
Initial information of UAVs.
UAVsLocation (m)Heading angle (°)ResourceUAV 1(500, 2500)30(2,1)UAV 2(0, 0)60(1,1)UAV 3(1000, 2000)300(3,2)UAV 4(3000, 2500)270(2,3)UAV 5(2000, 1500)30(2,2)UAV 6(2000, 500)60(2,2)Table 3
Initial information of targets.
TargetsLocation (m)Resource requirementTarget 1(1500, 1500)(4,2)Target 2(2000, 2000)(3,3)Table 4
Control parameters.
ParametersValueV50 m/sRmin50 mRs500 mω0.4c19.26×10−4c22250Figure 7
An illustration of initial location of UAVs and targets.At the initial moment, all UAVs perform a random search task along the heading direction. At timet=0.1s, U5 detects T1 and T2. U5 chooses T1 as the target, because the resource of U5 cannot meet the resource requirement of T1 or T2, while T1 is closer to U5. As U5 does not have sufficient resource to prosecute T1, U5 becomes a coalition leader and broadcasts the requirement and location of T1 to other UAVs. After receiving all the responses, U5 forms a coalition C1=U3,U5 for the target T1 using our proposed resource tree-based coalition formation algorithm, which comprehensively considers the target execution time and energy consumption. Then, U3 and U5 replan their path based on the Dubins curve to simultaneously arrive at T1 as shown in Figure 8. At time t=0.2s, U5 detects T2. U5 cannot be a potential coalition member, because it is now in the state of performing task. However, U5 can still act as a coalition leader and broadcast the location and resource requirement of T2 to other UAVs. After receiving all the responses, U5 forms a coalition C2=U1,U4 for T2. The trajectory of U1 and U4 is shown in Figure 9. The total mission time including target search and prosecute is 37.9 s, and the total energy consumption is 5.4419×104 J.Figure 8
The trajectories ofU3 and U5.Figure 9
The trajectories ofU1 and U4.Figures8 and 9 show that our proposed task allocation algorithm effectively completes the target search and prosecute in an unexplored environment. The proposed resource tree-based coalition formation algorithm can assign suitable UAVs for the target.


### 6.2. Comparison of Four Algorithms

In this example, we consider a simple scenario with one target and six UAVs in a bounded area. Our goal is to compare the differences between the four coalition formation algorithms. Table5 shows the initial information of all UAVs. The target is located at (1500, 1500), and resource requirement is rT=5,3⊤. The control parameters are the same as in Table 4.Table 5
The initial information of the UAVs.
UAVsLocation (m)Heading angle (°)ResourceUAV 1(500, 2500)30(2,2)UAV 2(0, 0)60(3,1)UAV 3(1000, 2000)300(2,1)UAV 4(1000, 1000)60(1,2)UAV 5(2000, 2000)30(4,1)UAV 6(2000, 1500)60(2,1)We compare the mission time, energy consumption, and mission planning time which includes coalition formation time and path planning time. The specific results are shown in Table6. The trajectories of coalition member are shown in Figures 10–12, where the coalition member for minimum energy consumption is the same as the resource tree-based coalition formation algorithm.Table 6
Performance comparison of the four algorithms.
Two-stageZero-one integer programmingResource treeResource welfareCoalition membersU3,U5,U6U4,U5U4,U5U1,U5Mission time (s)20.4220.4220.4234.23Energy consumption(×104 J)2.21421.73691.7361.7849Mission planning time (s)0.130.430.180.15Figure 10
Coalition members and its trajectories using the proposed resource tree-based coalition formation algorithm.Figure 11
Coalition members and its trajectories using the proposed two-stage coalition formation algorithm.Figure 12
Coalition members and its trajectories using the resource welfare-based coalition formation algorithm.It can be found from Figures10–12 that different coalition formation algorithms get different coalitions even if the target and potential coalition members are the same. Table 6 shows that the energy consumption of the two-stage coalition formation algorithm is the highest, because it only considers the mission time and do not consider the energy consumption of UAVs when it forms the coalition, which leads to the increased number of UAVs. The resource tree-based coalition formation algorithm has the same coalition members as the minimum energy consumption. However, the resource tree-based algorithm has less mission planning time, because the solver of the zero-one integer programming problem uses the cut plane method which has intensive computation. Therefore, the resource tree-based algorithm is more suitable for a real-time task assignment application. Compared with the resource welfare-based task allocation algorithm, the resource tree-based algorithm has less mission time and energy consumption. Because the resource welfare-based algorithm chooses U1 instead of U4 as one of the coalition members to achieve a balanced resource depletion, and U1 is farther from the target than U4.


### 6.3. Effects of Varying Number of UAVs

In this example, we make use of Monte Carlo simulation to illustrate the performance. The average mission completion time and energy consumption are measured and compared by varying the number of UAVs. The size of the mission area is5000m×5000m. The control parameters are the same as in Table 4. At the beginning, assume that all the UAVs are located at 0,0, and the resources of the UAVs and targets are randomly generated. The heading angles of UAVs are different. There are five targets in the mission area. The number of UAVs varies from 6 to 20. The experimental results are shown in Figures 12 and 13.Figure 13
Comparison of average mission completion time of four algorithms.Figure13 shows the average mission completion time of four algorithms when the number of UAVs changes. As the number of UAVs increases, the mission completion time decreases. Because the increased number of UAVs allows the resource requirements of the targets to be met as soon as possible, and the execution of multiple targets can be performed simultaneously. Compared with the resource welfare-based algorithm, the resource tree-based algorithm has less mission completion time. However, there is a small difference in the average mission completion time among the proposed algorithms.Figure14 compares the average energy consumption of four algorithms when the number of UAVs changes. As the number of UAVs increases, the energy consumption of UAVs continues to increase, because more UAVs are dispatched to perform mission. The resource welfare-based task allocation algorithm has the highest energy consumption. Because it uses an average resource consumption strategy, and each UAV maintains almost equal resource surplus. As the number of UAVs increases, multiple UAVs are allocated to execute the target with more resources, thereby increasing energy consumption. The energy consumption of the resource tree-based algorithm is less than the other two proposed algorithms.Figure 14
Comparison of average UAV energy consumption of the four algorithms.


## 6.1. General Scenario

Considering a general scenario with six UAVs and two targets in a bounded region3200m×3200m, we analyze the whole process of heterogeneous UAVs cooperative target search and execution. If the UAV flies out of the mission area, it will take the minimum turning radius to return to the mission area. Table 2 shows the initial information of each UAV, and Table 3 lists the location and resource requirement of each target. Note that the UAVs do not have any information about the location and required resource of the target at the initial moment. The information of the target can be obtained only when the UAV detects the target. The control parameters are shown in Table 4 where V is the flight speed, Rs denotes the sensor radius of the UAV, and Rmin denotes the UAV's minimum turning radius. Figure 7 illustrates the initial environment.Table 2
Initial information of UAVs.
UAVsLocation (m)Heading angle (°)ResourceUAV 1(500, 2500)30(2,1)UAV 2(0, 0)60(1,1)UAV 3(1000, 2000)300(3,2)UAV 4(3000, 2500)270(2,3)UAV 5(2000, 1500)30(2,2)UAV 6(2000, 500)60(2,2)Table 3
Initial information of targets.
TargetsLocation (m)Resource requirementTarget 1(1500, 1500)(4,2)Target 2(2000, 2000)(3,3)Table 4
Control parameters.
ParametersValueV50 m/sRmin50 mRs500 mω0.4c19.26×10−4c22250Figure 7
An illustration of initial location of UAVs and targets.At the initial moment, all UAVs perform a random search task along the heading direction. At timet=0.1s, U5 detects T1 and T2. U5 chooses T1 as the target, because the resource of U5 cannot meet the resource requirement of T1 or T2, while T1 is closer to U5. As U5 does not have sufficient resource to prosecute T1, U5 becomes a coalition leader and broadcasts the requirement and location of T1 to other UAVs. After receiving all the responses, U5 forms a coalition C1=U3,U5 for the target T1 using our proposed resource tree-based coalition formation algorithm, which comprehensively considers the target execution time and energy consumption. Then, U3 and U5 replan their path based on the Dubins curve to simultaneously arrive at T1 as shown in Figure 8. At time t=0.2s, U5 detects T2. U5 cannot be a potential coalition member, because it is now in the state of performing task. However, U5 can still act as a coalition leader and broadcast the location and resource requirement of T2 to other UAVs. After receiving all the responses, U5 forms a coalition C2=U1,U4 for T2. The trajectory of U1 and U4 is shown in Figure 9. The total mission time including target search and prosecute is 37.9 s, and the total energy consumption is 5.4419×104 J.Figure 8
The trajectories ofU3 and U5.Figure 9
The trajectories ofU1 and U4.Figures8 and 9 show that our proposed task allocation algorithm effectively completes the target search and prosecute in an unexplored environment. The proposed resource tree-based coalition formation algorithm can assign suitable UAVs for the target.


## 6.2. Comparison of Four Algorithms

In this example, we consider a simple scenario with one target and six UAVs in a bounded area. Our goal is to compare the differences between the four coalition formation algorithms. Table5 shows the initial information of all UAVs. The target is located at (1500, 1500), and resource requirement is rT=5,3⊤. The control parameters are the same as in Table 4.Table 5
The initial information of the UAVs.
UAVsLocation (m)Heading angle (°)ResourceUAV 1(500, 2500)30(2,2)UAV 2(0, 0)60(3,1)UAV 3(1000, 2000)300(2,1)UAV 4(1000, 1000)60(1,2)UAV 5(2000, 2000)30(4,1)UAV 6(2000, 1500)60(2,1)We compare the mission time, energy consumption, and mission planning time which includes coalition formation time and path planning time. The specific results are shown in Table6. The trajectories of coalition member are shown in Figures 10–12, where the coalition member for minimum energy consumption is the same as the resource tree-based coalition formation algorithm.Table 6
Performance comparison of the four algorithms.
Two-stageZero-one integer programmingResource treeResource welfareCoalition membersU3,U5,U6U4,U5U4,U5U1,U5Mission time (s)20.4220.4220.4234.23Energy consumption(×104 J)2.21421.73691.7361.7849Mission planning time (s)0.130.430.180.15Figure 10
Coalition members and its trajectories using the proposed resource tree-based coalition formation algorithm.Figure 11
Coalition members and its trajectories using the proposed two-stage coalition formation algorithm.Figure 12
Coalition members and its trajectories using the resource welfare-based coalition formation algorithm.It can be found from Figures10–12 that different coalition formation algorithms get different coalitions even if the target and potential coalition members are the same. Table 6 shows that the energy consumption of the two-stage coalition formation algorithm is the highest, because it only considers the mission time and do not consider the energy consumption of UAVs when it forms the coalition, which leads to the increased number of UAVs. The resource tree-based coalition formation algorithm has the same coalition members as the minimum energy consumption. However, the resource tree-based algorithm has less mission planning time, because the solver of the zero-one integer programming problem uses the cut plane method which has intensive computation. Therefore, the resource tree-based algorithm is more suitable for a real-time task assignment application. Compared with the resource welfare-based task allocation algorithm, the resource tree-based algorithm has less mission time and energy consumption. Because the resource welfare-based algorithm chooses U1 instead of U4 as one of the coalition members to achieve a balanced resource depletion, and U1 is farther from the target than U4.


## 6.3. Effects of Varying Number of UAVs

In this example, we make use of Monte Carlo simulation to illustrate the performance. The average mission completion time and energy consumption are measured and compared by varying the number of UAVs. The size of the mission area is5000m×5000m. The control parameters are the same as in Table 4. At the beginning, assume that all the UAVs are located at 0,0, and the resources of the UAVs and targets are randomly generated. The heading angles of UAVs are different. There are five targets in the mission area. The number of UAVs varies from 6 to 20. The experimental results are shown in Figures 12 and 13.Figure 13
Comparison of average mission completion time of four algorithms.Figure13 shows the average mission completion time of four algorithms when the number of UAVs changes. As the number of UAVs increases, the mission completion time decreases. Because the increased number of UAVs allows the resource requirements of the targets to be met as soon as possible, and the execution of multiple targets can be performed simultaneously. Compared with the resource welfare-based algorithm, the resource tree-based algorithm has less mission completion time. However, there is a small difference in the average mission completion time among the proposed algorithms.Figure14 compares the average energy consumption of four algorithms when the number of UAVs changes. As the number of UAVs increases, the energy consumption of UAVs continues to increase, because more UAVs are dispatched to perform mission. The resource welfare-based task allocation algorithm has the highest energy consumption. Because it uses an average resource consumption strategy, and each UAV maintains almost equal resource surplus. As the number of UAVs increases, multiple UAVs are allocated to execute the target with more resources, thereby increasing energy consumption. The energy consumption of the resource tree-based algorithm is less than the other two proposed algorithms.Figure 14
Comparison of average UAV energy consumption of the four algorithms.


## 7. Conclusions and Future Works

In this paper, we studied the task allocation problem of heterogeneous UAVs cooperative real-time target search and prosecute in an unexplored area. We analyzed it from two aspects: mission time and energy consumption. According to different optimization objectives, we established the corresponding model and designed the solution algorithm. For the minimum mission time objective, we proposed a two-stage coalition formation algorithm. For the minimum energy consumption objective, we solved it by modeling the problem as a zero-one integer programming problem and using the existing solver. For the minimum mission time and energy consumption objective, we proposed a resource tree-based algorithm. Through simulation experiments, we verified that our proposed algorithms is feasible and effective.In the future, we intend to consider the impact of time-varying communication network on online task allocation. The UAVs are always in flight and have limited communication ranges. Therefore, the coalition is formed in a time-varying network. It takes some time to transmit and process the message, which will affect the calculation of the time and energy consumption of UAV to reach the target.



---

*Source: 5516086-2021-08-02.xml*