# Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time
## 3 Related Works
### Consensus-Based Bundle Algorithm (CBBA)
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Contents** & \multicolumn{3}{c}{**Specification**} \\
**\# of robots** & **Simple** & **Medium** & **Huge** \\ \hline \# of robots & 3 & 4 & 6 \\ \# of missions & 8 & 30 & 50 \\ Pos. of robots & [1, 0], [2, 0], [3, 0] & [1, 0], [1, 1], & [1, 0], [1, 1] \\  & & [3, 0], [3, 1] & [2, 0], [2, 1] \\  & & [\(-\)2, 3], [\(-\)4, 3] & & \\ Pos. of missions & [\(-\)4, 5.1], [\(-\)2, 5.2] & & \\  & [\(7\), 7], [9, 7] & & \\  & [9, 9.1], [7, 9.2] & & \\ Spd. of robots & 2 [m/s] for all & 2.0 [m/s], 1.5 [m/s], & 2.0 [m/s], 1.8 [m/s], \\  & 1.0 [m/s], 0.5 [m/s] & 1.6 [m/s], 1.4 [m/s], \\ Dur. of missions & 5 [s] for all & 2.1:0.1:5 [s] & 1.2 [m/s], 1.0 [m/s] \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The scenarios of simulations. (M01-M02-M03) and (M05-M06-M07), which are the closest missions to the R01 and R03, respectively. R02 will conduct M04 and M08, which were the last missions for R01 and R03, so the total mission completion time is minimized. Panel (b) in Figures 1-3 shows a timetable of each algorithm to easily check the mission completion time of each robot. The blue boxes mean the duration times of missions. The 'R', 'M', and the number after them have the same meanings as in the panel (a). In the panel (b) of Figures 1 and 2, R01 will complete the last mission, M07, at 25.37 s. So, the total mission completion times of CBBA and TACTAR are 25.37 s. In the panel (b) of Figure 3, R03 will complete the last mission, M07, at 21.08 s, which is about 4.3 s lower than the results of CBBA and TACTAR. The calculation times of CBBA, TACTAR, and the proposed algorithm for the simple case are 0.0055 s, 0.0068 s, and 0.0155 s, respectively. The computational cost of the proposed algorithm is about 2\(\sim\)3 times larger than the others, but it is still fast enough to run it in real-time. ### The Medium Case

The results of the medium case are shown in Figures 4-6. Figure 4 depicts the results of CBBA, Figure 5 depicts the results of TACTAR, and Figure 6 depicts the results of the proposed algorithm. Unlike the simple case, the mission plan result of CBBA is different to the result of TACTAR, as seen in Figures 4 and 5. R01 will conduct M13 and go to M08 in Figure 4a, while it will conduct M13 and go to M02 in Figure 5a. In Figure 6a, R01 will initially conduct the same mission as the result of CBBA, M13-M08-M10. However, R01 will conduct M01 after finishing M10 in Figure 6a, while it will conduct M26 in Figure 4a. The mission plans of R02-04 calculated by the algorithms are very different. Panel (b) in Figures 4-6 shows a timetable of each algorithm for the medium case. In the panel (b) of Figure 4, [PERSON] will complete the last mission, M24, at 67.30 s. In the panel (b) of Figure 5, [PERSON] will complete the last mission, M22, at 47.07 s, which is about 20.3 s lower than the results of CBBA. In the panel (b) of Figure 6, [PERSON] will complete the last mission, M04, at 44.59 s, which is about 22.8 and 2.5 s lower than the results of CBBA and TACTAR, respectively. The main reason is the bundle adjustment step in the proposed algorithm. The number of missions each robot should conduct in Figure 4b are 11, 11, 5, and 3. However, in the number of missions each robot should conduct in Figure 6b are 8, 6, 7, and 9. It means that the missions of the robots that need to conduct more missions are distributed to the robots that have fewer missions by the bundle adjustment step. The calculation times of CBBA, TACTAR, and the proposed algorithm for the simple case are 0.0436 s, 0.0199 s, and 0.0342 s, respectively. Unlike the results for the simple case, the proposed algorithm has a lower computational cost than CBBA for the medium case. The computational cost is slightly increased, but it is still fast to run it in real-time. Panel (b) in Figures 7-9 shows a timetable of each algorithm for the huge case.