# A Hierarchical Mission Planning Method for Simultaneous Arrival of Multi-UAV Coalition
## 3 Task Allocation
### Task Allocation Algorithm  
The task allocation process defined in Section 2.2 is a Non-deterministic Polynomial hard problem. With the increasing size of the problem, the computational complexity will be increased sharply. It will be time-consuming and even impossible to obtain the optimal solution. In order to obtain a feasible solution within a reasonable time, in this paper, the task allocation algorithm assigns the most profitable target in each allocation round. In each allocation round, each UAV selects the most beneficial target to itself. Then, if there is a conflict among different UAVs, a consensus mechanism is used. The resource requirement of targets and task sequence of UAVs were considered. As mentioned above, the task allocation and path planning were coupled. In this paper, the path estimation process using the PH curve was used to decouple these two problems. The proposed task allocation algorithm based on a negotiation mechanism is presented as Algorithm 1. ```
0:\(T\): The set of targets and initial states; \(R^{T_{j}}\), \(j=1,\ldots,M\): Resource requirement of targets; \(U\): The set of UAVs and initial states; \(R^{U_{i}},i=1,\ldots,N\): Resources of UAVs;
0:\(A\): The allocation matrix of the UAV team
1:for\(k=1:M\)do
2:for\(U_{i},i=1,\ldots,N\)do
3:for\(j=1\)to the number of unallocated targets
4: calculate estimated reward for \(U_{i}\) performing target \(T_{j}\)
5:endfor
6: select the pre-allocated target for \(U_{i}\)
7:endfor
8: consensus on pre-allocated target in this allocation round and select the manner UAV
9:\(C_{j}\leftarrow\) coalition_formation \((U_{j}^{P},Va_{j},R^{T_{j}})\) --Algorithm 2
10: the UAVs in the coalition \(C_{j}\) add the target \(T_{j}\) into their task sequence
11: calculate resource consumption for UAVs in the coalition \(C_{j}\)
12: cooperative path planning for simultaneous arrival to target \(T_{j}\) --Section 4
13:endfor
```  
**Algorithm 1** Task allocation algorithm  
Figure 1: Integration framework of task allocation, path planning and path following. There were \(M\) targets at the initial time, each allocation round would assign one target (Line 1, Algorithm 1). Then, the estimated reward to perform all unallocated targets was calculated for each UAV using Equation (14; Line 4, Algorithm 1). Considering the task sequence of a UAV, the ETA of the UAV \(U_{i}\) to the target \(T_{j}\) can be represented as Equation (15). \[Reward(i,j)=Value_{j}\times e^{-\beta ETA(i,j)} \tag{14}\]  
\[ETA(i,j)=\left\{ \begin{array}{ll}L_{ij}^{e}/V_{i},&if\ A^{(i)}=\varnothing\\ L_{im}^{before}/V_{i}+L_{mj}^{e}/V_{i},&otherwise\end{array} \right. \tag{15}\]  
where \(A^{(i)}\) is the task sequence of the UAV \(U_{i}\), if \(A^{(i)}=\varnothing\), which denotes there is no target assigned to the UAV \(U_{i}\), then \(L_{ij}^{e}\) is the estimated path length between the current location of the UAV \(U_{i}\) to target \(T_{j}\), which can be obtained in the path estimation process (Section 4.2). Otherwise, there has been some targets assigned to the UAV \(U_{i}\), these assigned targets should be considered in calculating the \(ETA(i,j)\). Assuming the last target in the task sequence of UAV \(U_{i}\) is the target \(T_{m}\), the ETA from UAV \(U_{i}\) to the target \(T_{j}\) can be divided into two parts. The first part is the accurate path length of the assigned targets \(L_{im}^{before}\), which can be obtained by the path planning process (Section 4.3) in the previous allocation round; the second part \(L_{ij}^{e}\) is the estimated path length from the target \(T_{m}\) to \(T_{j}\), which can be obtained in the path estimation process. Then, the UAV \(U_{i}\) selects the most appropriate target \(j^{*}\) as its pre-allocated target (Line 6 Algorithm 1):  
\[j_{i}^{*}=\operatorname*{argmax}_{j\in M^{\prime}}(Reward(i,j)) \tag{16}\]  
where \(M^{\prime}\) represents the targets, which have not been assigned. After all the UAVs have computed their pre-allocated targets, there may be conflicts among UAVs.