Correlation Clustering Based Coalition Formation For Multi-Robot Task Allocation

Due to the inherent complexity of many real world tasks and the limited capabilities of currently available robots in the market, it is almost impossible for a single robot to finish a complex task. Therefore several robots may need to form coalitions to complete such tasks. In this paper, we study the multi-robot coalition formation problem for instantaneous task allocation (IA) where a group of robots needs to be allocated to a set of tasks so that the tasks can be finished optimally. This is a well-known NP-hard problem. To tackle this notoriously difficult problem, we use a correlation clustering technique that enables us to bring similar robots together to form coalitions. This clustering is achieved by using a Linear Programming-based graph partitioning approach along with a region growing strategy. The algorithm presented in this paper is fast and efficient in allocating (near) optimal robot coalitions to tasks.