Scalable Integrated Task and Motion Planning from Signal Temporal Logic Specifications
This addresses the need for safety-critical systems to achieve high-level task specifications with guaranteed safety and correctness, representing a novel method rather than an incremental improvement.
The paper tackles the problem of synthesizing continuous trajectories for high-dimensional systems to satisfy non-convex signal temporal logic (STL) specifications, achieving a scalable, provably complete algorithm that separates discrete task and continuous motion planning using SMT and LP solvers.
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.