Computing Abstractions of Nonlinear Systems

DOI10.1109/TAC.2011.2118950zbMATH Open1368.93178arXiv0910.2187MaRDI QIDQ5347889FDOQ5347889

Gunther Reißig

Publication date: 25 August 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: Sufficiently accurate finite state models, also called symbolic models or discrete abstractions, allow one to apply fully automated methods, originally developed for purely discrete systems, to formally reason about continuous and hybrid systems, and to design finite state controllers that provably enforce predefined specifications. We present a novel algorithm to compute such finite state models for nonlinear discrete-time and sampled systems which depends on quantizing the state space using polyhedral cells, embedding these cells into suitable supersets whose attainable sets are convex, and over-approximating attainable sets by intersections of supporting half-spaces. We prove a novel recursive description of these half-spaces and propose an iterative procedure to compute them efficiently. We also provide new sufficient conditions for the convexity of attainable sets which imply the existence of the aforementioned embeddings of quantizer cells. Our method yields highly accurate abstractions and applies to nonlinear systems under mild assumptions, which reduce to sufficient smoothness in the case of sampled systems. Its practicability in the design of discrete controllers for nonlinear continuous plants under state and control constraints is demonstrated by an example.

Full work available at URL: https://arxiv.org/abs/0910.2187

Mathematics Subject Classification ID

Approximation by convex sets (52A27) Attainable sets, reachability (93B03) Sampled-data control/observation systems (93C57)

Cited In (21)

• Automatic abstraction of non-linear systems using change of bases transformations
• Abstractions of Varying Decentralization Degree for Reachability of Coupled Multiagent Systems
• Asynchronous \(l\)-complete approximations
• On distributed symbolic control of interconnected systems under persistency specifications
• Construction of discontinuous piecewise quadratic value functions in a target control problem
• Finite abstractions with robustness margins for temporal logic-based control synthesis
• Convexity of the images of small balls through nonconvex multifunctions
• Safety synthesis for incrementally stable switched systems using discretization-free multi-resolution abstractions
• Formal controller synthesis from specifications given by discrete-time hybrid automata
• Abstraction-based control synthesis using partial information
• Discrete-State Abstractions of Nonlinear Systems Using Multi-resolution Quantizer
• Modelling and supervisory control of hybrid dynamical systems via fuzzy \(l\)-complete approximation approach
• Automated generation of dynamics-based runtime certificates for high-level control
• Towards scalable synthesis of stochastic control systems
• Refinements of behavioural abstractions for the supervisory control of hybrid systems
• Finite horizon discrete models for multi-agent control systems with coupled dynamics
• Algorithms for exact and approximate linear abstractions of polynomial continuous systems
• Decentralized abstractions for multi-agent systems under coupled constraints
• Finite abstraction of mixed monotone systems with discrete and continuous inputs
• ABS: A formally correct software tool for space-efficient symbolic synthesis
• Optimization-based subdivision algorithm for reachable sets

This page was built for publication: Computing Abstractions of Nonlinear Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5347889)