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.

Keywords

• mission planning
• task allocation
• task alignment
• task planning
• multi-robot systems
• automation