Lingzhi Luo, Nilanjan Chakraborty, and Katia Sycara
tech. report CMURITR1235, Robotics Institute, Carnegie Mellon University, December, 2012
Download 

Abstract 
In this paper, we present provablygood distributed task allocation (assignment) algorithms for a heterogeneous multirobot 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 multirobot 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 
Multirobot 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 MultiRobot Task Assignment for Grouped Tasks," tech. report CMURITR1235, 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 MultiRobot Task Assignment for Grouped Tasks", booktitle = "", institution = "Robotics Institute", month = "December", year = "2012", number= "CMURITR1235", address= "Pittsburgh, PA", } 
The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University. Contact Us  Update Instructions 