Multi-Level Partitioning and Distribution of the Assignment Problem for Large-Scale Multi-Robot Task Allocation

Abstract

A team of robots can handle failures and dynamic tasks by repeatedly assigning functioning robots to tasks. This paper introduces an algorithm that scales to large numbers of robots and tasks by exploiting both task locality and sparsity. The algorithm mixes both centralized and decentralized approaches at different scales to produce a fast, robust method that is accurate and scalable, and reduces both the global communication and unnecessary repeated computation. We depart from optimization and bipartite matching formulations of the problem, observing instead that an assignment can be computed through coarsening and partitioning operations on the utility matrix. First, a coarse assignment is calculated by evaluating the global utility information and partitioning it into clusters in a problem-domain independent way. Next, the assignment solutions in each partition are refined (either recursively, or via an existing algorithm). This multilevel framework allows the repeated reassignment to execute among interrelated partitions. The results suggest that only a minor sacrifice in solution quality is required for gains in efficiency. The proposed algorithm is validated using extensive simulation experiments and the results show advantages over the traditional optimal assignment algorithms. * More precisely, a greedy choice can be employed locally, which is distinct from the Greedy Algorithm but is the same in spirit.