# Distributed Task Allocation for Multiple UAVs Based on Swarm Benefit Optimization
## 3 Method
### Task Plan Construction  
Based on the aforementioned calculations of individual benefits and their variations, UAV \(i\) can determine the individual benefit variation \(\kappa^{+}_{ij}(\mathbf{a}_{i})\) generated by any feasible task \(j\) that is not currently included in its task allocation plan \(\mathbf{a}_{i}\). If there are multiple tasks \(j\) available for UAV \(i\) to add to its current plan, resulting in an increase in individual benefit, the task \(j^{*}\) that is selected is the one that maximizes the difference in its benefit variation compared to the maximum benefit variation among other UAVs in the swarm, which will result in the greatest swarm benefit increase according to Formula (11). \[j^{*}=\arg\max_{j}(\Delta\kappa^{+}_{ij}(\mathbf{a}_{i})),\quad\forall j\in \mathcal{J},\quad\forall i\in\mathcal{I} \tag{15}\]  
where \(\Delta\kappa^{+}_{ij}(\mathbf{a}_{i})=\kappa^{+}_{ij}(\mathbf{a}_{i})-\mathbf{ B}^{i}_{j}\) is the difference between the individual benefit variation of UAV \(i\) joining task \(j\) and the swarm benefit variation \(\mathbf{B}^{i}_{j}\) of the task \(j\) from the perspective of UAV \(i\) (swarm benefit variation is the current maximum individual benefit variation among the UAV swarm), and \(\Delta\kappa^{+}_{ij}(\mathbf{a}_{i})\) must meet condition \(\Delta\kappa^{+}_{ij}(\mathbf{a}_{i})>0\). In particular, when task \(j\) is not selected by any UAV in the swarm, the current swarm benefit variation of task \(j\) is zero, that is, \(\mathbf{B}^{i}_{j}=0\). The optimal task \(j^{*}\) selected is inserted into the position \(n^{*}\) of the task allocation plan \(\mathbf{a}_{i}\) of UAV \(i\), which is the position that generates the maximum of individual benefit variation, that is:  
\[n^{*}=\arg\max_{n\subset\overline{\mathbf{x}_{i}}}(\sum\zeta^{j^{ *}(\mathbf{a}_{i}+n(j))}_{j}-\sum\zeta^{j^{*}(\mathbf{a}_{i})}_{j}),\quad \forall j\in\mathcal{J},\quad\forall i\in\mathcal{I} \tag{16}\]  
Upon integrating a new task \(j^{*}\) into the task allocation plan \(\mathbf{a}_{i}\) of UAV \(i\), the current swarm benefit variation \(\mathbf{B}^{i}_{j^{*}}\) of the task \(j^{*}\) must be updated to the individual benefit variation of task \(j^{*}\) for UAV \(i\), i.e., \(\mathbf{B}^{i}_{j^{*}}=\kappa^{+}_{ij^{*}}(\mathbf{a}_{i})\). Concurrently, it is necessary to adjust the planned execution times \(\tau^{j}_{i}(\mathbf{a}_{i})\) for the subsequent tasks following task \(j^{*}\), to ensure precise calculation of individual benefit variations when these tasks are added to UAV \(i\)'s plan. When UAV \(i\) either exhausts all available tasks \(j^{*}\) that meet the criteria for inclusion in its task plan or reaches its maximum capacity for selected tasks, the process of task selection for UAV \(i\) terminates. Subsequently, the swarm benefit variations contributed by all tasks in UAV \(i\)'s task plan \(\mathbf{a}_{i}\) must be updated. This step is essential because the addition of new tasks to UAV \(i\)'s task plan \(\mathbf{a}_{i}\) alters the individual benefit values of all previously included tasks. Updating these values ensures that the current task plan accurately reflects the actual swarm benefit variations experienced by UAV \(i\), i.e.,  
\[\mathbf{B}^{i}_{j}=\sum\zeta^{j^{*}(\mathbf{a}_{i})}_{j}\bar{b}_{j}-\sum\zeta^ {j^{*}(\mathbf{a}_{i}-(j))}_{j}\bar{b}_{j},\quad\forall j\in\mathbf{a}_{i} \tag{17}\]  
The specific procedure for UAV \(i\) to select feasible tasks \(j^{*}\) and construct its task plan \(\mathbf{a}_{i}\) is outlined in Algorithm 1. When UAV \(i\) does not reach its maximum capacity for selected tasks (line 1), the process of task selection for UAV \(i\) continues (lines 2-8). Figure 1: A clear comparison between the distance-first approach and the benefit-first approach. Initially, according to Formula (13), calculate the individual benefit variations \(\kappa_{ij}^{+}\) for all task \(j\) (\(j=1,2,\ldots,N_{l}\)) performed by UAV \(i\) (line 2).