# Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time
## 3 Related Works
### Consensus-Based Bundle Algorithm (CBBA)
### Centralized Task Allocation and Alignment Based on Constraint Table and Alignment Rules (TACTAR)

CBBA cannot solve the problem with several constraints. The constraints are separated into two types: temporal and spatial constraints. The temporal constraints are constraints about the start/finish time of missions. For instance,'mission A ends before mission B starts','mission A starts simultaneously with mission B', etc., are temporal constraints. The spatial constraints are constraints about mission allocation. For example,'mission A is local MUTEX with mission B' means mission A cannot be allocated to the robot who takes mission B and vice versa. TACTAR is a centralized mission planning algorithm that can handle spatial and temporal constraints based on CBBA. Supported constraints in TACTAR are depicted in Table 2.

The purpose of TACTAR is to calculate the mission plan considering spatial and temporal constraints quickly. TACTAR does not do as described in line 6 of Algorithm 1, just calculate rewards of missions, assuming missions are performed right after the robot's last mission. The optimization performance may suffer slightly, but calculation speed is boosted much faster than CBBA. In addition, some filtering process is added to TACTAR before the beginning of the mission allocation and alignment to not violate constraints. In the mission alignment of TACTAR, some delay or renewal of the mission time (arrival time to mission area, start/finish time of mission) are performed based on constraint table and alignment rules. Further details can be found in [33]. ## 4 Mission Planning Scheme

In this section, we propose a centralized mission planning algorithm for minimizing the total mission completion time. It is based on minimizing total mission completion time for a single-robot-multi-mission problem, modified from the bundle construction in CBBA. So, the algorithm for single-robot is introduced first, and it expands to the algorithm for the multi-robot problems. Note that only mission alignment is needed in single-robot-single-mission problems. In addition, note that this section is focused on the mission planning, not path planning, for minimizing total mission completion time. ### Single-Robot-Multi-Mission Problem

In Single-Robot-Multi-Mission (SRMM) problem, one robot has to conduct all missions, so there is no need to select missions to conduct. All the mission planning has to achieve is to decide the sequence of missions and to calculate start/finish time of each mission. To find the optimal sequence of missions, we propose a process similar to line 6 of Algorithm 1 as described in Algorithm 2. \begin{table}
\begin{tabular}{c c} \hline \hline
**Name** & **Description** \\ \hline Simultaneous & Mission A and B must start at the same time \\ After & Mission A must start after mission B’s finish time \\ Start During & Mission A must start between mission B’s start time and finish time \\ End During & Mission A must end between mission B’s start time and finish time \\ Local MUTEX & Mission A and B are locally mutually exclusive \\ Global MUTEX & Mission A and B are globally mutually exclusive \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Supported type of constraints in TACTAR. In line 2, the total mission completion time is calculated when a mission is added to nth space of sequence using the speed of the robot, the distances between the robot and mission areas, and duration of missions. It repeats for all missions and lengths of sequence. Then, it finds the (mission-space) pair that has the minimum total mission completion time. Finally, the found mission is added to the found space of sequence. Lines 2-5 of Algorithm 2 repeat until all missions (or \(L_{m}\) missions) are allocated. After the final mission is allocated, the start/finish times of each mission are calculated. ### Multi-Robot-Multi-Mission Problem

Unlike the SRMM problems, each robot must select which missions it will perform in Multi-Robot-Multi-Mission (MRMM) problems, considering the equipment status of robots.