Matching-based Coalition Formation for Multi-robot Task Assignment Under Partial Uncertainty

Abstract

In this paper, we study the multi-robot coalition formation problem for instantaneous task allocation, where a group of robots needs to be allocated to a set of tasks to execute optimally. One robot might not be enough to complete a given task, so forming teams to complete these tasks becomes necessary. In many real-world scenarios, the robots might have noisy localization. Due to this, cost calculations for robot-to-task assignments become uncertain. However, a small amount of resources might be available to accurately localize a subset of these robots. To this end, we propose a bipartite graph matching-based task allocation strategy (centralized and distributed versions) that gracefully handles the uncertainty arising from cost calculations using an interval-based technique while leveraging the fact that a small number of robots might be localized on demand using an external system such as drones. We have tested the proposed technique in simulation. Results show that our approach is moderately fast -- scales up to 100 robots and 50 tasks in 0.85 sec. (distributed solution) while gracefully handling partial uncertainty.