# Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time
###### Abstract  
Most mission planning algorithms solve multi-robot-multi-mission problems based on mixed integer linear programming. In these algorithms, the rewards (or costs) of missions for each robot are calculated according to the purpose of the user. Then, the (robot-mission) pair that has maximum rewards (or minimum costs) is found in the rewards (or costs) table and the mission is allocated to the robot. However, it is hard to design the reward for minimizing total mission completion time because not only a robot, but also the whole robots' mission plans must be considered to achieve the purpose. In this paper, we propose centralized mission planning for multi-robot-multi-mission problems, minimizing total mission completion time. First, mission planning for single-robot-multi-mission problems is proposed because it is easy to solve. Then, this method is applied for multi-robot-multi-mission problems, adding a mission-plan-adjustment step. To show the excellent performance of the suggested algorithm in diverse situations, we demonstrate simulations for 3 representative cases: a simple case, which is composed of 3 robots and 8 missions, a medium case, which is composed of 4 robots and 30 missions, and a huge case, which is composed of 6 robots and 50 missions. The total mission completion time of the proposed algorithm for each case is lower than the results of the existing algorithm. m _Applied_  
_sciences_  
**Citation:** [PERSON]; [PERSON]; [PERSON] Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time. _Appl. Sci._**2033**, 13, 3737. [[https://doi.org/10.3390/app136737](https://doi.org/10.3390/app136737)]([https://doi.org/10.3390/app136737](https://doi.org/10.3390/app136737))  
Academic Editor: [PERSON] Received: 21 February 2023  
Revised: 10 March 2023  
Revised:  
score. CBBA is a deterministic allocation algorithm, so results are always same if the inputs, the information of the robots and missions, are same. In addition, the computation cost of CBBA is much lower than for other heuristic algorithms. The modified task allocation that can handle some constraints based on CBBA is Coupled-Constraint CBBA (CCBBA) [26]. The missions that have a constraint relationship are grouped as 'Activity' and each mission in the activity is set as 'Element'. Such settings enable easy judgement of whether a mission can be allocated to a robot or not. In addition, it uses optimistic and pessimistic bidding strategies. Each robot bids to the missions based on the strategy for obeying the constraints. However, there are some problems regarding convergence and calculation time for mission planning. Hence, our previous work proposed the Task Allocation and Alignment based on Constraint Table and Alignment Rules (TACTAR), which is modified based on CBBA for centralized mission planning systems [33]. It handles some spatial and temporal constraints using a constraint table and four alignment rules for mission planning. These methods commonly use only the robot's own information to score the missions, but the plans of all robots should be considered to minimize the total task completion time. Hence, CBBA, CCBBA, and TACTAR cannot be used for mission allocation, minimizing total mission completion time without any modification. [PERSON] et al. proposed path planning algorithms for multiple Unmanned Aerial Vehicles (UAVs) to minimize mission completion time [24]. The problem in this paper is defined as a collection of sparse multiple sensors. The sensor points which have distances less than the communication distance of UAVs are grouped, and the center point of each group is defined as hovering point. Then, an ant colony algorithm for solving Traveling Salesman Problem (TSP) is used to visit whole hovering points by one UAV, and a cycle is made as the result. The k-cycles algorithm is used for decomposing the cycle into the number of UAVs. However, this algorithm is based on basic TSP, which means that UAVs must come back to home, and the home positions for all UAVs must be the same.