# Cooperative Multi-Robot Task Allocation with Reinforcement Learning
## 3 Problem Formulation
### Markov Decision Process Formulation
#### 3.2.2 Inner Environment  
The robots take one of actions (working or moving) in the inner environment. We first describe how to encode the information of the robots and tasks. Coordinates \((x_{i}^{r},y_{i}^{r})\) and \((x_{i}^{t},y_{i}^{t})\) denote positions of robots and tasks. The state information of robot \(r_{i}\) is one of _ready_, _going_ and _working_. The state information of task \(t_{j}\) is one of _done_ and _remaining_. \((task(r_{i}).x,(task(r_{i}).y)\) is the x,y coordinates of allocated task of robot \(r_{i}\). If there is no allocation of task to robot \(r_{i}\), \((task(r_{i}).x,(task(r_{i}).y)=(0,0)\). Since the problem is cooperative, there could be multiple robots working on and coming to the task \(t_{j}\). The allocation must consider the existence of robots on task \(t_{j}\), so that we can prevent unnecessary allocation (when the allocated task is done before reaching to the position) and encourage cooperation. Therefore we encode two types of information, \(work(t_{j})\) and \(com(t_{j})\). \(work(t_{j})\) is the number of working robots on task \(t_{j}\) so that we can know when the task finishes. \(com(t_{j})\) is a set of distances whose element is \(d(r_{i},t_{j})\) for robot \(r_{i}\) coming to the task \(t_{j}\). We give mean and variance of distances coming to the task and \(0\) for each value if there is no robot coming to the task. The overall encoded information \(\{R_{1},\cdots R_{m}\}\) and \(\{T_{1},\cdots,T_{n}\}\) are shown in Equations (15) and (16) for robots and tasks.  
\[R_{i}=[x_{j}^{r},\ y_{j}^{r},\ state_{j}^{r},\ task(r_{j}).x,\ task(r_{j} ).y] \tag{15}\]  
\[T_{j}=[x,\ y,\ state,\ w(t_{j}),\ work(t_{j}),\ Mean(com(t_{j})),\ Var(com(t_{j}))] \tag{16}\]  
A single time step of the inner environment is \(1\) unit time behavior which means robot \(r_{i}\) moves \(1\) unit distance when moving to task \(t_{j}\) and reduces the workload \(w(t_{j})\) by \(1\) when working on task \(t_{j}\). In the mathematical formulation of the problem, The start time and finish time are real values in MIP formulation. Therefore, the discrete environment does not match with the problem formulation. However, the two become more similar when the unit time approaches 0. By considering the gap between the formulation and the environment, we assume that the robot has reached the task when the distance \(d(r_{i},t_{j})\) of allocated task \(t_{j}\) is less than some small positive value \(\epsilon\). When the robot reaches the task, we change the state of robot \(r_{i}\) from moving to working. This change of state is described in line (11) in Algorithm 1. Even though the inner environment can be formulated by MDP, we do not train the robots because the goal of our paper is training task allocation method, not individual robots. The episode of the inner environment starts when there is no \(\mathcal{R}_{ready}\) and runs until there are some robots who finished the assigned task. When a task is finished, the robots that worked on the task become idle and they are allocated to new tasks in \(\mathcal{T}_{remaining}\). We designed this hierarchical architecture of environment for future study, where not only the outer MDP formulation is trained but also the robots are also trained.