# Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time
## 3 Related Works
### Consensus-Based Bundle Algorithm (CBBA)
```
1:\(t^{e}_{max,prev}=max(\mathbf{t}^{e})\)
2:\(\mathbf{b}_{prev}=\mathbf{b}\)
3:while 1
4:\(i_{max}=argmax_{i}(t^{e}_{i})\)
5:for\(n=1:size(\mathbf{b}_{i_{max}})\)
6:\(\mathbf{b}_{i_{max}}=\mathbf{b}_{i_{max},prev}\)
7:\(|_{sl}(n)=\mathbf{b}_{i_{max}}(n)\)
8:\(\mathbf{b}_{i_{max}}=\mathbf{b}_{i_{max}}(-)\)
9:\(\mathbf{b}_{i}=\mathbf{b}_{i}(+)_{end}(\mathbf{l}_{sl}(n)),\forall i\in\mathbf{\Gamma}\backslash i _{max}\) if \(i\) can do \(j_{sl}(n)\)
10: calculate \(max(\mathbf{t}^{e}_{in})\) for \(\mathbf{b}\)
11:endfor
12:\(t^{e}_{max}=min\left(max(\mathbf{t}^{e}_{in})\right),\forall i\in\mathbf{\Gamma} \backslash i_{max}\)
13:\(i_{s}=argmin_{i}(max(\mathbf{t}^{e}_{in})),\forall i\in\mathbf{\Gamma}\backslash i _{max}\)
14:\(j_{s}=j_{sl}(argmin_{i}(max(\mathbf{t}^{e}_{in}))\)
15:if multiple \((i_{s},\,j_{s})\) that has same \(t^{e}_{max}\)
16: choose that has \(min\left(\max\left(t^{e}_{i_{max}},\,t^{e}_{i_{s}}\right)\right)\)
17:endif
18:if\(t^{e}_{max,prev}>t^{e}_{max}\)
19:\(t^{e}_{max,prev}=t^{e}_{max}\)
20:\(\mathbf{p}_{prev}=\mathbf{p}\)
21:else
22: break
23:endif
24:endwhile
```

**Algorithm 5** Adjust bundle

## 5 Result and Discussion

In this section, some simulation results are shown to assess the algorithm that we have proposed. We simulated three cases, a simple case, medium case, and huge case, to prove the performance of proposed algorithm. The simple case is composed of 3 robots and 8 missions, the medium case is composed of 4 robots and 30 missions, and the huge case is composed of 6 robots and 50 missions. The speed of all robots and the duration of all missions are equally set to 2 m/s and 5 s, respectively, to simplify the problem in the simple case. In the medium and huge cases, the speed of each robot and the duration time of each mission are set differently to represent the general situations. The detailed scenarios of simulations are described in Table 3.

CBBA and TACTAR are used to show that the proposed algorithm is improved over the existing algorithm. The total mission completion time and computational cost are set as performance indicators. We used OpenMP parallel computing to run each algorithm, and the computational cost of each algorithm is measured based on the result of the parallel computation. The environment of simulations is described in Table 4.

### The Simple Case

The results of the simple case are shown in Figures 1-3. Figure 1 depicts the results of CBBA, Figure 2 depicts the results of TACTAR, and Figure 3 depicts the results of the proposed algorithm. Panel (a) in Figures 1-3 shows the 2D situation map to easily check the mission plan result of each algorithm. The 'R' and 'M' means robot and mission, respectively. The following number means the index of robots and missions. The red lines mean the sequence of missions for each robot. For example, R01 will conduct M01, M03, and M07 sequentially, as seen in Figure 1a. As seen in Figures 1 and 2, the mission plan result of CBBA is absolutely the same as with the result of TACTAR. However, the mission plan result of the proposed algorithm is totally different to them. R01 and R03 will conduct \begin{table}
\begin{tabular}{c c} \hline \hline
**Contents** & **Specification** \\ \hline CPU & Intel® CoreTM i5-10500 3.10 GHz \\  & (6 cores, 12 threads) \\ GPU & Intel® UHD Graphics 630 \\ RAM & 16 GB \\ Storage & 256 GB SSD \\ Program & Calculation & Visual Studio Professional 2013 C++ \\  & Plotting & MATLAB 2018b \\ \hline \hline \end{tabular}
\end{table} 
Table 4: The environment of simulations.