T* : A Heuristic Search Based Path Planning Algorithm for Temporal Logic Specifications

摘要

The fundamental path planning problem for a mobile robot involves generating a trajectory for point-to-point navigation while avoiding obstacles. Heuristic-based search algorithms like A* have been shown to be efficient in solving such planning problems. Recently, there has been an increased interest in specifying complex path planning problem using temporal logic. In the state-of-the-art algorithm, the temporal logic path planning problem is reduced to a graph search problem, and Dijkstra's shortest path algorithm is used to compute the optimal trajectory satisfying the specification.The A* algorithm, when used with an appropriate heuristic for the distance from the destination, can generate an optimal path in a graph more efficiently than Dijkstra's shortest path algorithm. The primary challenge for using A* algorithm in temporal logic path planning is that there is no notion of a single destination state for the robot. We present a novel path planning algorithm T* that uses the A* search procedure opportunistically to generate an optimal trajectory satisfying a temporal logic query. Our experimental results demonstrate that T* achieves an order of magnitude improvement over the state-of-the-art algorithm to solve many temporal logic path planning problems in 2-D as well as 3-D workspaces.