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

Lingzhi Luo, Nilanjan Chakraborty, and Katia Sycara
tech. report CMU-RI-TR-12-35, Robotics Institute, Carnegie Mellon University, December, 2012


Download
  • Adobe portable document format (pdf) (186KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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_t\epsilon)$ 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.

Keywords
Multi-robot assignment, Task allocation, Auction algorithm, Distributed algorithm

Notes
Sponsor: AFOSR MURI grant FA95500810356 and ONR grant N000140910680.

Text Reference
Lingzhi Luo, Nilanjan Chakraborty, and Katia Sycara, "A Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks," tech. report CMU-RI-TR-12-35, Robotics Institute, Carnegie Mellon University, December, 2012

BibTeX Reference
@techreport{Luo_2012_7378,
   author = "Lingzhi Luo and Nilanjan Chakraborty and Katia Sycara",
   title = "A Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks",
   booktitle = "",
   institution = "Robotics Institute",
   month = "December",
   year = "2012",
   number= "CMU-RI-TR-12-35",
   address= "Pittsburgh, PA",
}