2024/03/24 by Ishaan Mehta, Junseo Kim, Mehta, Ishaan +5
Engineering · Computer Science · #Advanced Manufacturing and Logistics Optimization #Scheduling and Optimization Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2403.16275
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 (M3RS) problem, designed for time-constrained missions. In M3RS, each task offers multiple execution modes with varying resource needs, durations, and quality levels, allowing trade-offs across mission objectives. M3RS is modeled as a mixed-integer linear programming (MIP) problem and optimizes task sequencing and execution modes for each agent. We apply M3RS to multi-robot disinfection in healthcare and public spaces, optimizing disinfection quality and task completion rates. Through synthetic case studies, M3RS 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: \hrefhttps://sites.google.com/view/g-robot/m3rs/https://sites.google.com/view/g-robot/m3rs/.