T* : A Heuristic Search Based Algorithm for Motion Planning with Temporal Goals
  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.
