Robustness-Based Synthesis for Time Window Temporal Logic Specifications via Mixed-Integer Linear Programming
Philip Smith, Ahmad Ahmad, Kevin Leahy · 2026
Read Robustness-Based Synthesis for Time Window Temporal Logic Specifications via Mixed-Integer Linear Programming by Philip Smith, Ahmad Ahmad, Kevin Leahy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30820.txt.
Introduction
Philip Smith, Ahmad Ahmad and Kevin Leahy synthesise robot controllers from timed task specifications. Time Window Temporal Logic is a language for tasks with timing windows, such as dwell in this region, then visit that one by a deadline. The team build on the logic's quantitative semantics, a robustness score saying how well a behaviour satisfies the formula.
They encode robust satisfaction as mixed-integer linear constraints, turning synthesis into an optimisation problem that maximises the robustness degree. Any feasible solution with positive score provably satisfies the task. Two settings are covered: open-loop, which plans the full control sequence at once, and a receding-horizon controller that re-solves at each step from the measured state. Their controller shortens its horizon adaptively, using the task automaton to plan only through the current window. That makes each solve much cheaper than the full open-loop one.
Catalog record
| CREATOR | Philip Smith, Ahmad Ahmad, Kevin Leahy |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30820
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robustness-Based Synthesis for Time Window Temporal Logic Specifications via Mixed-Integer Linear Programming Philip Smith, Ahmad Ahmad, Kevin Leahy Abstract Time Window Temporal Logic (TWTL) is a rich specification language for cyber-physical systems that can compactly express sequential tasks with explicit timing constraints. In this paper, we consider the problem of synthesizing control inputs for discrete-time linear systems subject to TWTL task specifications. Building on the quantitative semantics (robustness) recently introduced for TWTL in [ 2 ] , we encode the robust satisfaction of a TWTL formula as a set of Mixed-Integer Linear constraints and pose synthesis as a Mixed Integer Linear Program (MILP) that maximizes the robustness degree. We prove that any feasible solution with positive objective value guarantees Boolean satisfaction of the specification. We address two synthesis settings: an open-loop formulation that optimizes the full control sequence from the initial state, and a closed-loop receding-horizon Model Predictive Controller (MPC) formulation that re-solves the MILP at each step using the current measured state. A key feature of our MPC formulation is a task-adaptive horizon that exploits the TWTL Deterministic Finite Automaton (DFA) to determine the active sub-task at each step, limiting the prediction horizon to the remaining window of the current task rather than the full formula horizon, this makes each re-solve significantly cheaper than the initial open-loop solve. I Introduction Robot tasks often use spatio-temporal constraints: a surveillance drone which must dwell for a duration in multiple regions, or a multi-robot team which must complete sub-tasks in sequence while respecting timing windows. Temporal logics (TLs) [ 4 , 12 ] address this by providing a language for stating what a system must accomplish over time. As such, they have become a standard tool for encoding high-level task specifications for cyber-physical systems. Signal Temporal Logic (STL) [ 15 ] and Metric Temporal Logic (MTL) [ 13 ] are widely used concrete-time logics. Time Window Temporal Logic (TWTL) [ 19 ] was introduced more recently as an alternative that (i) expresses sequential tasks compactly through a dedicated concatenation operator, and (ii) admits automata translations whose complexity is independent of the formula time bounds, making it particularly attractive for automata-based planning and synthesis [ 17 ] . Satisfying a TL specification requires synthesizing a control policy [ 5 ] . Optimization-based synthesis from TL specifications is enabled by a robustness measure quantifies Boolean satisfaction as a real value. Such a measure allows synthesis to optimize satisfaction margin, such as clearance of obstacles, alongside other optimization concerns like path length or battery life, and lends itself naturally to an MPC formulation. Optimizing robustness in this way allows plans to survive in a real, noisy world. For STL, the classical robustness [ 9 ] has been encoded as Mixed-Integer Linear constraints by Raman et al. [ 18 ] , who also propose a receding-horizon MPC framework where the MILP is re-solved at each step with a fixed horizon equal to the formula time bound, with the executed history pinned as equality constraints. Until recently, TWTL lacked a robustness measure. In [ 2 ] , we introduced two sound quantitative semantics for TWTL— a \mathrm{min} - \mathrm{max} -based robustness ( \rho ) and an Arithmetic Geometric Mean (AGM) robustness [ 16 ] —together with runtime monitors for partial runs. A robustness measure only scores a given run; it does not produce one. What has been missing for TWTL is a synthesis procedure to optimize for \rho . In this paper, we leverage \rho from [ 2 ] to develop the first MILP synthesis procedure for TWTL. Contributions. 1. We encode robustness as a recursive big-M MILP encoding and prove correctness (Sec. IV , Theorem IV.1 ); 2. We formulate an open-loop controller (Problem III.1 ) and a closed-loop MPC controller (Problem III.2 ) with a task-adaptive horizon that exploits the TWTL DFA to bound the prediction horizon rather than use the full formula horizon T (Sec. V ); 3. We propose a warm-start strategy for the MPC re-solves that reduces the per-step online cost to linear in the number of TWTL sub-tasks for state updates and O(1) for horizon shrinkage, plus the MILP re-solve on a progressively smaller problem (Sec. V-C ); and 4. We demonstrate the incresed efficiency of direct TWTL enconding by comparing against TWTL translated to STL (Sec. VI-C ) Related work. While other works have previously used TWTL for monitoring [ 6 , 7 ] , or as a basis for sampling-based planning [ 19 , 17 , 1 ] , we perform synthesis directly using the specification and a model of system dynamics (Sec. II-A ). Unlike sampling-based planners, which offer probabilistic completeness but no hard guarantees on robustness degree, our MILP formulation deterministically maximizes robustness and enables closed-loop MPC with disturbance rejection. The only prior work to use MILP with TWTL is [ 11 ] , which encodes automaton transitions (not robustness) as the MILP objective; ours is the first robustness-maximizing MILP for TWTL. Our encoding is directly analogous to [ 18 ] for STL, with TWTL’s hold and within operators playing the roles of STL’s always and eventually. This approach was also used successfully with another temporal logic (wSTL) in [ 8 ] . Our MPC horizon strategy differs from Raman et al.’s [ 18 ] fixed- H approach by exploiting TWTL’s automata structure to obtain a task-adaptive horizon, a mechanism that is not available for STL without an automaton. II Preliminaries II-A Dynamical System Consider a discrete-time linear time-invariant (LTI) system: \displaystyle x_{t+1} \displaystyle=Ax_{t}+Bu_{t}, (1) \displaystyle o_{t} \displaystyle=Cx_{t}, where x_{t}\in\mathcal{X}\subseteq\mathbb{R}^{n} is the state, u_{t}\in\mathcal{U}\subseteq\mathbb{R}^{m} is the control input, and o_{t}\in\mathcal{O}\subseteq\mathbb{R}^{p} is the observable output; \mathcal{X} and \mathcal{U} are convex polytopes. \mathbf{o}_{t_{1},t_{2}}:=o_{t_{1}}o_{t_{1}+1}\cdots o_{t_{2}} denotes the output word over [t_{1},t_{2}] . We fix a finite set \Pi=\{\pi_{1},\dots,\pi_{k}\} of atomic propositions. Each \pi_{A}\in\Pi is identified with a satisfaction region A\subseteq\mathcal{O} . An observation o_{t} satisfies \pi_{A} iff o_{t}\in A . In [ 2 ] a general predicate function h is used to represent these atomic propositions, which we spoecialize to an affine form via Assumtion II.1 Assumption II.1 All atomic propositions \pi_{A}\in\Pi have affine predicate functions h(o)=\mathbf{c}_{A}^{T}o-b_{A} , where \mathbf{c}_{A}\in\mathbb{R}^{p} and b_{A},\sigma\in\mathbb{R} , so that A=\{o\mid h(o)>\sigma\} . Without loss of generality we absorb \sigma into b_{A} , so that h(o_{t})=\mathbf{c}_{A}^{T}Cx_{t}-b_{A} throughout. II-B Time Window Temporal Logic TWTL syntax is defined, inductively, as follows [ 19 ] . \phi\;::=\;H^{d}s\mid H^{d}\neg s\mid\phi_{1}\wedge\phi_{2}\mid\phi_{1}\vee\phi_{2}\mid\neg\phi\mid\phi_{1}\cdot\phi_{2}\mid[\phi]^{[a,b]} (2) where s is an atomic proposition with affine predicate function by Assumption II.1 , H^{d} is the hold operator, \cdot is the concatenation operator, and [\phi]^{[a,b]} is the within operator, with d,a,b\in\mathbb{Z}_{\geq 0} and b\geq a . From a given TWTL formula, the time horizion T=||\phi||\in\mathbb{N} is computed, recursively, as follows [ 2 ] . ||\phi||:=\begin{cases}\max(||\phi_{1}||,||\phi_{2}||);&\text{if }\phi\in\{\phi_{1}\wedge\phi_{2},\phi_{1}\vee\phi_{2}\}\\ ||\phi_{1}||;&\text{if }\phi=\neg\phi_{1}\\ ||\phi_{1}||+||\phi_{2}||+\Delta t;&\text{if }\phi=\phi_{1}\cdot\phi_{2}\\ d\Delta t;&\text{if }\phi=H^{d}\pi_{A}\\ b;&\text{if }\phi=[\phi_{1}]^{[a,b]}\end{cases} (3) The hold operator H_{d}s specifies that s\in AP should be repeated for d time units. The semantics of H_{d}\neg s is defined similarly, but for d time units only symbols from AP\setminus\{s\} should appear. The word \mathbf{o}_{t_{1},t_{2}} satisfies \phi_{1}\wedge\phi_{2} , \phi_{1}\vee\phi_{2} , or \neg\phi if \mathbf{o}_{t_{1},t_{2}} satisfies both formulae, at least one formula, or does not satisfy the formula, respectively. The within operator [\phi]_{[a,b]} bounds the satisfaction of \phi to