# Cooperative Multi-Robot Task Allocation with Reinforcement Learning
## 3 Problem Formulation
### Markov Decision Process Formulation
#### 3.2.1 Allocation Environment  
The role of the allocation environment is to allocate robot \(r_{i}\) to task \(t_{j}\). We formulate the allocation environment as follows. The observation is the encoded information of \(n\) robots and the remaining tasks \(\mathcal{T}_{remaining}\). The reward \(r(s_{t})\) is a sparse reward with a penalty _-makespan_ at the end of an episode. The episode finishes when there are no remaining tasks.  
\[r(s_{t})=\begin{cases}-makespan&\text{if }s_{t}=terminal\\ 0&otherwise\end{cases} \tag{14}\]  
We define \(\mathcal{T}_{remaining}\) as a set of remaining tasks whose workload is larger than 0, \(\mathcal{T}_{finished}=\mathcal{T}\setminus\mathcal{T}_{remaining}\) as a set of finished tasks and \(\mathcal{R}_{ready}\) as a set of ready robots which are waiting to be allocated. A single time step of the environment is allocation of robot \(r_{i}\in\mathcal{R}_{ready}\) as described in Figure 2. Since we allocate only one robot in a single time step, it requires \(m\) successive environment time steps for the \(m\) ready robots. This successive allocation is denoted in the lines (4-6) in Algorithm 1. Therefore, the action \(A_{t}\) is a mapping \(A_{t}=r_{i}\to t_{j}\). Since a target task should be one of tasks in \(\mathcal{T}_{remaining}\), we use the notation \(Allocate(r_{i},\mathcal{T}_{remaining})\) to describe the allocation of robot \(r_{i}\) in Algorithm 1. Note that this environment is working independently from the real simulation of robots and is only responsible for the allocation of robots.  
Figure 1: Time steps of an example episode. The time step of the allocation environment is denoted by \(T_{i}\) and the time step of the inner environment is denoted by \(t_{i}^{i}\). In this example, the allocation algorithm has allocated robots 3 times and _makespan_ is \(12=(5+3+4)\).  
Figure 2: A single time step of the allocation environment. When the allocation algorithm gives action \(A_{t}\) to the environment, the environment gives the next state and reward pair \((S_{t+1},R_{t+1})\). When we simulate the environment, robots \(\{R_{1},R_{2},R_{3},R_{4}\}\) choose actions in the inner environment which is also form of MDP. The allocation algorithm decides which task \(t_{j}\) in \(\mathcal{T}_{remaining}\) is assigned to the given robot \(r_{i}\) in \(\mathcal{R}_{ready}\). In this example, \(\mathcal{R}_{ready}=\{R_{3},R_{4}\}\), \(\mathcal{T}_{remaining}=\{T_{1},T_{2},T_{3}\}\), and the given robot is \(R_{4}\). The algorithm allocates the robot \(R_{4}\) to task \(T_{3}\). After allocation, the inner environment runs until there is another ready robot. In this case, robot \(R_{3}\) is another ready robot and next allocation happens immediately. Best viewed in color.  
```
1:Inputs:
2:Robots \(\mathcal{R}\), Tasks \(\mathcal{T}\),workload \(w(t)\), distance function \(d(\cdot,\cdot)\), work distance \(e\)
3:Initialize:
4:\(\mathcal{R}_{ready}\leftarrow\mathcal{R}\)
5:\(\mathcal{T}_{remaining}\leftarrow\mathcal{T}\)
6:\(\mathcal{T}_{finished}\leftarrow\mathcal{O}\)
7:while\(\mathcal{T}_{remaining}\) is not \(\emptyset\)do# begin allocation episode
8:for\(r_{i}\) in \(\mathcal{R}_{ready}\)do
9:\(r_{i}\).task = Allocate(\(r_{i}\), \(\mathcal{T}_{remaining}\))
10:\(\mathcal{R}_{ready}=\mathcal{R}_{ready}\setminus\{r_{i}\}\)
11:endfor
12:while\(\mathcal{R}_{ready}\) is \(\emptyset\)do# begin inner environment episode
13:for\(r_{i}\) in \(\mathcal{R}\)do
14:\(t=r_{i}\).task
15:if\(d(r_{i},t)\leq e\)then
16:\(w(t)=w(t)-1\)
17:else
18:\(r_{i}\).\(x=r_{i}\).\(x+u_{x}\)
19:\(r_{i}\).\(y=r_{i}\).\(y+u_{y}\)
20: where \(u_{x}=(t.x-r_{i}.x)/d(r_{i},t)\) and \(u_{y}=(t.y-r_{i}.y)/d(r_{i},t)\)
21:endif
22:if\(w(t)\leq 0\)then
23:\(\mathcal{R}_{ready}=\mathcal{R}_{ready}\cup\{r_{i}\}\)
24:\(\mathcal{T}_{finished}=\mathcal{T}_{finished}\cup\{t\}\)
25:\(\mathcal{T}_{remaining}=\mathcal{T}_{remaining}\setminus\{t\}\)
26:endif
27:endfor
28:endwhile
```  
**Algorithm 1** Allocation Algorithm in MDP