ICRA 2011 Paper Abstract


Paper WeA102.1

Luo, Lingzhi (Carnegie Mellon University), Chakraborty, Nilanjan (Carnegie Mellon University), Sycara, Katia (Carnegie Mellon University)

Multi-Robot Assignment Algorithm for Tasks with Set Precedence Constraints

Scheduled for presentation during the Regular Sessions "Agent-Based Systems II" (WeA102), Wednesday, May 11, 2011, 08:20−08:35, Room 3C

2011 IEEE International Conference on Robotics and Automation, May 9-13, 2011, Shanghai International Conference Center, Shanghai, China

This information is tentative and subject to change. Compiled on July 14, 2020

Keywords Distributed Robot Systems, Agent-Based Systems


In this paper, we present task allocation (assignment) algorithms for a multi-robot system where the tasks are divided into disjoint groups and there are precedence constraints between the task groups. Existing auction-based algorithms assume the task independence and hence can not be used directly to solve the class of multi-robot task assignment problems that we consider. In our model, each robot can do a fixed number of tasks and obtains a benefit (or incurs a cost) for each task. The tasks are divided into groups and each robot can do only one task from each group. These constraints arise when the robots have to do a set of tasks that have precedence constraints and each task takes the same time to be completed. We extend the auction algorithm to provide an almost optimal solution to the task assignment problem with set precedence constraints (the theoretical guarantees are the same as that of the original auction algorithm for unconstrained tasks). In other words, we guarantee that we will get a solution 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. We first present our algorithm using a shared memory model and then indicate how consensus algorithms can be used to make the algorithm totally distributed.



Technical Content © IEEE Robotics & Automation Society

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2020 PaperCept, Inc.
Page generated 2020-07-14  17:08:40 PST  Terms of use