Scalable Integrated Task and Motion Planning from Signal Temporal Logic Specifications

Many safety-critical systems must achieve high-level task specifications with guaranteed safety and correctness. Much recent progress towards this goal has been made through controller synthesis from signal temporal logic (STL) specifications. Existing approaches, however, either consider some a priori discretization of the state-space, deal only with a convex fragment of STL, or are not provably complete. We propose a scalable, provably complete algorithm that directly synthesizes continuous trajectories to satisfy non-convex STL specifications. We separate discrete task planning and continuous motion planning on the fly and harness highly efficient satisfiability modulo theories (SMT) and linear programming (LP) solvers to find dynamically feasible trajectories for high dimensional systems that satisfies non-convex STL specifications. The proposed design algorithms are proved sound and complete, and simulation results demonstrate the scalability of our approach.