Multi-robot assignment algorithm for tasks with set precedence constraints
- Resource Type
- Conference
- Authors
- Lingzhi Luo; Chakraborty, Nilanjan; Sycara, Katia
- Source
- 2011 IEEE International Conference on Robotics and Automation Robotics and Automation (ICRA), 2011 IEEE International Conference on. :2526-2533 May, 2011
- Subject
- Robotics and Control Systems
Signal Processing and Analysis
Power, Energy and Industry Applications
Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Bioengineering
Nickel
Algorithm design and analysis
Robot kinematics
Distributed algorithms
Resource management
Greedy algorithms
Multi-robot assignment
Task allocation
Auction algorithm
- Language
- ISSN
- 1050-4729
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 t e) of the optimal solution, where n t is the total number of tasks and ε 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.