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

Abstract

The assignment problem arises in multi-robot taskallocation 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(n 3 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.