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

abstract

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

authors

• Shell, Dylan

published proceedings

• 2014 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA)

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

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE International Conference on Robotics and Automation  Journal

Digital Object Identifier (DOI)

• 10.1109/icra.2014.6907156

start page

• 2158

end page

• 2163

URL

• http://dx.doi.org/10.1109/icra.2014.6907156