Sparse Polynomial Zonotopes: A Novel Set Representation for Reachability Analysis

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.

References in corpus (1)

• Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices

Cited by in corpus (3)

• Open- and Closed-Loop Neural Network Verification using Polynomial Zonotopes
• Provably Safe Reinforcement Learning via Action Projection using Reachability Analysis and Polynomial Zonotopes
• Reachability Analysis Using Constrained Polynomial Logical Zonotopes