# Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time
## 3 Related Works
### Consensus-Based Bundle Algorithm (CBBA)
In the panel (b) of Figure 7, [PERSON] will complete the last mission, M22, at 63.83 s. In the panel (b) of Figure 8, [PERSON] will complete the last mission, M48, at 59.27 s, which is about 4.6 s lower than the results of CBBA. In the panel (b) of Figure 9, [PERSON] will complete the last mission, M49, at 56.76 s, which is about 7.1 and 2.5 s lower than the results of CBBA and TACTAR, respectively. The performance of the bundle adjustment step in the proposed algorithm can also be seen in the huge case. However, unlike the medium case, the number of missions each robot should conduct in Figures 7b and 9b are (10, 8, 8, 10, 7, 7) and (10, 10, 7, 7, 8, 8), respectively, which are similar to each other. It means that the bundle adjustment step in the proposed algorithm considers not only the number of missions but also the total mission time of each robot. Figure 4: The results for medium case using CBBA: (**a**) 2D situation map; (**b**) timetable. Figure 5: The results for medium case using TACTAR: (**a**) 2D situation map; (**b**) timetable. The calculation times of CBBA, TACTAR, and the proposed algorithm for the simple case are 0.1815 s, 0.0754 s, and 0.1636 s, respectively. Like the results for medium, the proposed algorithm has a lower computational cost than CBBA for the huge case. The computational cost is highly increased compared to the simple case, but it is still fast to run it in real-time. Figure 6: The results for medium case using proposed algorithm: (**a**) 2D situation map; (**b**) timetable. Figure 7: The results for huge case using CBBA: (**a**) 2D situation map; (**b**) timetable. Figure 8: The results for huge case using TACTAR: (**a**) 2D situation map; (**b**) timetable. Figure 9: The results for huge case using proposed algorithm: (**a**) 2D situation map; (**b**) timetable. ## 6 Conclusions

In this paper, we suggested a centralized mission planning algorithm of single/multiple robots for minimizing total mission completion time. First, we introduced the algorithm for single-robot-multi-mission (SRMM) problems, minimizing total mission completion time based on the bundle construction step in CBBA. In SRMM problems, which robot will take the mission was already decided, so it focused on how to decide the sequence of missions that the robot has to work on. Then, the algorithm was expanded for multi-robot-multi-mission (MRMM) problems. Unlike SRMM problems, it had to decide which robot will take the mission. However, it is hard to decide at once because the whole situation needs to be considered to minimize the total mission completion time. So, the initial bundles were constructed based on the expected finish time of each mission for robots and bundles and were adjusted iteratively. Finally, we demonstrated simulation results comparing them with CBBA and TACTAR, the existing mission planning algorithm, and the proposed algorithm. To verify the performance of these algorithms for various situations, we selected 3 cases: the simple case, which was composed of 3 robots and 8 missions, the medium case, which was composed of 4 robots and 30 missions, and the huge case, which was composed of 6 robots and 50 missions. The results showed that the proposed algorithm always outputs the mission plan that has the minimum total mission completion time. In addition, the computational cost of the proposed algorithm is lower than CBBA, and larger than TACTAR. However, the calculation time of our algorithm is fast enough to use in real-time applications. One of the limitations in our algorithm is that it cannot handle constraints like TACTAR. It is important because most users want to set constraints for various applications. The constraints are separated into two types: the spatial ones and the temporal ones. The spatial constraints are related to mission allocation. A typical spatial constraint is MUTual Exclusive (MUTEX). The temporal constraints are related to the mission alignment, e.g., mission time. The typical spatial constraints are 'Before', 'After', 'Simultaneous', etc.