# Efficient Task Allocation in Multi-Agent Systems Using Reinforcement Learning and Genetic Algorithm
## 3 Problem Formulation
### State Action Model  
In our agent swarm framework, each agent's transition at time \(t\) is represented by the tuple \((s_{t},a_{t},r_{t},s_{t+1})\), where the following hold:  
* \(s_{t}\) denotes the agent's current state, which is a composite representation consisting of the following:
* The agent's location \(\text{pos}_{i}=(x_{i},y_{i},z_{i})\), providing the agent's spatial position in the environment. This information is essential for determining the agent's proximity to tasks and other agents, which influences both task allocation and collision avoidance. * Task-related information, including task priorities, workload status, and the agent's assigned task. This information allows the agent to evaluate its current workload and adjust its decisions based on the urgency and importance of tasks within its scope. * The occupancy map, encoding the spatial distribution of tasks and agents within the agent's communication or sensing range. This map helps the agent understand its environment by providing real-time updates on the locations of other agents and tasks, enabling more informed decisions on task allocation and collaboration with other agents. * \(a_{t}\) is the action selected by the agent in state \(s_{t}\). The action is defined as the selection of a task \(j\in S\), where \(S\) represents the set of available tasks. Formally, \[a_{t}=\arg\max_{j\in\mathcal{C}(i)}\pi(s_{t},j),\] (6) where \(\pi(s_{t},j)\) is the policy function that outputs the probability of selecting task \(j\) given the current state \(s_{t}\), and \(\mathcal{C}(i)\) is the set of tasks within the communication or sensing range of agent \(i\). If no tasks are feasible, the agent may choose an idle action. The policy function \(\pi(s_{t},j)\) is learned using the Actor-Critic architecture, where the Actor is responsible for selecting actions based on the current state, while the Critic evaluates the actions taken by estimating the value function. Specifically, the Actor network takes the current state \(s_{t}\) as input and outputs a probability distribution over possible actions (tasks). The policy function \(\pi(s_{t},j)\) is expressed as \[\pi(s_{t},j)=P(a_{t}=j\mid s_{t}),\] (7)where \(a_{t}\) is the action selected by the agent at time step \(t\), and \(j\) is a task from the set of available tasks \(\mathcal{C}(i)\). The Critic, on the other hand, estimates the expected cumulative reward for the agent starting from state \(s_{t}\). This is achieved through the value function \(V(s_{t})\), which represents the expected long-term reward given the current state. It is formally expressed as  
\[V(s_{t})=\mathbb{E}\left[\sum_{k=t}^{T}\gamma^{k-t}r_{k}\mid s_{t}\right], \tag{8}\]  
where \(r_{k}\) is the reward received at time step \(k\), and \(\gamma\) is the discount factor that determines the importance of future rewards. At each time step, the agent selects an action \(a_{t}\) based on the policy \(\pi(s_{t},j)\) by maximizing the probability of selecting a task from the set \(\mathcal{C}(i)\) based on the current state \(s_{t}\). The interaction between the Actor and Critic helps in continuously optimizing the policy, with the Critic providing feedback on the expected rewards, guiding the Actor to improve its decision-making over time. If no feasible tasks are within the agent's sensing or communication range, the agent may choose an idle action, which corresponds to not selecting any task. This idle action is implicitly represented within the action space, where one of the actions is designated as \"idle\". * \(r_{t}\) represents the reward obtained after executing action \(a_{t}\). This reward reflects the agent's contribution to task completion, considering factors such as task importance, completion effectiveness, and collaborative efficiency with other agents. * \(s_{t+1}\) is the subsequent state resulting from the agent's interaction with the environment after performing \(a_{t}\).