Assignment Algorithms for Modeling Resource Contention in Multirobot Task Allocation

作者：Nam Changjoo^*; Shell Dylan A

来源：IEEE Transactions on Automation Science and Engineering, 2015, 12(3): 889-900.

DOI：10.1109/TASE.2015.2415514

• Assignment algorithm
• interference
• multirobot task allocation
• resource contention

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.
Note to Practitioners-An idealization is made in the vast majority of the task allocation literature: the presumption of task independence. Tasks are never performed in perfect isolation in practice and this paper shows that computing task costs independently, although a prevalent modeling simplification, may be detrimental. Whenever robots use shared resources (e.g., narrow passages, limited communication bandwidth), resource contention and physical interference may cause performance to degrade. These aspects can be thought of as interrelationships between tasks costs and this article introduces an augmented model that expresses such interrelationships by capturing resource-based interactions among robots which change task execution costs. This paper describes optimization methods which allowing different models of contention (e.g., linear or convex) giving the practitioner flexibility for their specific application. Generally, the algorithms described are fast enough to be applied to real-time applications, but the experimental data also enable an understanding of modeling complexity versus running-time.

• 出版日期2015-7