# Efficient Task Allocation in Multi-Agent Systems Using Reinforcement Learning and Genetic Algorithm
## 3 Problem Formulation
### System Model  
Suppose there exist a set of agents formed by \(N=\{1,2,\ldots,n\}\) and a set of tasks formed by \(S=\{1,2,\ldots,m\}\). An agent cannot participate in multiple tasks simultaneously. The task allocation problem in this multi-agent system can be formulated by defining the strategy space for each agent. Let \(\{S\}_{i}\) represent the task selected by agent \(i\in N\), and let \(\{I\}_{j}\) represent the set of agents allocated to task \(j\in S\). Each task \(j\) is positioned at a fixed location \(pos_{j}=(x_{j},y_{j},z_{j})\), defined by its three-dimensional coordinates. The position of agent \(i\), \(pos_{i}\), coincides with the position of the task it selects. The Euclidean distance between agent \(i\) and task \(j\) is expressed as  
\[d_{ij}=\|\text{pos}_{i}-\text{pos}_{j}\|. \tag{1}\]  
Here, \(d_{ij}\) also represents a constraint on the communication range of the agents. Specifically, an agent can only access tasks or interact with other agents that are within its communication range, as determined by \(d_{ij}\).  
The workload of task \(j\), represented as \(h_{j}\geq 0\), represents the total effort required to complete the task through the combined efforts of the agents. The work ability of agent \(i\) is represented by \(\omega_{i}\), indicating the amount of work that agent \(i\) can execute per unit time. For task \(j\), the work ability of the group allocated to the task is defined as the sum of the work capacities of all agents in that group \(\sum_{i\in I_{j}}\omega_{i}\). To complete task \(j\), the total work ability of the allocated group must satisfy  
\[\sum_{i\in\{I\}_{j}}\omega_{i}-h_{j}\geq 0. \tag{2}\]  
For each task \(j\in S\), it is crucial to allocate an appropriate number of agents to satisfy (2) and thereby minimize resource wastage due to inefficient allocations. Thus, the reward for task \(j\) is expressed as  
\[R_{j}=-\tau^{\sum_{i\in\{I\}_{j}}\omega_{i}-h_{j}}, \tag{3}\]  
where discount factor \(\tau\in(0,1)\) represents the rate of change in reward based on the work ability of the group \(\{I\}_{j}\). It also indicates the timeliness of the task. When \(\tau\) approaches one, the reward continues to increase even if (2) is satisfied, encouraging more agents to participate and thereby speeding up task completion. Conversely, when \(\tau\) approaches 0, the reward \(R_{j}\) becomes insensitive to the (2), meaning no additional agents would gain rewards from the task once the condition is satisfied.  
Figure 1: Adaptive task-oriented GA-PPO for agent swarms algorithm.  
The objective of the task allocation problem is to identify an optimal allocation that minimizes the total completion time \(T=\max\{T_{1},T_{2},\ldots,T_{m}\}\), where the completion time for task \(j\) is expressed as  
\[T_{j}=\frac{h_{j}}{\sum_{i\in\{I\};\mu i_{j}}}. \tag{4}\]  
Therefore, the problem can be formulated as follows:  
\[\begin{split}&\min_{\{e_{ij}\}}\{T_{j}\},\\ &\text{s.t.}\quad\sum_{j=1}^{m}e_{ij}\leq 1,\quad\forall i\in N,\\ & e_{ij}\in\{0,1\},\quad\forall i\in N,\forall j\in S,\end{split} \tag{5}\]  
where \(e_{ij}\) is a binary decision variable, if \(e_{ij}=1\) indicates that agent \(i\) is allocated to task \(j\); otherwise, agent \(i\) is not allocated to task \(j\).