Distributed Algorithm Design for Multi-Robot Task Assignment with Deadlines for Tasks

Lingzhi Luo, Nilanjan Chakraborty and Katia Sycara
Conference Paper, International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, May, 2013

View Publication

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.


In this paper, we present provably-good algo- rithms for multi-robot task assignment, where each task has to be completed within its deadline. Each robot has a upper limit on the maximum number of tasks that it can perform due to its limited battery life, and each task takes the same amount of time to complete. Each robot has a different payoff (or cost) for the tasks and the objective is to assign the tasks to the robots such that the total payoff (cost) is maximized (minimized) while respecting the task deadline constraints. This problem is an extension of a special generalized assignment problem (where each task consumes the same time resource and must be finished), with additional deadline constraints for the time resource assignment. We show that the problem can be reduced to a problem of assigning tasks to robots, where the tasks are organized in overlapping sets, and each robot has a limit on the number of tasks it can perform from each set, which is a variant of multi-robot assignment problem with set precedence constraint (SPC-MAP) discussed in [1]. We present a distributed auction-based algorithm for this problem and prove that the solution is almost-optimal. We also present simulation results to depict the performance of our algorithm.

author = {Lingzhi Luo and Nilanjan Chakraborty and Katia Sycara},
title = {Distributed Algorithm Design for Multi-Robot Task Assignment with Deadlines for Tasks},
booktitle = {International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany},
year = {2013},
month = {May},
} 2017-09-13T10:39:21-04:00