# Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time
## 3 Related Works
### Consensus-Based Bundle Algorithm (CBBA)  
CBBA is one of the mission planning algorithms for the multi-robot-multi-mission problem. It is inspired by a decentralized auction process. CBBA is composed of two steps: the bundle construction step and the conflict resolution phase. In bundle construction step, robots make their mission lists, called a bundle, and decide their own sequence of missions assuming that each robot takes all missions. For this step, each agent calculates the rewards of the possible mission. The reward calculation scheme depends on the purpose of users. The procedure of bundle construction is as in Algorithm 1. ```
1:\(\textbf{\emph{Min}}\big{(}\text{Max}\big{(}t_{e}(j,\ p_{i})x_{ij}\big{)}\big{)}\)
2:\(\textbf{\emph{Min}}\big{(}\text{Max}\big



\(\mathbf{p}_{i}\), so the reward of the mission is the highest score difference \(\mathbf{S}_{i}^{\mathbf{p}_{i}(+)_{n}\{j\}}-\mathbf{S}_{i}^{\mathbf{p}_{i}}\) when the mission is added to the sequence. In line 7, the reward of the mission is compared to the winning bid of the mission. \(\mathbf{h}_{ij}\) is 1 if the reward is higher than the winning bid, and 0 otherwise. If the rewards of all possible missions are calculated, then the robot \(i\) chooses the mission that has the highest rewards. Finally, the chosen mission is added to the results of the current iteration. ```
1:\(\mathbf{y}_{i}(t)=\mathbf{y}_{i}(t-1)\)
2:\(\mathbf{z}_{i}(t)=\mathbf{z}_{i}(t-1)\)
3:\(\mathbf{b}_{i}(t)=\mathbf{b}_{i}(t-1)\)
4:\(\mathbf{p}_{i}(t)=\mathbf{p}_{i}(t-1)\)
5:while\(|\mathbf{b}_{i}|<L_{t}\),do
6:\(c_{ij}=max_{n\leq|\mathbf{p}_{i}|}\mathbf{S}_{i}^{\mathbf{p}_{i}(+)_{n}\{j\}}-\mathbf{S}_{i}^{ \mathbf{p}_{i}}\), \(\forall j\in\mathbf{J}\setminus\mathbf{b}_{i}\)
7:\(h_{ij}=\Pi\big{(}c_{ij}>y_{ij}\big{)}\), \(\forall j\in\mathbf{J}\)
8:\(JJ_{i}=argmax_{ij}\cdot h_{ij}\)
9:\(n_{i,JJ_{i}}=argmax_{n}\;\mathbf{S}_{i}^{\mathbf{p}_{i}(+)_{n}\{j\}}\)
10:\(\mathbf{b}_{i}=\mathbf{b}_{i}(+)_{\text{end}}\{[PERSON]_{i}\}\)
11:\(\mathbf{p}_{i}=\mathbf{p}_{i}(+)_{\text{nt}_{i,JJ_{i}}\{[PERSON]_{i}\}}\)
12:\(y_{i,JJ_{i}}(t)=c_{i,JJ_{i}}\)
13:\(z_{i,JJ_{i}}(t)=i\)
14:endwhile
```
**Algorithm 1** CBBA Phase 1: Bundle construction

The next step of CBBA is the conflict resolution step, which is making a decision on who will take the mission by comparing the rewards of each robot. Basically, CBBA is for a decentralized mission planning system, so two communicable robots decide the owner of missions following the rules described in Table 1.

If CBBA is used in centralized mission planning, the conflict resolution step based on the rules in Table 1 is replaced into the Sequential Greedy Algorithm (SGA). When the bundle construction step is performed, the rewards of missions for each robot are calculated

\begin{table}
\begin{tabular}{c c c} \hline \hline \begin{tabular}{c} **Robot \(k\)s** \\ **(Sender) \(\mathbf{z}_{kj}\) Is** \\ \end{tabular}  & \ \begin{tabular}{c} **Robot \(k\)s** \\ **(Sender) \(\mathbf{z}_{kj}\) Is** \\ \end{tabular}  & \begin{tabular}{c} **Receiver’s Action** \\ **(Default: Leave)** \\ \end{tabular}  \\ \hline \multirow{4}{*}{\(k\)} & \(i\) & update if (\(y_{kj}>y_{ij}\)) \\  & \(k\) & update \\  & \(m\
otin\{i,\;k\}\) & update if (\(s_{km}>s_{im}\)) \(|\;|\;(y_{kj}>y_{ij}\)) \\  & none & update \\ \hline \multirow{4}{*}{\(i\)} & \(i\) & leave \\  & \(k\) & reset \\  & \(m\
otin\{i,\;k\}\) & reset if (\(s_{km}>s_{im}\)) \\  & none & leave \\ \hline \multirow{4}{*}{\(m\
otin\{i,\;k\}\)} & \(i\) & update if (\(s_{km}>s_{im}\)) \& (\;(y_{kj}>y_{ij}\)) \\  & \(k\) & update if (\(s_{km}>s_{im}\)), reset else \\  & \(m\) & update if (\(s_{km}>s_{im}\)) \\  & \(m\
otin\{i,\;k,\;m\}\) & update if (\(s_{km}>s_{im}\)) \and the central computer makes a reward table based on the rewards of each robot. Then, the SGA just finds the (robot-mission) pair that has the maximum reward and conducts mission allocation and alignment.