Decentralized Matroid Optimization for Topology Constraints in Multi-Robot Allocation Problems

Abstract

In this paper, we demonstrate how topological constraints, as well as other abstract constraints, can be integrated into task allocation by applying the combinatorial theory of matroids. By modeling problems as an intersection of matroid constraints, arbitrary combinatorial relationships can be achieved in the task allocation space. To illustrate the expressiveness of the framework, we model a novel task allocation problem that couples abstract per-robot constraints with a communication spanning tree constraint. As our problem is cast as a matroid intersection, provable optimality bounds with simple greedy algorithms follows immediately from theory. Next, we present a decentralized algorithm that applies auction methods to task allocation with matroid intersections. Simulations of task allocation for surveillance in urban environments demonstrate our results. Finally, Monte Carlo results are provided that indicate greedy task allocations can be highly competitive even with near-optimal solutions in practice.