A Distributable and Computation-flexible Assignment Algorithm: From Local Task Swapping to Global Optimality

The assignment problem arises in multi-robot task-allocation scenarios. This paper introduces an algorithm for solving the assignment problem with several appealing features for online, distributed robotics applications. The method can start with any initial matching and incrementally improve the solution to reach the global optimum, producing valid assignments at any intermediate point. It is an any-time algorithm with an attractive performance profile (quality improves linearly) that, additionally, is comparatively straightforward to implement and is efficient both theoretically (O(n3 lg n) complexity is better than widely used solvers) and practically (comparable to the fastest implementation, for up to hundreds of robots/tasks). We present a centralized version and two decentralized variants that trade between computational and communication complexity. Inspired by techniques that employ task exchanges between robots, our algorithm guarantees global optimality while using generalized swap primitives. The centralized version turns out to be a computational improvement and reinterpretation of the little-known method of Balinski-Gomory, proposed over half a century ago. Deeper understanding of the relationship between approximate swap-based techniques developed by roboticists and combinatorial optimization techniques, e.g., the Hungarian and Auction algorithms developed by operations researchers but used extensively by roboticists is uncovered.