Assignment Algorithms for Modeling Resource Contention and Interference in Multi-Robot Task-Allocation
- Additional Document Info
- View All
© 2014 IEEE. We consider optimization of the multi-robot task-allocation problem when the overall performance of the team need not be a standard sum-of-cost model. We introduce a generalization that allows for the additional cost incurred by resource contention to be treated in a straightforward manner. In this variant, robots may choose one of shared resources to perform a task, and interference may be modeled as occurring when multiple robots use the same resource. We investigate the general NP-hard problem and instances where the interference results in linear or convex penalization functions. We propose an exact algorithm for the general problem and polynomial-time algorithms for the other problems. The exact algorithm finds an optimal assignment in a reasonable time on small instances. The other two algorithms quickly find an optimal and a high-quality approximation assignment even if a problem is of considerable size. In contrast to conventional approximation methods, our algorithm provides the performance guarantee.
author list (cited authors)