CS Paper Radar

Integer-Free Control Synthesis for Signal Temporal Logic via Ranked Implicants

Arash Bahari Kordabad, Mohammad H. Mamduhi, Sadegh Soudjani

eess.SY ·submitted 2026-10-14 21:44 UTC · v1
theory

Abstract

This paper proposes an integer-free method for control synthesis of nonlinear discrete-time systems under finite-horizon Signal Temporal Logic (STL) constraints. Instead of introducing integer variables, we consider the discrete choices of the specification in a ranked order and solve a standard nonlinear program for each selected choice until a satisfying trajectory is found. We first define implicants as sets of timed atomic constraints whose joint satisfaction is sufficient to satisfy the specification. A reference trajectory obtained from a smooth approximation of the STL robustness is used to rank these implicants. Fixing one implicant turns the problem into a standard nonlinear program with no auxiliary weights or bilinear terms. If the solution does not satisfy the specification, the next implicant will be considered. We prove soundness and completeness of our method relative to the nonlinear programming solver. Numerical evaluation on nonlinear multi-agent systems shows that our proposed method identifies satisfying trajectories where the exact continuous reformulation fails, and moreover, it is faster than a mixed-integer formulation of the same specification.

Comment
7 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Satisfiability Modulo Theories for Robust Synthesis of Signal Temporal Logic Specifications

eess.SY cs.RO ·2026-11-17 ·Philip Smith, Kevin Leahy
similarity 0.65
Abstract · Submitted to American Control Conference

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.

0.33

Fast Constraint Extraction for Corrective Control under STL Specifications via Logical Dependency Tracking

cs.LO cs.ROeess.SY ·2026-09-08 ·Antoine Besset, Joris Tillet, Chuchu Fan, Julien Alexandre dit Sandretto
publishedcode/data similarity 0.63
Abstract · Accepted for publication at 65th IEEE Conference on Decision and Control (CDC 26)

Ensuring the satisfaction of Signal Temporal Logic (STL) specifications under uncertainty is challenging, as reachability-based monitoring provides guarantees but does not indicate how to restore satisfaction when it becomes indeterminate. A key difficulty is identifying which uncertain components actually affect global satisfaction, especially for nested formulas. This paper introduces a logical dependency tracking framework that propagates uncertainty through the STL structure and captures the causal contribution of reachable sets to satisfaction. By associating markers to uncertain predicates and propagating them via three-valued semantics, we extract in milliseconds a compact Disjunctive Normal Form (DNF) of sufficient constraints, avoiding combinatorial enumeration. As an application, we formulate control correction as a minimum-effort optimization problem. Using zonotopic reachability, the derived constraints are enforced via linear programming, yielding corrections that guarantee STL satisfaction under bounded uncertainty and provide certified probabilistic bounds in the stochastic case. We demonstrate the approach on a nonlinear system with nested STL specifications, showing that dependency tracking enables efficient and formally guaranteed correction. The tracking implementation is available at https://github.com/Antoine-Bst/STL-Three-Valued-Clause-Filtering/.

0.50

A Geometric Decision Procedure for STL Feasibility and Repair

eess.SY cs.RO ·2026-09-19 ·Avinash Malik
theory similarity 0.63
Abstract · 11 pages, 2 figures

Feasibility of a Signal Temporal Logic (STL) specification asks whether, from a given initial state, an admissible control input can satisfy its continuous-time requirements under actuator limits. Establishing feasibility is essential for detecting unrealizable tasks and repairing specifications before execution. State-of-the-art Mixed-Integer Linear Programming (MILP) methods face growing model sizes as temporal horizons and formula complexity increase, and can accept control witnesses that violate continuous-time STL semantics between samples. We propose a geometric approach to STL feasibility and temporal repair that translates temporal requirements into spatial constraints evaluated at the initial state. Its compiled feasibility check is independent of horizon length for fixed compiled dimensions. We prove nonnegative continuous robustness under a joint controller assumption. On 6D UAV benchmarks, median geometric repair times are 0.265--1.510 ms; we show up to 1.68x10^4 speedup over MILP feasibility checker. All geometric runs pass continuous STL validation, whereas majority of completed MILP control witnesses violate continuous-time STL.

0.27

Scenario MPC with STL Specifications and Pareto-Based Feasibility Repair

cs.RO eess.SY ·2026-09-20 ·Tianhao Wu, Yiwei Lyu
similarity 0.62
Abstract

Temporal logic is a formal language for reasoning about system behaviors over time. Signal temporal logic (STL), in particular, has been used to encode spatio-temporal requirements for control synthesis in multi-agent systems, often under the assumption that agents are cooperative and their dynamics are known. However, real-world multi-agent applications, such as autonomous driving, typically involve stochastic and uncontrollable agents. Recent work explored robust control with worst-case or probabilistic formulations, but remains limited in that it either (1) certifies strict satisfaction of STL constraints without addressing feasibility recovery, or (2) relaxes infeasible constraints with ego-centric objectives. In this paper, we propose a model predictive control (MPC) framework that treats feasibility repair as a Pareto optimization problem to explicitly characterize tradeoffs among agent objectives. We further provide a probabilistic certificate on STL violation rate to formally quantify uncertainty under stochastic and uncontrollable agents. The proposed framework is evaluated on two autonomous driving scenarios. Results show that the framework recovers feasible control with demonstrated safe behaviors.

0.16

SparseMax-dSTL: Sound Robustness with Horizon-Independent Gradient Allocation for Temporal Logic Trajectory Optimization

eess.SY cs.LOcs.RO ·2026-10-16 ·Sai Sandeep Damera, Ryan Matheu, John S. Baras, Calin Belta
theory similarity 0.61
Abstract · 8 pages, 5 figures. This work has been submitted to the IEEE for possible publication

A gradient-based solver that enforces a Signal Temporal Logic (STL) specification uses a smooth approximation of its quantitative semantics, the robustness. In safety-critical trajectory optimization, this approximation must have two properties. First, it must be sound, that is, nonnegative only on trajectories that satisfy the specification. Second, at each temporal operator, the weight of its gradient on the violating samples must stay bounded away from zero, however long the horizon. The approximations in use, including the log-sum-exp, its sound variant, and the generalized-mean robustness, do not have both. We introduce lower approximations of the minimum and the maximum whose gradients are sparsemax projections, and we prove that the robustness built from them has both. It lies below the exact robustness and is therefore sound, and its error has a bound that is independent of the number of samples and known before optimization. The gradient of each approximation is exactly zero on every sample beyond a data-dependent threshold, so the weight on violating samples a gap beyond the others has a positive lower bound at every horizon. On a planar unicycle and on a seven-joint manipulator beside a person in simulation, the log-sum-exp approximation is positive on a violating trajectory. As the horizon of the manipulator's task grows from 10 to 80 s, the gradient weight of the sound variant on the violating samples falls from 0.22 to 0.04, while that of sparsemax stays at 1. In a constrained trajectory optimization of the unicycle, the constraint on the log-sum-exp robustness returns a violating trajectory, whereas the constraint on the sparsemax robustness returns a trajectory that satisfies the specification with the required margin.

0.20

Time-Invariant Control Barrier Functions for Bounded STL Safety

eess.SY ·2026-08-28 ·Avinash Malik
theory similarity 0.60
Abstract · 6 pages, 3 figures

Enforcing finite-time persistence specifications in Signal Temporal Logic typically requires formulating Control Barrier Functions within an extended state-time space. This introduces strict mathematical assumptions on global clock synchronization, rendering multi-agent execution brittle under asynchronous network delays, clock skew, and non-monotonic jitter. In this paper, we prove that for bounded-time safety tasks, explicit time dependency can be mathematically eliminated for general continuous-time nonlinear systems. By leveraging the reciprocal integral of worst-case system dissipation, we systematically compile temporal specifications into static, lower-dimensional spatial invariants. We formally prove that this time-invariant realization is strictly sound, removes the need for heuristic time-varying envelope tuning, and guarantees robust forward invariance even under severe network desynchronization.

0.18

Expressive Power of WSTL Formulas for Learning to Rank

eess.SY ·2026-09-18 ·Ruya Karagulle, Gustavo A. Cardona, Necmiye Ozay, Cristian-Ioan Vasile
published similarity 0.59
Abstract · 8 pages, 2 figures, 2 tables, accepted to IEEE CDC 2026

Weighted Signal Temporal Logic (WSTL) is increasingly used as a scoring function in learning-to-rank problems of trajectories with safety guarantees, where its weighted quantitative semantics serve as a parametrized utility function. Despite the growing interest, prior work only assumes the expressiveness of WSTL formulas and empirically demonstrates its utility in capturing diverse preferences. This work focuses on the correctness of this assumption and asks whether using WSTL formulas as scoring functions is theoretically justified. We formalize two concepts: first, rank-realizability, which asks whether all rankings of a given signal set are achievable by varying weights, and, second, rank-capacity, the maximum signal set size for which the formula is rank-realizable. We propose a Mixed-Integer Linear Program to decide rank-realizability, and derive constructive lower bounds for rank-capacity. Experiments on a robotic navigation task show that while a practical WSTL specification may fail to be rank-realizable on a set with similar trajectories, its rank-capacity exceeds the size of the trajectory set. Analysis of Boolean-equivalent formulas reveals that formula structure affects expressivity and that rank-capacity can be increased without altering qualitative semantics.

0.31

Sound Compilation of Weighted Event Signal Temporal Logic to Timeless Geometric Control

eess.SY ·2026-09-07 ·Avinash Malik
similarity 0.59
Abstract · 14 pages

Cyber-Physical Systems (CPS) controllers synthesized from standard temporal logics rely on rigid global clocks, rendering them vulnerable to asynchronous timing anomalies like clock snaps, jitter, and network delays. To overcome these vulnerabilities, we introduce a fundamentally timeless geometric control paradigm alongside a novel specification language: Weighted Event-Based Signal Temporal Logic (weSTL+). This new weSTL+ logic combines the event triggered nature of Event-STL with weighted user preferences of weighted-STL making it suitable for specification of practical autonomous CPS. Using a two-pass compiler, our framework translates weSTL+ formulae directly into C^1-differentiable time-invariant geometric surrogate constraints via finite-time level-set inversion. By mapping temporal windows directly into physical time independent geometric boundaries, this approach entirely eliminates explicit runtime clock monitoring. Our autonomous robotics case study demonstrates that the proposed geometric architecture guarantees enforcement of safety and liveness under severe macroscopic timing discontinuities, succeeding where traditional time-indexed controllers fail.

0.20