Correlation clustering-based multi-robot task allocation: a tale of two graphs

• Published in: Applied computing review : a publication of the Special Interest Group on Applied Computing 2020-01, Vol.19 (4), p.5-16
• Main Authors: Dutta, Ayan, Czarnecki, Emily, Ufimtsev, Vladimir, Asaithambi, Asai
• Format: Article
• Language: English
• ISSN: 1559-6915; 1931-0161
• DOI: 10.1145/3381307.3381308

Robots currently available in the market are somewhat limited in their capabilities, which makes it difficult for a single robot to handle many real-world tasks that are inherently complex. Thus, it becomes necessary to engage multiple robots which might form coalitions to complete such complex tasks. In this paper, we consider the well-known NP-hard problem of forming coalitions with the goal of instantaneous allocation (IA) of a group of robots to a set of tasks for optimal completion of the tasks. With the goal of bringing similar robots together to form coalitions, we use a correlation clustering technique, which uses a Linear Programming-based graph partitioning approach along with a region growing strategy. Our proposed approach is shown to gracefully handle both cost and utility-based objective functions for task allocation. We demonstrate that the resulting algorithm is fast and efficient in allocating (near) optimal robot coalitions to tasks. Furthermore, it outperforms two existing approaches in terms of execution times while yielding similar new-optimal solutions.