Temporal Logic Control for Nonlinear Stochastic Systems Under Unknown Disturbances
Ibon Gracia, Luca Laurenti, Manuel Mazo Jr, Alessandro Abate, Morteza Lahijanian · 2024
Read Temporal Logic Control for Nonlinear Stochastic Systems Under Unknown Disturbances by Ibon Gracia, Luca Laurenti, Manuel Mazo Jr, Alessandro Abate, Morteza Lahijanian (2024) 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-2412-11343.txt.
Introduction
Ibon Gracia, Luca Laurenti, Manuel Mazo and colleagues build controllers that obey time-based rules for systems shaken by unknown random disturbances in 2024. Their framework learns a model of the system from observations, expressed as a Markov decision process with quantified uncertainty.
The uncertainty is shaped as a convex polytope for each state and action, built from a two-layer grid plus concentration inequalities. That shape gives tighter bounds than earlier methods and lets a tailored synthesis algorithm run efficiently. In case studies the approach performed much better than the state of the art. The result is a data-driven route to control with formal guarantees, even when the disturbance pattern is never observed directly.
Catalog record
| CREATOR | Ibon Gracia, Luca Laurenti, Manuel Mazo Jr, Alessandro Abate, Morteza Lahijanian |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-11343
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Temporal Logic Control for Nonlinear Stochastic Systems Under Unknown Disturbances Thanks: The authors are with the Smead Department of Aerospace Engineering Sciences, CU Boulder, Boulder, CO, {ibon.gracia, morteza.lahijanian}@colorado.edu, the Delft Center for Systems and Control, Faculty of Mechanical, Maritime and Materials Engineering, Delft University of Technology {m.mazo,l.laurenti}@tudelft.nl and the Department of Computer Science, University of Oxford [email protected] Ibon Gracia, Luca Laurenti, Manuel Mazo Jr, Alessandro Abate, Morteza Lahijanian Abstract . In this paper, we present a novel framework to synthesize robust strategies for discrete-time nonlinear systems with random disturbances that are unknown, against temporal logic specifications. The proposed framework is data-driven and abstraction-based: leveraging observations of the system, our approach learns a high-confidence abstraction of the system in the form of an uncertain Markov decision process (UMDP). The uncertainty in the resulting UMDP is used to formally account for both the error in abstracting the system and for the uncertainty coming from the data. Critically, we show that for any given state-action pair in the resulting UMDP, the uncertainty in the transition probabilities can be represented as a convex polytope obtained by a two-layer state discretization and concentration inequalities. This allows us to obtain tighter uncertainty estimates compared to existing approaches, and guarantees efficiency, as we tailor a synthesis algorithm exploiting the structure of this UMDP. We empirically validate our approach on several case studies, showing substantially improved performance compared to the state-of-the-art. 1. Introduction The synthesis of safe strategies for stochastic systems is critical in ensuring reliable and safe operations in domains such as robotics, autonomous vehicles, and cyber-physical systems [ 1 , 2 ] . A key challenge arises when the system dynamics include unknown random disturbances, making it difficult to account for uncertainties while guaranteeing performance against high-level complex specifications. Existing methods often assume known distributions for the disturbances or rely on abstractions with overly conservative uncertainty estimates, limiting their scalability and applicability to complex systems. This paper aims to address these gaps by presenting a novel framework to synthesize optimal strategies for nonlinear stochastic systems with unknown disturbances, ensuring both formal guarantees and computational efficiency. Our framework employs a data-driven, abstraction-based approach to strategy synthesis for stochastic systems with unknown noise under linear temporal logic over finite traces (LTL f ) [ 3 ] specifications. Starting with data from the system’s trajectories, we construct a high-confidence abstraction in the form of an uncertain Markov decision process (UMDP) [ 4 ] , a flexible model that captures complex uncertainties. Unlike existing methods relying on interval-based abstractions or conservative assumptions, our framework represents transition probability uncertainties as convex polytopes. These sets are derived through a novel two-layer discretization scheme and learning the support of the unknown disturbance. This leads to tighter uncertainty sets and less conservative results compared to existing methods. Exploiting this UMDP structure, we introduce a synthesis algorithm for LTL f specifications that simplifies the computation, reducing the complexity of standard UMDP linear programming approaches. By incorporating uncertainties from both abstraction errors and data limitations, our framework yields a strategy that is robust. Our empirical evaluations over various types of systems reveals the efficacy of this approach over existing methods, namely in data efficiency, tightness of results, and scalability. The main contributions of this paper are fourfold: (i) a novel framework for synthesizing strategies for nonlinear stochastic systems under non-additive, unknown disturbances with LTL f specifications, (ii) a distribution-agnostic, data-driven construction of UMDP abstraction with a specific structure that reduces conservatism of existing abstraction-based techniques, (iii) an efficient tailored synthesis algorithm for this UMDP abstraction, which does not introduce additional conservatism, and (iv) a series of case studies and benchmarks that show superiority of the framework over the state-of-the-art, with up to 3 orders of magnitude improvement in sample complexity and an order of magnitude reduction in computation time. Related Work Abstractions of stochastic systems to finite Markov decision processes (MDPs) are powerful tools for controller synthesis on highly-complex systems under complex logic specifications [ 2 ] . In particular, Interval MDPs (IMDPs) [ 5 , 6 ] abstract systems by presenting uncertain transition probabilities within intervals, capturing the full range of system behaviors. For example, [ 7 ] efficiently abstracts linear systems with additive Gaussian noise, while [ 8 ] extends this to nonlinear dynamics. Uncertain MDPs (UMDPs) [ 4 , 9 ] generalize IMDPs by allowing transition probabilities to belong to more complex sets and have been used for strategy synthesis against specifications such as linear temporal logic (LTL) [ 10 ] . However, these abstractions typically require system models, which are often unavailable in practice. To address model uncertainty, various methods leverage Gaussian processes [ 11 ] , neural networks [ 12 ] , and ambiguity sets [ 13 ] , which are then abstracted as IMDPs or UMDPs. Statistical tools like the scenario approach have also been used to abstract stochastic [ 14 , 15 ] , non-deterministic [ 16 ] , and deterministic systems [ 17 , 18 ] . Also, techniques such as super-martingales and barrier functions enable safety verification and control synthesis for general dynamics [ 19 , 20 , 21 ] . Nevertheless, all these works assume that the disturbance distribution is known. When disturbance distributions are uncertain, some works combine IMDP abstractions with statistical tools [ 14 , 15 , 22 ] , while others employ barrier certificates with the scenario approach for safety verification [ 23 ] . Another approach [ 24 ] constructs Wasserstein ambiguity sets from data samples to abstract systems as UMDPs, which account for the uncertainty regarding the unknown distributions. However, these methods typically assume simple dynamics or additive noise. For general dynamics with unknown disturbance distributions, only a few works exist. [ 25 ] uses barrier certificates for safety verification, and [ 26 ] extends the ambiguity set approach to nonlinear dynamics, formally characterizing the guarantees of these approaches. Both assume that certain distribution-related properties, such as variance or support, are known—an assumption often unrealistic in practice, and also suffer from high sample complexity, especially under high-confidence requirements. Our work overcomes these limitations by removing assumptions about disturbance distributions and offering a data-efficient and scalable approach suitable for systems with general dynamics. 2. Problem Formulation In this work the focus is on discrete-time stochastic systems given by (2.1) \displaystyle\bm{{x}}_{k+1}=f(\bm{{x}}_{k},u_{k},\bm{{w}}_{k}), where \bm{{x}}_{k}\in\mathbb{R}^{n} denotes the state at time k\in\mathbb{N}_{0} , u_{k}\in U\subset\mathbb{R}^{m} is the control input chosen from a finite set U , and \bm{{w}}_{k}\in W\subseteq\mathbb{R}^{d} is the disturbance. The latter is a sequence of independent and identically distributed (i.i.d.) random variables on the probability space (W,\mathcal{B}(W),P_{W}) , with \mathcal{B} being the Borel \sigma -algebra on W , and where the support W and probability distribution P_{W} of \bm{{w}}_{k} are unknown . The vector field (possibly nonlinear) f:\mathbb{R}^{n}\times U\times W\rightarrow\mathbb{R}^{n} is assumed to be Lipschitz continuous on its third argument, uniformly for all values of its first argument on some set. Assumption 2.1 . There exists a set X\subset\mathbb{R}^{n} , such that, for every u\in U , there exists a constant L_{u}>0 such that, for all x\in X , w,w^{\prime}\in W , it holds that \|f(x,u,w)-f(x,u,w^{\prime})\|\leq L_{u}\|w-w^{\prime}\| . In lieu of unknown W and P_{W} , we assume a dataset on the disturbance