# Distributed Task Allocation for Multiple UAVs Based on Swarm Benefit Optimization
## 3 Method
### Basic Idea  
Firstly, the concept of individual benefit variation is introduced to quantify the effect of a task on the benefit of a single UAV. It is defined as follows:  
\[\kappa_{ij}=|B(\mathbf{a}_{i}\pm\{j\})-B(\mathbf{a}_{i})|,\ \ \ \forall j\in \mathcal{J},\ \ \ \forall i\in\mathcal{I} \tag{7}\]  
where \(\kappa_{ij}\) represents the individual benefit variation of task \(j\) for UAV \(i\). It is defined as the difference between the benefit of the allocation result \(B(\mathbf{a}_{i}\pm\{j\})\), obtained by either adding or removing task \(j\) from UAV \(i\)'s original allocation \(\mathbf{a}_{i}\), and the benefit of the original allocation \(\mathbf{a}_{i}\). The function \(B(*)\) denotes the individual benefit of a given allocation result.  
When task \(j\) is not included in the set of tasks \(\mathbf{a}_{i}\) selected by UAV \(i\), i.e., \(j\
otin\mathbf{a}_{i}\), Equation (7) can be modified as follows:  
\[\kappa_{ij}^{+}=B(\mathbf{a}_{i}+\{j\})-B(\mathbf{a}_{i})=\max_{n\leq\overline {n}}B(\mathbf{a}_{i}+_{n}\{j\})-B(\mathbf{a}_{i}),\ \ \ \forall j\in\mathcal{J},\ \ \ \forall i\in \mathcal{I} \tag{8}\]  
where the notation \(\mathbf{a}_{i}+_{n}\{j\}\) signifies the insertion of task \(j\) into the \(n\)-th position of the task allocation plan \(\mathbf{a}_{i}\) for UAV \(i\). If multiple potential insertion points exist within UAV \(i\)'s task allocation plan for task \(j\), the optimal insertion should occur at the position yielding the maximum individual benefit.  
When task \(j\) is already included in the set of tasks \(\mathbf{a}_{i}\) selected by UAV \(i\), i.e., \(j\in\mathbf{a}_{i}\), Equation (7) can be transformed as follows:  
\[\kappa_{ij}^{-}=B(\mathbf{a}_{i})-B(\mathbf{a}_{i}-\{j\}),\ \ \ \forall j\in \mathcal{J},\ \ \ \forall i\in\mathcal{I} \tag{9}\]  
where \(\mathbf{a}_{i}-\{j\}\) denotes the task sequence obtained after removing task \(j\) from its task allocation plan \(\mathbf{a}_{i}\).  
Indeed, for the same UAV \(i\), if only task \(j\) varies within its task plan while all other tasks remain constant, the computed variation in individual benefit for UAV \(i\) will be identical. That is, under the condition where \(\Delta(\mathbf{a}_{i})=j\), the following equation holds true:  
\[\kappa_{ij}=\kappa_{ij}^{+}=\kappa_{ij}^{-},\ \ \ \forall j\in\mathcal{J},\ \ \ \forall i\in\mathcal{I} \tag{10}\]  
Since the swarm benefit is an aggregation of individual benefits, to augment the incremental contribution of a specific task \(j\) to this swarm benefit, the following conditions must be met:  
\[\kappa_{ij}^{-}<\kappa_{kj}^{+},\ \ \ \forall j\in\mathcal{J},\ \ \ \forall i,k\in \mathcal{I} \tag{11}\]  
In other words, the transfer of task \(j\) from UAV \(i\) to UAV \(k\) within their respective task allocation plan will lead to an elevation in the overall efficiency of the UAV swarm, provided that the reduction in individual benefit resulting from the removal of task \(j\) from UAV \(i\) is less than the increase in individual benefit stemming from the addition of task \(j\) to UAV \(k\). By employing this method, an optimization of Problem (1) is achieved.