A Taxonomy for Task Allocation Problems with Temporal and Ordering Constraints

Abstract

Previous work on assigning tasks to robots has proposed extensive categorizations of allocation of tasks with and without constraints. The main contribution of this paper is a more specific categorization of problems that have both temporal and ordering constraints. We propose a novel taxonomy that builds on the existing taxonomy for multi-robot task allocation and organizes the current literature according to the temporal nature of the tasks. We summarize widely used models and methods from the task allocation literature and related areas, such as vehicle routing and scheduling problems, showing similarities and differences.