Provably-Good Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks

February 2015

Provably-Good Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks

Authors:

Lingzhi Luo, Nilanjan Chakraborty, and Katia Sycara

Abstract:

In this paper, we present provably-good distributed task assignment algorithms for a heterogeneous multi-robot system, in which 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). Each robot obtains a payoff (or incurs a cost) for each task and the overall objective for task allocation is to maximize (minimize) the total payoff (cost) of the robots. In general, existing algorithms for task allocation either assume that tasks are independent or do not provide performance guarantee for the situation, in which task constraints exist. We present a distributed algorithm to provide an almost optimal solution for our problem. The key aspect of our distributed algorithm is that the overall objective is (almost) maximized by each robot maximizing its own objective iteratively (using a modified payoff function based on an auxiliary variable, called price of a task). Our distributed algorithm is polynomial in the number of tasks, as well as the number of robots.
@article{Luo-2015-120820,
author = {Lingzhi Luo And Nilanjan Chakraborty And Katia Sycara},
title = {Provably-Good Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks},
journal = {Proceedings of IEEE Transactions on Robotics},
year = {2015},
month = {February},
volume = {31},
number = {1},
pages = {19 - 30},
}
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.