eess.SYNov 17, 2026

Satisfiability Modulo Theories for Robust Synthesis of Signal Temporal Logic Specifications

Authors: Philip Smith, Kevin Leahy

Organizations: Department of Robotics Engineering, Worcester Polytechnic Institute

Abstract

Signal Temporal Logic is a popular framework for describing a robotic system's goals. Once described using a temporal logic framework, synthesis turns the goals into actual steps for the robots to follow. Currently, the state of the art for sound and complete synthesis is using Mixed-Integer Linear Programming (MILP), which struggles on long time horizons and large environments, preventing the construction of guaranteed safe plans for long deployments. This paper introduces a new synthesis method using Satisfiability Modulo Theories (SMT) which scales better for long deployments and adapts to environmental changes more quickly. We do this by introducing an encoding method for STL into SMT constraints, and an encoding method for discrete-time dynamical systems modeled as a transition system. We then conduct an empirical comparison of our SMT based methods against the state of the art MILP based methods. Results show that for this class of problems, SMT is an effective encoding strategy that performs the best on long time horizon tasks.

Figures & tables

Explore similar work

CardsList
  1. Correct-by-Construction Behavior Tree Synthesis from Signal Temporal Logic Specifications with Application to Robotic Missions

    Jul 21, 2026Jiaheng Dong, Jingyi Huang, Liang HanSignal Temporal LogicRobot Task Planning

  2. Temporal logics and formal synthesis for robot planning and control

    Jun 19, 2026Jana Tumova, Joris Verhagen, Matti VahsRoboticsSignal Temporal Logic

  3. Reward Machines for Signal Temporal Logic

    Aug 13, 2026Alper Kamil Bozkurt, Shangtong Zhang, Yuichi MotaiReward MachinesReward Design for RL