Title: Decentralized Task Allocation in Multi-Robot Systems via Bipartite Graph Matching Augmented with Fuzzy Clustering,
Abstract: Robotic systems, working together as a team, are becoming valuable players in
different real-world applications, from disaster response to warehouse
fulfillment services. Centralized solutions for coordinating multi-robot teams
often suffer from poor scalability and vulnerability to communication
disruptions. This paper develops a decentralized multi-agent task allocation
(Dec-MATA) algorithm for multi-robot applications. The task planning problem is
posed as a maximum-weighted matching of a bipartite graph, the solution of
which using the blossom algorithm allows each robot to autonomously identify
the optimal sequence of tasks it should undertake. The graph weights are
determined based on a soft clustering process, which also plays a problem
decomposition role seeking to reduce the complexity of the individual-agents'
task assignment problems. To evaluate the new Dec-MATA algorithm, a series of
case studies (of varying complexity) are performed, with tasks being
distributed randomly over an observable 2D environment. A centralized approach,
based on a state-of-the-art MILP formulation of the multi-Traveling Salesman
problem is used for comparative analysis. While getting within 7-28% of the
optimal cost obtained by the centralized algorithm, the Dec-MATA algorithm is
found to be 1-3 orders of magnitude faster and minimally sensitive to
task-to-robot ratios, unlike the centralized algorithm.