Safe Planning Through Incremental Decomposition of Signal Temporal Logic Specifications

Trajectory planning is a critical process that enables autonomous systems to safely navigate complex environments. Signal temporal logic (STL) specifications are an effective way to encode complex, temporally extended objectives for trajectory planning in cyber-physical systems (CPS). However, the complexity of planning with STL using existing techniques scales exponentially with the number of nested operators and the time horizon of a given specification. Additionally, poor performance is exacerbated at runtime due to limited computational budgets and compounding modeling errors. Decomposing a complex specification into smaller subtasks and incrementally planning for them can remedy these issues. In this work, we present a method for decomposing STL specifications to improve planning efficiency and performance. The key insight in our work is to encode all specifications as a set of basic constraints called reachability and invariance constraints, and schedule these constraints sequentially at runtime. Our experiment shows that the proposed technique outperforms the state-of-the-art trajectory planning techniques for both linear and non-linear dynamical systems.