Title: T* : A Heuristic Search Based Algorithm for Motion Planning with Temporal Goals,
Abstract: Motion planning is the core problem to solve for developing any application
involving an autonomous mobile robot. The fundamental motion planning problem
involves generating a trajectory for a robot for point-to-point navigation
while avoiding obstacles. Heuristic-based search algorithms like A* have been
shown to be extremely efficient in solving such planning problems. Recently,
there has been an increased interest in specifying complex motion plans using
temporal logic. In the state-of-the-art algorithm, the temporal logic motion
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 a proper heuristic for the distance from the
destination can generate an optimal path in a graph efficiently. 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. In this thesis, we
present a novel motion planning algorithm T* that uses the A* search procedure
in temporal logic path planning \emph{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 motion planning
problems.