Fast Task Allocation of Heterogeneous Robots With Temporal Logic and Inter-Task Constraints

Abstract

This work develops a fast task allocation framework for heterogeneous multi-robot systems subject to both temporal logic and inter-task constraints. The considered inter-task constraints include unrelated tasks, compatible tasks, and exclusive tasks. To specify such inter-task relationships, we extend conventional atomic proposition to batch atomic propositions, which gives rise to the LTL <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{\mathcal {T}}$</tex-math></inline-formula> formula. The Task Batch Planning Decision Tree (TB-PDT) is then developed, which is a variant of conventional decision tree specialized for temporal logic and inter-task constraints. The TB-PDT is built incrementally to represent the task progress and does not require sophisticated product automaton, which significantly reduces the search space. Based on TB-PDT, the search algorithm, namely Intensive Inter-task Relationship Tree Search (IIRTS), is developed for the fast task allocation of heterogeneous multi-robot systems. It is shown that the solution time of finding a satisfactory task allocation grows almost quadratically with the number of automaton states. Extensive simulation and experiment demonstrate the validity, the effectiveness, and the transferability of IIRTS.