M ³ RS: Multi‐Robot, Multi‐Objective, and Multi‐Mode Routing and Scheduling

ABSTRACT Task execution quality significantly impacts multi‐robot missions, yet existing task allocation frameworks rarely consider quality of service as a decision variable, despite its importance in applications like robotic disinfection and cleaning. We introduce the multi‐robot, multi‐objective, and multi‐mode routing and scheduling (M 3 RS) problem, designed for time‐constrained missions. In M 3 RS, each task offers multiple execution modes with varying resource needs, durations, and quality levels, allowing trade‐offs across mission objectives. M 3 RS is modeled as a mixed‐integer linear programming (MIP) problem that optimizes task sequencing and execution modes for each agent. We apply M 3 RS to multi‐robot disinfection in healthcare and public spaces, optimizing disinfection quality and task completion rates. Through synthetic case studies, M 3 RS demonstrates 3%–46% performance improvements over the standard task allocation method across various metrics. Further, to improve compute time, we propose a clustering‐based column generation algorithm that achieves solutions comparable to or better than the baseline MIP solver while reducing computation time by 60%. We also conduct case studies with simulated and real robots. Experimental videos are available on the project page ( https://sites.google.com/view/g-robot/m3rs/ ).