MT* : Multi-Robot Path Planning for Temporal Logic Specifications
This addresses the computational inefficiency in multi-robot path planning for complex missions, offering a more scalable solution for robotics applications.
The paper tackles the path planning problem for multi-robot systems under Linear Temporal Logic specifications by proposing MT*, an algorithm that reduces computational burden by generating a reduced product graph and dividing the mission among robots, achieving substantial speedup and better scalability with robot count and workspace size.
We address the path planning problem for a team of robots satisfying a complex high-level mission specification given in the form of an 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 Buchi automaton generated from the LTL specification and a joint transition system which captures the collective motion of the robots and then computation of the shortest path using Dijkstra'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 unlike the state of the art approach, scales well with both the number of robots and the size of the workspace