# Cooperative Multi-Robot Task Allocation with Reinforcement Learning
## 5 Experiments
### Reinforcement Learning
When the problem is simple (i.e., with ten tasks), GA outperforms our model. This occurs because the search space becomes smaller when the problem is simpler and because near-optimal solutions can be found with a random exhausted search. On the other hand, the on-policy method finds improved solutions based on the current solution. Therefore, the improved solution can be biased with regard to the initial policy, which is randomly initialized. Therefore, meta-heuristic-based methods perform relatively well in simpler problems. However, the performance difference (when the number of tasks is 10) is marginal and the proposed method significantly outperforms the baselines in more complex cases (when the number of tasks is larger). We present the baseline reward and the on-policy reward while training. As shown in Figure 9, the baseline reward works as a lower bound for the on-policy reward, and the \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multicolumn{1}{c}{**\# Robots/ Tasks**} & **Algorithm** & \begin{tabular}{c} **Makespan** \\ **(20 m)** \\ \end{tabular} & \
\begin{tabular}{c} **Makespan** \\ **(40 m)** \\ \end{tabular} &
\begin{tabular}{c} **Makespan** \\ **(1 h)** \\ \end{tabular} \\ \hline \multirow{6}{*}{5/10} & IG & 144.9 & 142.5 & 141.2 \\  & SG & 147.7 & 147.1 & 147.1 \\  & RD & 137.2 & 136.9 & 136.9 \\  & GA & **132.5** & **132.1** & **132.0** \\  & PPO & 134.0 & 132.6 & 132.2 \\ \hline \multirow{6}{*}{5/20} & IG & 288.7 & 280.7 & 275.4 \\  & SG & 281.4 & 280.4 & 280.1 \\  & RD & 237.9 & 236.6 & 236.3 \\  & GA & **199.4** & 196.3 & 195.9 \\  & PPO & 200.0 & **192.9** & **188.8** \\ \hline \multirow{6}{*}{5/30} & IG & 427.9 & 418.3 & 413.6 \\  & SG & 416.1 & 414.3 & 413.8 \\  & RD & 357.6 & 355.8 & 355.5 \\  & GA & 299.8 & 282.9 & 279.2 \\  & PPO & **276.4** & **261.3** & **251.4** \\ \hline \multirow{6}{*}{5/40} & IG & 578.6 & 568.5 & 558.1 \\  & SG & 554.2 & 552.7 & 552.6 \\ \cline{1-1}  & RD & 480.0 & 478.3 & 477.4 \\ \cline{1-1}  & GA & 392.0 & 380.1 & 373.3 \\ \cline{1-1}  & PPO & **351.8** & **333.4** & **318.2** \\ \hline \multirow{6}{*}{5/50} & IG & 719.3 & 715.9 & 698.3 \\ \cline{1-1}  & SG & 696.1 & 694.9 & 694.6 \\ \cline{1-1}  & RD & 604.3 & 603.3 & 602.8 \\ \cline{1-1}  & GA & 502.3 & 483.6 & 473.2 \\ \cline{1-1}  & PPO & **429.7** & **408.0** & **394.5** \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Mean makespan of 100 problem instances for various number of tasks and allocation algorithms. The bold text indicates the best makespan among allocation algorithms. Figure 8: Boxplot of the makespan gap (\(\mathit{makespan_meta}-\mathit{makespan_{PPO}}\)) between PPO and meta-heuristic methods for each 100 samples in 5 robots, 50 tasks, and 1 h training. rates of increase for the two reward types are similar, as the improvement in the policy results in an improvement in the baseline and because the evaluation of the policy is based on the improved baseline. It is important to design an interpretable algorithm when devising a reliable autonomous allocation system. For example, the greedy algorithm selects tasks greedily and the overall plan is imaginable. However, the interpretation of the neural network is not intuitive even despite the fact that the RL based approach outperforms the baseline algorithms. We show a non-explainable property of our training scheme in Figure 10. We train a single instance of five robots and 50 tasks. There are no visual patterns that can be found despite the 38% performance gain from the 658 makespan to 412 makespan. Although the RL-based algorithm shows a significant performance gain with the complex problems, it is still difficult to understand the intention of the neural network. Figure 10: The disadvantage of end-to-end training. The first row represents the initial allocation of the PPO model and the second row represents the trained model. The makespan before training is 658 while the trained allocation has 412 makespan. Even though the makespan is reduced by 38%, the interpretation of the model is not trivial.