Decentralised submodular multi-robot Task Allocation

Abstract

In this paper we present a decentralised algorithm to solve the Task Allocation problem. Given a set of tasks and a set of robots each with its own utility function, this problem concerns the non-overlapping allocation of tasks to agents maximising the sum of the robot's utility functions. Our algorithm provides a constant factor approximation of (1 - 1/e ≈ 63%) for positive-valued monotone submodular utility functions, and of (1/e ≈ 37%) for positive-valued non-monotone submodular utility functions. In our algorithm, robots only rely on local utility function and neighbour to neighbour communications to find the solution. The algorithm proceeds in two steps. Initially, the robots use Maximum Consensus-based algorithm to find a relaxed solution of the problem using the multilinear extension of their utility functions. Finally, they follow a randomised rounding procedure to exchange valuations on sets of tasks in order to round the relaxed solution. To conclude, we provide experimental evidence of our claims for both monotone and non-monotone submodular functions.