Sampling-based tree search with discrete abstractions for motion planning with dynamics and temporal logic

This paper presents an efficient approach for planning collision-free, dynamically-feasible, and low-cost motion trajectories that satisfy task specifications given as formulas in a temporal logic, namely Syntactically Co-Safe Linear Temporal Logic (LTL). The planner is geared toward high-dimensional mobile robots with nonlinear dynamics operating in complex environments. The planner incorporates physics-based engines for accurate simulations of rigid-body dynamics. To obtain computational efficiency and generate low-cost solutions, the planner first imposes a discrete abstraction by combining an automaton representing the LTL formula with a workspace decomposition. The planner then uses the discrete abstraction to induce a partition of a sampling-based motion tree being expanded in the state space into equivalence classes. Each equivalence class captures the progress made toward achieving the temporal logic specifications. Heuristics defined over the abstraction are used to estimate the feasibility of expanding the motion tree from these equivalence classes and reaching an accepting automaton state. Costs are adjusted based on progress made, giving the planner the flexibility to make rapid progress while discovering new ways to expand the search. Comparisons to related work show statistically significant computational speedups and reduced solution costs.