  In this paper, we consider the problem of optimally allocating tasks,
expressed as global Linear Temporal Logic (LTL) specifications, to teams of
heterogeneous mobile robots. The robots are classified in different types that
capture their different capabilities, and each task may require robots of
multiple types. The specific robots assigned to each task are immaterial, as
long as they are of the desired type. Given a discrete workspace, our goal is
to design paths, i.e., sequences of discrete states, for the robots so that the
LTL specification is satisfied. To obtain a scalable solution to this complex
temporal logic task allocation problem, we propose a hierarchical approach that
first allocates specific robots to tasks using the information about the tasks
contained in the Nondeterministic Buchi Automaton (NBA) that captures the LTL
specification, and then designs low-level executable plans for the robots that
respect the high-level assignment. Specifically, we first prune and relax the
NBA by removing all negative atomic propositions. This step is motivated by
"lazy collision checking" methods in robotics and allows to simplify the
planning problem by checking constraint satisfaction only when needed. Then, we
extract sequences of subtasks from the relaxed NBA along with their temporal
orders, and formulate a Mixed Integer Linear Program (MILP) to allocate these
subtasks to the robots. Finally, we define generalized multi-robot path
planning problems to obtain low-level executable robot plans that satisfy both
the high-level task allocation and the temporal constraints captured by the
negative atomic propositions in the original NBA. We show that our method is
complete for a subclass of LTL that covers a broad range of tasks and present
numerical simulations demonstrating that it can generate paths with lower cost,
considerably faster than existing methods.
