# Distributed Task Allocation for Multiple UAVs Based on Swarm Benefit Optimization
## 2 Problem Formulation  
The task allocation problem for UAV swarms is essentially an optimization problem, revolving around how to allocate a finite number of UAV resources to various swarm tasks. Typically, solving this problem primarily involves optimizing the swarm's benefit, while also considering the constraints of both the UAVs and the tasks. A UAV only contributes effective benefits when it can accomplish tasks without violating these constraints. Based on this, the problem can be formalized into the following mathematical model:  
\[\max\sum_{i=1}^{N_{u}}\left(\sum_{j=1}^{N_{t}}b_{ij}(\mathbf{a}_{i})\right) \tag{1}\]  
subject to:  
\[\overline{\overline{\mathbf{a}}_{i}}\leq L_{i},\quad\forall i\in\mathcal{I} \tag{2}\]  
\[\sum_{i=1}^{N_{u}}\overline{\overline{\mathbf{a}}_{i}}=J_{min},\quad\forall i \in\mathcal{I} \tag{3}\]  
\[\sum_{j=1}^{\overline{\mathbf{a}}_{i}}c_{ij}(\mathbf{a}_{i})\leq C_{i},\quad \forall i\in\mathcal{I} \tag{4}\]  
\[\mathbf{a}_{i}\cap\mathbf{a}_{k}=\emptyset,\quad\forall i\
eq k\in\mathcal{I} \tag{5}\]  
\[t_{ij}(\mathbf{a}_{i})\leq d_{j},\quad\forall i\in\mathcal{I},\quad\forall j\in \mathcal{J} \tag{6}\]  
where \(i\) and \(j\) denote the indices for UAVs and tasks, respectively, and \(\mathcal{I}\) and \(\mathcal{J}\) denote the sets consisting of all UAV indices \(i\) and task indices \(j\). \(N_{u}\) denotes the number of UAVs, \(N_{t}\) denotes the number of tasks. The symbol \(\mathbf{a}_{i}\) signifies the task sequence of UAV \(i\), which is derived from the ordered set of tasks selected by UAV \(i\), and \(\overline{\overline{\mathbf{a}}_{i}}\) signifies the cardinality of the set \(\mathbf{a}_{i}\), i.e., the number of tasks that UAV \(i\) is assigned to execute. \(b_{ij}\) indicates the benefit accrued when UAV \(i\) undertakes task \(j\). \(L_{i}\) delineates the maximum number of tasks that UAV \(i\) can accomplish. The term \(J_{min}\) represents the maximum number of tasks that the UAV swarm can complete, defined as \(J_{min}\stackrel{{\Delta}}{{=}}min\{N_{t},N_{u}L_{i}\}\), which is determined by the maximum total number of tasks, \(N_{u}L_{i}\), that can be completed by \(N_{u}\) UAVs and the original number of tasks, \(N_{t}\), specifically taking the minimum value between the two. The function \(c_{ij}(\mathbf{a}_{i})\) signifies the energy consumption required for UAV \(i\) to execute task \(j\) according to its task sequence \(\mathbf{a}_{i}\), while \(C_{i}\) represents the maximum energy consumption that UAV \(i\) can sustain. The function \(t_{ij}(\mathbf{a}_{i})\) specifies the time at which UAV \(i\) commences task \(j\) according to its task allocation plan \(\mathbf{a}_{i}\), and \(d_{j}\) denotes the latest permissible start time for task \(j\).  
Constraints (2)-(4) pertain to the limitations of individual UAVs. Specifically, constraint (2) stipulates that the number of tasks selected by UAV \(i\) must not exceed its maximum task capacity. Constraint (3), on the other hand, dictates that the total number of tasks accomplished by the UAV swarm, comprising \(N_{u}\) UAVs, equates to \(J_{min}\) tasks. Constraint (4) stipulates that the total energy consumption required for UAV \(i\) to execute all tasks in its task sequence must not exceed the maximum energy capacity that it can endure. Meanwhile, Constraints (5) and (6) address the restrictions related to task allocation. Constraint (5) ensures that no two UAVs, \(i\) and \(k\), within the swarm select the same task. Constraint (6) mandates that UAV \(i\) must commence task \(j\) before its latest permissible execution time.