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

BACKGROUND: Efficiently combating with the coronavirus disease 2019 (COVID-19) has been challenging for medics, police and other service providers. To reduce human interaction, multi-robot systems are promising for performing various missions such as disinfection, monitoring, temperature measurement and delivering goods to people quarantined in prescribed homes and hotels. This paper studies the task assignment problem for multiple dispersed homogeneous robots to visit a set of prescribed hotels to perform tasks such as body temperature assessment or oropharyngeal swabs for people quarantined in the hotels while trying to minimize the robots’ total operation time. Each robot can move to multiple hotels sequentially within its limited maximum operation time to provide the service. METHODS: The task assignment problem generalizes the multiple traveling salesman problem, which is an NP-hard problem. The main contributions of the paper are twofold: (I) a lower bound on the robots’ total operation time to serve all the people has been found based on graph theory, which can be used to approximately evaluate the optimality of an assignment solution; (II) several efficient marginal-cost-based task assignment algorithms are designed to assign the hotel-serving tasks to the robots. RESULTS: In the Monte Carlo simulations where different numbers of robots need to serve the people quarantined in 30 and 90 hotels, the designed task assignment algorithms can quickly (around 30 ms) calculate near-optimal assignment solutions (within 1.15 times of the optimal value). CONCLUSIONS: Numerical simulations show that the algorithms can lead to solutions that are close to the optimal compared with the competitive genetic algorithm and greedy algorithm.