  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.
