MT*: Multi-Robot Path Planning for Temporal Logic Specifications

Abstract

We address the path planning problem for a team of robots satisfying a complex high-level mission specification given in the form of a Linear Temporal Logic (LTL) formula. The state-of-the-art approach to this problem employs the automata-theoretic model checking technique to solve this problem. This approach involves computation of a product graph of the Büchi automaton generated from the LTL specification and a joint transition system that captures the collective motion of the robots and then computation of the shortest path using Di-jkstra's shortest path algorithm. We propose MT*, an algorithm that reduces the computation burden for generating such plans for multi-robot systems significantly. Our approach generates a reduced version of the product graph without computing the complete joint transition system, which is computationally expensive. It then divides the complete mission specification among the participating robots and generates the trajectories for the individual robots independently. Our approach demonstrates substantial speedup in terms of computation time over the state-of-the-art approach and scales well with both the number of robots and the size of the workspace.