Assignment Algorithms for Modeling Resource Contention in Multirobot Task Allocation Academic Article

abstract

• 2015 IEEE. This paper considers multirobot task allocation problems where the estimated costs for performing tasks are interrelated, and the overall team objective need not be a standard sum-of-costs (or utilities) model, enabling straightforward treatment of the additional costs incurred by resource contention. In the model we introduce, a team may choose one of a set of shared resources to perform a task (e.g., several routes to reach a destination), and interference is modeled when multiple robots use the same resource. We show that the general problem is NP-hard, and investigate specialized subinstances with particular cost structures. For the general problem, we describe an exact algorithm which finds an optimal assignment in a reasonable time on small instances. Aiming at larger problems, we turn two particular subinstances, introducing an two algorithms that find assignments quickly even for problems of considerable size, the first being optimal, the second being an approximation algorithm but also producing high-quality solutions with bounded suboptimality.

authors

• Shell, Dylan

published proceedings

• IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING

author list (cited authors)

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

citation count

• 27

complete list of authors

• Nam, Changjoo||Shell, Dylan A

publication date

• July 2015

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE Transactions on Automation Science and Engineering  Journal

keywords

• Assignment Algorithm
• Interference
• Multirobot Task Allocation
• Resource Contention

Digital Object Identifier (DOI)

• 10.1109/TASE.2015.2415514

start page

• 889

end page

• 900

volume

• 12

issue

• 3

URL

• http://dx.doi.org/10.1109/tase.2015.2415514