Multi-Robot Assignment Algorithm for Tasks with Set Precedence Constraints
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(nt ε) of the optimal solution, where nt is the total number of tasks and e 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.
Multi-robot assignment Task allocation Auction algorithm
Lingzhi Luo Nilanjan Chakraborty Katia Sycara
Robotics Institute,School of Computer Science,Carnegie Mellon University,5000 Forbes Ave,Pittsburgh,PA 15213
国际会议
2011 IEEE International Conference on Robotics and Automation(2011年IEEE世界机器人与自动化大会 ICRA 2011)
上海
英文
2526-2533
2011-05-09（万方平台首次上网日期，不代表论文的发表时间）