CS Paper Radar

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

Avinash Malik

eess.SY ·submitted 2026-09-07 19:03 UTC · v2

Abstract

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.

Comment
14 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Runtime Monitoring of Distributed Cyber-Physical Systems Without a Global Clock

cs.LO ·2026-08-13 ·Charles Koll, Houssam Abbas
published similarity 0.70
Abstract · Accepted to Runtime Verification 2026

We give the first theoretical characterization, and the first algorithm, for continuous monitoring of a distributed Cyber-Physical System (CPS) against a dense-time temporal logic specification. A distributed CPS is composed of multiple agents, each with a local clock; these clocks drift from each other, so there is no well-defined global time. When monitoring such a system's output signal against a temporal logic specification, it is not evident how to interpret the temporal constraints of the formula, and what satisfaction means. Yet CPS designers, like control engineers, typically think of their system's operation in terms of global time. Most existing techniques for monitoring distributed systems work with discrete-time specifications not suitable for CPS, and/or require an explicit mapping of temporal constraints to local clocks. We introduce an algorithm that addresses the above challenges for a fragment of Signal Temporal Logic (STL) that still includes all temporal operators. It relies on a novel extension of satisfaction signals to this partially synchronous setting (where clocks drift), and an analysis of the geometry of multi-dimensional partially synchronous time. The algorithm returns the set of all possible global moments that can satisfy the specification. Knowledge of these possible global moments is important for debugging distributed hybrid control systems such as fleets of drones and electrical grids. We derive the worst-case complexity of the algorithm, and implement a sound approximation of it that experimentally illustrates effective monitoring, even in scenarios of up to 50 agents.

0.23

Time-Invariant Control Barrier Functions for Bounded STL Safety

eess.SY ·2026-08-28 ·Avinash Malik
theory similarity 0.68
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

A Geometric Decision Procedure for STL Feasibility and Repair

eess.SY cs.RO ·2026-09-19 ·Avinash Malik
theory similarity 0.67
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

On the Time and Frequency Domain Representations of Signals for CPS Specification

cs.SE ·2026-08-21 ·Claudio Mandrioli, Drishti Yadav, Domenico Bianculli
similarity 0.66
Abstract

Specification languages are instrumental to the Verification \& Validation of Cyber-Physical Systems (CPSs). Most state-of-the-art specification languages use the time-domain representation of signals, which is not always suitable for describing signal shapes and dynamic behaviours. Instead, fields like control and robotics use the frequency-domain representation to characterise these behaviours. Time-frequency representations combine the capabilities of both domains. We investigate the use of time-frequency representations to specify CPS requirements. We analyse existing taxonomies of CPS requirements to identify which requirement classes can benefit from time-frequency representations. We derive the desiderata for a specification language that uses time-frequency representations and propose Signal-Spectrum Temporal Logic (S2TL), a language enabling assertions over frequency intervals and relations between frequency components. We operationalise the S2TL semantics for monitoring CPS traces, and implement a monitor. We define specification templates for the identified requirement classes and compare time- and time-frequency-domain formulations in terms of applicability, expression fidelity, and noise tolerance of monitoring. We observe that, while time-domain specifications are applicable only to input traces containing step-like changes or using constant interpolation, time-frequency specifications extend their evaluation to traces generated through linear interpolation, and improve tolerance to offset and high-frequency noise, while achieving comparable fidelity to the intended system properties.

0.13

Satisfiability Modulo Theories for Robust Synthesis of Signal Temporal Logic Specifications

eess.SY cs.RO ·2026-11-17 ·Philip Smith, Kevin Leahy
similarity 0.66
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.24

Compiling Spatial Certificates into Temporal Contracts for Latency-Aware Control

eess.SY ·2026-08-25 ·Avinash malik
benchmark similarity 0.65
Abstract · 6 pages, 1 figure

We introduce CIPS, a contract-driven execution abstraction for managing computational latency and sampled-data updates in safety-critical cyber-physical systems (CPS). A fundamental challenge in real-time control is that physical safety certificates are defined spatially, yet predicting their validity under non-zero computation and handoff latency requires online numerical integration of plant dynamics. CIPS resolves this operational dichotomy by systematically compiling heterogeneous spatial safety certificates into normalized, unit-rate temporal contracts entirely offline. This transformation abstracts complex plant dynamics, exposing a deterministic, O(1) temporal budget to a generic sampled-data scheduler. We formally prove that this architecture guarantees global hybrid safety invariance under bounded computational latency and asynchronous execution. Finally, we validate the framework via an autonomous vehicle braking benchmark, demonstrating a 60.5 times reduction in micro-architectural evaluation overhead compared to latency-aware event-triggered control (LA-ETC) while preserving safety bounds.

0.15

Differentiable Ternary Temporal Logic Semantics with Polynomial Surrogate Networks

eess.SY cs.RO ·2026-10-03 ·Ryan Matheu, Sai Sandeep Damera, John S. Baras, Calin Belta
similarity 0.64
Abstract · 9 pages, 6 figures

Temporal logic provides designers a formal reasoning tool for specifying complex spatio-temporal behaviors and tasks for autonomous systems. Many techniques exist for control synthesis according to temporal logic specifications, spanning a large variety of systems, including robotics. However, the vast majority of implementations are limited to Boolean temporal logics. Boolean temporal logic does not have an innate mechanism for quantifying abstention, rather verdicts are either definitively \textit{True} or \textit{False}. Recent work demonstrates that ternary logic is a capable formalism for reasoning about robotic behaviors, with the natural ability to classify uncertainty with the \textit{Unknown} literal. Ternary temporal logic is still in its infancy, with work limited to synthesis for linear systems and monitoring. This work proposes a probabilistic relaxation of ternary temporal logic that allows for value and gradient computation through the same network while retaining exact verdicts on actual data. The relaxed network can be used as an objective in gradient-based control synthesis for both offline and online robotic control applications. We demonstrate the utility of our framework with two robotic manipulator tasks, one offline and one online, involving intermediate checking and sequencing of subtasks to demonstrate the benefit of our approach in terms of correct and timely execution.

0.20

When Automata Meet Streams: Temporal Logic Compilation for Stream-Based Robotics Task and Motion Planning

cs.RO cs.FL ·2026-08-19 ·Sayem Nazmuz Zaman, Cyrus Neary
similarity 0.64
Abstract

Stream-based robotics Task and Motion Planning (TAMP) integrates discrete symbolic planning with dynamically generated continuous geometric parameters, such as poses, grasps, and trajectories. However, stream-based planners typically reason only about goal reachability, whereas long-horizon tasks also demand adherence to temporal specifications, such as safety-critical ordering, invariance, and liveness constraints. No methods currently exist to enforce such temporal constraints for stream-based solvers because streams generate an expanding geometric object set via iterative stream refinement loops during planning, rendering existing temporal-logic compilation techniques incompatible. We therefore present Synchronous Action Monitoring with Token Destruction (SAM-TD), a compilation method that enforces arbitrary Linear Temporal Logic over finite traces ($\textrm{LTL}_f$) specifications in stream-based TAMP. SAM-TD translates arbitrary $\textrm{LTL}_f$ constraints into automata and embeds regressed automaton guards into action schemas, which are pre-specified before planning begins. By doing so, SAM-TD can handle objects generated by streams during planning, thus circumventing the need to enumerate a fixed object set or modify the underlying planner. During search, SAM-TD synchronously updates automaton states and uses a validity token shared across all automata to prune constraint-violating branches. We show that SAM-TD supports dynamically generated stream objects from iterative stream refinements during plan search. Experimental results provide the first ever demonstration of stream-based TAMP under $\textrm{LTL}_f$ constraints in three robotics PDDLStream environments. Furthermore, on standard discrete PDDL benchmarks, SAM-TD is competitive with state-of-the-art temporal-constraint compilation methods.

0.24