Multi-robot task assignment for serving people quarantined in multiple hotels during COVID-19 pandemic

Area of Science:

• Robotics
• Operations Research
• Epidemiology

Background:

• The coronavirus disease 2019 (COVID-19) pandemic necessitates innovative solutions to minimize human interaction for service providers.
• Multi-robot systems offer a promising approach for tasks like disinfection, monitoring, and delivery to quarantined individuals.
• Efficiently assigning tasks to these robots is crucial for managing operations during public health crises.

Purpose of the Study:

• To address the task assignment problem for multiple homogeneous robots serving quarantined individuals in hotels.
• To minimize the total operation time for robots performing services such as temperature assessment and sample collection.
• To develop efficient algorithms for solving this NP-hard problem, which generalizes the multiple traveling salesman problem.

Main Methods:

• Developed a lower bound for total robot operation time using graph theory to evaluate solution optimality.
• Designed several efficient marginal-cost-based algorithms for task assignment.
• Utilized Monte Carlo simulations to test algorithm performance with varying numbers of robots and hotels.

Main Results:

• The designed task assignment algorithms rapidly compute near-optimal solutions (within 1.15 times the optimal value) in approximately 30 ms.
• Simulations involving 30 and 90 hotels demonstrated the algorithms' efficiency and effectiveness.
• The algorithms produced solutions comparable or superior to established methods like genetic and greedy algorithms.

Conclusions:

• The proposed marginal-cost-based algorithms provide efficient and effective solutions for multi-robot task assignment in quarantine scenarios.
• The developed methods offer a practical approach to optimizing robot operations during public health emergencies.
• The study contributes valuable insights into the application of robotics for pandemic response.