Assignment Algorithms for Modeling Resource Contention and Interference in Multi-Robot Task-Allocation Conference Paper uri icon


  • 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.

name of conference

  • 2014 IEEE International Conference on Robotics and Automation (ICRA)

published proceedings


author list (cited authors)

  • Nam, C., & Shell, D. A.

citation count

  • 16

complete list of authors

  • Nam, Changjoo||Shell, Dylan A

publication date

  • January 2014