Multi-robot assignment algorithm for tasks with set precedence constraints

Abstract

In this paper, we present task allocation (assignment) algorithms for a multi-robot system where the tasks are divided into disjoint groups and there are precedence constraints between the task groups. Existing auction-based algorithms assume the task independence and hence can not be used directly to solve the class of multi-robot task assignment problems that we consider. In our model, each robot can do a fixed number of tasks and obtains a benefit (or incurs a cost) for each task. The tasks are divided into groups and each robot can do only one task from each group. These constraints arise when the robots have to do a set of tasks that have precedence constraints and each task takes the same time to be completed. We extend the auction algorithm to provide an almost optimal solution to the task assignment problem with set precedence constraints (the theoretical guarantees are the same as that of the original auction algorithm for unconstrained tasks). In other words, we guarantee that we will get a solution within a factor of O(n <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</inf> e) of the optimal solution, where n <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</inf> is the total number of tasks and ε is a parameter that we choose. We first present our algorithm using a shared memory model and then indicate how consensus algorithms can be used to make the algorithm totally distributed.