A Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks

Abstract

In this paper, we present provably-good distributed task allocation (assignment) algorithms for a heterogeneous multi-robot system where the tasks form disjoint groups and there are constraints on the number of tasks a robot can do (both within the overall mission and within each task group). Our problem is motivated by applications where multiple robots with heterogeneous capabilities have to work together to accomplish tasks. Thus, for our purposes, a task group is a {em compound task} composed of more than one atomic tasks where one robot is required for each atomic task. Since robots have limited battery life, we assume that the number of (atomic) tasks that a robot can do within a mission has an upper bound. Furthermore, each robot has a constraint on the number of tasks it can do from each group (this models the fact that multiple robots may be needed to simultaneously perform the atomic tasks that make up the compound task). Each robot obtains a payoff (or incurs a cost) for each task and the overall objective for task allocation is to maximize the total payoff (or minimize the total cost) of all the robots. In general, existing (centralized or distributed) algorithms for task allocation either assume that (atomic) tasks are independent, or do not provide performance guarantee for the situation where task constraints exist. We show that our problem can be solved in polynomial time by a centralized algorithm by reducing it to a minimum cost network flow problem. We then present a decentralized algorithm (that extends the auction algorithm of Bertsekas for linear assignment problems~cite{Bertsekas88}) to provide an almost optimal solution. We prove that our solution is within a factor of $O(n_tepsilon)$ of the optimal solution, where $n_t$ is the total number of tasks and $epsilon$ is a parameter that we choose (the guarantees are the same as that of the original auction algorithm for unconstrained tasks). The decentralized algorithm assumes a shared memory model of computation that may be unrealistic for many multi-robot deployments. Therefore, we show that by using a maximum consensus algorithm along with our algorithm, we can design a totally distributed algorithm for task allocation with group constraints. The key aspect of our distributed algorithm is that the overall objective is (nearly) maximized by {em each robot maximizing its own objective iteratively (using a modified payoff function based on an auxiliary variable, called price of a task)}. Our algorithm is polynomial in the number of tasks as well as the number of robots.