M^3RS: Multi-robot, Multi-objective, and Multi-mode Routing and Scheduling

The quality of task execution can significantly impact a multi-robot mission. While higher quality is desirable, it may not always be feasible due to mission constraints. Existing multi-robot task allocation literature generally overlooks quality of service as a decision variable. Addressing this gap, we introduce the multi-robot, multi-objective, and multi-mode routing and scheduling (M^3RS) problem, designed for time-bound, multi-robot, multi-objective missions. In M^3RS, each task offers multiple execution modes, each with different resource requirements, execution time, and quality. M^3RS optimizes task sequences and execution modes for each agent. The need for M^3RS comes from multi-robot applications in which a trade-off between multiple criteria can be achieved by varying the task level quality of service through task execution modes. Such ability is particularly useful for service robot applications. We use M^3RS for the application of multi-robot disinfection in healthcare environments and other public locations. The objectives considered for disinfection application are disinfection quality and number of tasks completed. A mixed-integer linear programming (MIP) model is proposed for M^3RS. Further, a clustering-based column generation (CCG) algorithm is proposed to handle larger problem instances. Through synthetic, simulated, and hardware case studies, we demonstrate the advantages of M^3RS, showing it provides flexibility and strong performance across multiple metrics. Our CCG algorithm generates solutions 2.5x faster than a baseline MIP optimizer, maintaining competitive performance. The videos for the experiments are available on the project website: https://sites.google.com/view/g-robot/m3rs/