Paper Info
Title
Large-scale multi-robot task allocation via dynamic partitioning and distribution.
Abstract
This paper introduces an approach that scales assignment algorithms to large numbers of robots and tasks. It is especially suitable for dynamic task allocations since both task locality and sparsity can be effectively exploited. We observe that an assignment can be computed through coarsening and partitioning operations on the standard utility matrix via a set of mature partitioning techniques and programs. The algorithm mixes centralized and decentralized approaches dynamically at different scales to produce a fast, robust method that is accurate and scalable, and reduces both the global communication and unnecessary repeated computation. An allocation results by operating on each partition: either the steps are repeated recursively to refine the generalized assignment, or each sub-problem may be solved by an existing algorithm. The results suggest that only a minor sacrifice in solution quality is needed for significant gains in efficiency. The algorithm is validated using extensive simulation experiments and the results show advantages over the traditional optimal assignment algorithms.
Year
DOI
Venue
2012
10.1007/s10514-012-9303-2
Auton. Robots
Keywords
DocType
Volume
Assignment partitioning,Multi-robot task allocation,Dynamic assignment
Journal
33
Issue
ISSN
Citations 
3
0929-5593
30
PageRank 
References 
Authors
1.05
28
2
Name
Order
Citations
PageRank
Lantao Liu115716.49
Dylan A. Shell233447.94