# Cooperative Multi-Robot Task Allocation with Reinforcement Learning
## 3 Problem Formulation
### Mixed Integer Programming Formulation  
In Equations (2)-(13), we describe the mixed integer programming (MIP) formulation of the cooperative ST-MR-TA problem following [26]. There are \(\mathcal{T}\), a set of \(n\) tasks with x,y coordinates and workload \(w(t_{j})\) for each task \(t_{j}\) and \(\mathcal{R}\), a set of \(m\) robots with x,y coordinates. We add initial task \(t_{0}\) of workload 0 at coordinates (0,0) which is the initial location of robots. Additionally, robot \(r_{i}\) can have battery constraint \(b(r_{i})\). The distance between two objects in the map is denoted by \(d(\cdot,\cdot)\) which is Euclidean distance. The variables \(S^{r_{i}}_{t_{j}}\) and \(F^{r_{i}}_{t_{j}}\) are continuous variables represents start time and finish time of work on task \(t_{j}\) by robot \(r_{i}\). The start time and finish time are 0 if robot \(r_{i}\) is not allocated to task \(t_{j}\). The binary variable \(A^{r_{i}}_{t_{j}}\) is 1 if task \(t_{j}\) is assigned to robot \(r_{i}\) and the binary variable \(X^{r_{i}}_{t_{j},k}\) is 1 if robot \(r_{i}\) performs task \(t_{j}\) followed by \(t_{k}\).  
The constraints for the MIP formulation are described in Equations (2)-(13). Equation (2) is the objective of the problem. We add another variable \(F_{last}\) which is greater than or equal to finish time \(F^{r_{i}}_{t_{j}}\) and minimize it for all robots \(r_{i}\in\mathcal{R}\) and tasks \(t_{j}\in\mathcal{T}\) in Equation (3).  
Equations (4)-(6) are the domain of each variable. Equation (7) ensures the cumulative work time on task \(t_{j}\) for all robots is larger than the workload \(w(t_{j})\) of task \(t_{j}\). Equation (8) forces start time \(S_{t_{j}}^{r_{j}}\) and finish time \(F_{t_{j}}^{r_{j}}\) to be 0 if indexed task \(t_{j}\) is not allocated to robot \(r_{i}\). The very large number \(M\) is used for the conditional trick. Equation (9) ensures that travel time of a successive task allocation is bounded by the distance of two allocated tasks. Equations (10) and (11) are used to match the allocation variable \(A_{t_{k}}^{r_{i}}\) and the successive allocation variable \(X_{t_{j},t_{k}}^{r_{i}}\). Equation (12) indicates the initial position for every robot \(r_{t}\in\mathcal{R}\). Equation (13) is optional for a battery constraint.  
minimize: \[F_{last}\] (2) subject to: \[F_{t_{j}}^{r_{i}}\leq F_{last},\;\forall t_{j}\in\mathcal{T},\;r_{i}\in \mathcal{R}\] (3) \[A_{t_{j}}^{r_{i}}\in\{0,1\},\;\forall t_{j}\in\mathcal{T},\;r_{i} \in\mathcal{R}\] (4) \[X_{t_{j},t_{k}}^{r_{i}}\in\{0,1\},\;\forall t_{j},t_{k}\in \mathcal{T},\;r_{i}\in\mathcal{R}\] (5) \[0\leq S_{t_{j}}^{r_{j}}<\infty,\;0\leq F_{t_{j}}^{r_{j}}<\infty, \;\forall t_{j}\in\mathcal{T},\;r_{i}\in\mathcal{R}\] (6) \[\sum_{r_{i}}F_{t_{j}}^{r_{i}}-S_{t_{j}}^{r_{i}}\geq w(t_{j}),\; \forall t_{j}\in\mathcal{T},\;r_{i}\in\mathcal{R}\] (7) \[S_{t_{j}}^{r_{i}}+F_{t_{j}}^{r_{i}}\leq M\cdot A_{t_{j}}^{r_{i}}, \;\forall t_{j}\in\mathcal{T},\;r_{i}\in\mathcal{R}\] (8) \[F_{t_{j}}^{r_{i}}+d(t_{j},t_{k})-M(1-X_{t_{j},t_{k}}^{r_{i}}) \leq S_{t_{j}}^{r_{i}},\;\forall t_{j},\;t_{k}\in\mathcal{T},\;r_{i}\in \mathcal{R}\] (9) \[\sum_{t_{j}}X_{t_{j},t_{k}}^{r_{i}}=A_{t_{k}}^{r_{i}},\;\forall t _{j},t_{k}\in\mathcal{T},\;r_{i}\in\mathcal{R}\] (10) \[\sum_{t_{k},\;k\
eq 0}X_{t_{j},t_{k}}^{r_{i}}=A_{t_{j}}^{r_{i}},\; \forall t_{j},t_{k}\in\mathcal{T},\;r_{i}\in\mathcal{R}\] (11) \[A_{t_{0}}^{r_{i}}=1,\;\forall r_{i}\in\mathcal{R}\] (12) \[\sum_{t_{j},t_{k}}d(t_{j},t_{k})X_{t_{j},t_{k}}^{r_{i}}\leq b^{r_{ i}},\;\forall t_{j},t_{k}\in\mathcal{T},\;r_{i}\in\mathcal{R}\] (13)