# Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time
## 3 Related Works
### Consensus-Based Bundle Algorithm (CBBA)
For example, the robot that does not have camera cannot conduct surveillance and reconnaissance missions. However, it is hard to conduct a mission allocation because not only a robot but also the whole robots' planning results must be considered to achieve total mission completion time minimization. So, we propose initial bundle construction and bundle adjustment methods as described in Algorithm 3. ```
1:if first time
2: Construct initial bundle
3:else
4: bundle = result of adjustment
5:endif
6: Adjust bundle
```
**Algorithm 3** Mission planning: MRMM

If it is first time for the mission planning, initial bundle construction step runs. If not, the result of the previous adjustment is copied into the bundle for preventing to fall into local optimization solutions during mission planning iterations. Then, the bundle adjustment for total mission completion time minimization is run. In initial bundle construction, as described in Algorithm 4, each robot calculates the expected finish time of missions based on the positions of the robot and missions, the speed of the robot, and the duration of each mission for the robot. Then, the table of finish time of missions for robots will be made. The (robot-mission) pair that has the minimum finish time of the mission is found in the table. If the pair has an infinity finish time of mission (initial value of the table), all possible missions are already added to the bundles, so it breaks out of the iterations. If not, it checks the selected robot that can conduct the selected mission. If the robot cannot conduct the mission, \(t_{i_{self}}\) in the table is set to infinity (or initial value) and another pair in the table is found. If the robot can conduct the mission, the mission is added to the bundle of the robot. The column (or row) about the mission is set to infinity (or initial value) in the table, and the procedure is repeated until all missions are added to the bundle. In the bundle adjustment, line 6 of Algorithm 3, the robot that has the maximum total mission completion time is found. Then, one of the missions in the bundle of that robot is moved to the bundles of the others who can conduct the mission. The total mission completion time for each robot can be calculated based on the bundles following Algorithm 2, because fixing the bundles of each robot means MRMM problems are simplified into SRMM problems for each robot. The \((i_{s},\,j_{s})\) pair that has the minimum total mission completion time is searched. If there are multiple \((i_{s},\,j_{s})\) pairs that have the same minimum total completion time, a \((i_{s},\,j_{s})\) pair in which the larger value is the smallest among the total mission completion time of \(i_{max}\) and \(i_{s}\) is selected. Finally, the total mission completion times for the results of previous and current iterations are compared. If the current one is lower than the previous one, the current bundle and total mission completion time are copied into the previous results. Then, it goes to line 4 of Algorithm 5 and the procedures are repeated. If not, it means the previous results are the optimal mission plans for minimizing the total mission completion time, so it outputs the previous results.