Sparse Polynomial Zonotopes: A Novel Set Representation for Reachability Analysis

DOI10.1109/TAC.2020.3024348MaRDI QIDQ4957696zbMATH OpenFDO

Authors Niklas Kochdumper, Matthias Althoff

Publication date 9 September 2021

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

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

zbMATH Keywords

hybrid systemsnonlinear dynamicsreachability analysissparse polynomial zonotopes

Mathematics Subject Classification ID

Attainable sets, reachability (93B03) Algebraic methods (93B25) Nonlinear systems in control theory (93C10) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30)

Abstract: We introduce sparse polynomial zonotopes, a new set representation for formal verification of hybrid systems. Sparse polynomial zonotopes can represent non-convex sets and are generalizations of zonotopes, polytopes, and Taylor models. Operations like Minkowski sum, quadratic mapping, and reduction of the representation size can be computed with polynomial complexity w.r.t. the dimension of the system. In particular, for reachability analysis of nonlinear systems, the wrapping effect is substantially reduced using sparse polynomial zonotopes, as demonstrated by numerical examples. In addition, we can significantly reduce the computation time compared to zonotopes when dealing with nonlinear dynamics.

Cited in

(23)

• Adaptive reachability algorithms for nonlinear systems using abstraction error analysis
• Functional sets with typed symbols: Mixed zonotopes and polynotopes for hybrid nonlinear reachability and filtering
• Geometric control of hybrid systems
• Adaptive parameter tuning for reachability analysis of nonlinear systems
• Using Intersection of Unions to Minimize Multi-directional Linearization Error in Reachability Analysis
• Event-based fault estimation and compensation for discrete-time systems via zonotopes
• Constrained polynomial zonotopes
• Hybrid zonotopes: A new set representation for reachability analysis of mixed logical dynamical systems
• Towards optimal space-time discretization for reachable sets of nonlinear control systems
• Computation of invariant sets for discrete‐time uncertain systems
• Reachability Analysis for Linear Systems with Uncertain Parameters using Polynomial Zonotopes
• Automatic Abstraction Refinement in Neural Network Verification using Sensitivity Analysis
• Reachability of Koopman Linearized Systems Using Random Fourier Feature Observables and Polynomial Zonotope Refinement
• Towards global neural network abstractions with locally-exact reconstruction
• Fully automated verification of linear time-invariant systems against signal temporal logic specifications via reachability analysis
• Polynomial logical zonotope: a set representation for reachability analysis of logical systems
• Schatten-\(p\) radius: optimality criterion and optimization for basic ellipsotopes with application to zonotopes and ellipsoids
• Robust identification of hybrid automata from noisy data
• Sparse intersection checking for sparse polynomial zonotopes
• Fault detection for Lipschitz nonlinear systems using robust observer and ellipsoidal analysis
• Reachability of Koopman linearized systems using explicit kernel approximation and polynomial zonotope refinement
• Falsification using reachability of surrogate Koopman models
• Reachability analysis for linear systems with uncertain parameters using polynomial zonotopes

This page was built for publication: Sparse Polynomial Zonotopes: A Novel Set Representation for Reachability Analysis

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