A MATLAB Toolbox for Set-based Control Systems Analysis Using Hybrid Zonotopes (2024)

Definition 1

Definition 2

Definition 3

As shown in Fig. 1, a zonotope is an affine image of the unit hypercube $\mathcal{B}_{\infty}^{n_{g}}$, while a constrained zonotope is an affine image of the constrained unit hypercube $\mathcal{B}_{\infty}^{n_{g}}(A,b)$. By introducing $n_{b}$ binary factors, a hybrid zonotope is equivalent to the union of $|\mathcal{T}|\leq 2^{n_{b}}$ constrained zonotopes as

where the $i^{th}$ constrained zonotope (4b) has its center and constraint vector shifted by the $i^{th}$ value of the discrete set $\mathcal{T}=\{\xi_{i}^{b}\in\{-1,1\}^{n_{b}}~{}|~{}\mathcal{Z}_{c,i}\not=\emptyset\}$ mapped by $G^{b}$ and $A^{b}$, respectively. Therefore, while a constrained zonotope is the affine image of the intersection of a hypercube and hyperplanes, a hybrid zonotope is the affine image of multiple intersections of a hypercube and shifted hyperplanes, as shown in Fig. 1.

Historically, the computational benefits of using a zonotope set representation come from the relative ease, numerical accuracy, and scalability of computing linear mappings and Minkowski sums, where given matrix $R\in\mathbb{R}^{m\times n}$ and zonotopes $\mathcal{Z},\mathcal{W}\subset\mathbb{R}^{n}$,

The hybrid zonotope $\mathcal{Z}_{h}=\langle G^{c},G^{b},c,A^{c},A^{b},b\rangle$ is defined using zonoLAB as

assuming the variables Gb,c,Ac,Ab,b are predefined. Zonotopes and constrained zontopes are defined similarly. Sets can also be recast to a more expressive representation. For example, a constrained zonotope, Zc, can be recast as a hybrid zonotope using

which automatically sets Gb and Ab to matrices of all zeros of the appropriate dimension.

A convex polytopic set defined in H-rep as $\mathcal{H}=\{x\in\mathbb{R}^{n}|Hx\leq f\}$, where $H\in\mathbb{R}^{n_{h}\times n}$, $f\in\mathbb{R}^{n_{h}}$, and $n_{h}$ is the number of halfspaces, can be represented as a constrained zonotope using

The union of $N$ sets in H-rep can be represented as a hybrid zonotope using

where ollection is a $N\times 1$ cell array where the $i^{th}$ cell is $[H_{i}\;f_{i}]$ corresponding to the $i^{th}$ set $\mathcal{H}_{i}=\{x\in\mathbb{R}^{n}|H_{i}x\leq f_{i}\}$. Note that the $N$ sets do not need to have the same number of halfspaces.

For a collection of $n_{v}$ vertices $\{v_{1},\dots,v_{n_{v}}\}$, where $v_{i}\in\mathbb{R}^{n}$, a set $\mathcal{V}$ defined in V-rep is conventionally considered as the convex hull of the vertices, $\mathcal{V}=\text{conv}(\{v_{1},\dots,v_{n_{v}}\})$. However, zonoLAB provides the flexibility to use this collection of vertices to define a set as the union of the vertices, as the union of line segments between vertices, as the conventional convex hull of these vertices, or some combination of these three [23]. Thus, in addition to providing the vertex matrix $V=[v_{1},\dots,v_{n_{v}}]\in\mathbb{R}^{n\times n_{v}}$, an incidence matrix $M\in\mathbb{R}^{n_{v}\times N}$ must also be provided, where the rows correspond to the $n_{v}$ vertices and the columns correspond to the desired $N$ convex sets. Elements $M_{i,j}=1$ if the $i^{th}$ vertex is a member of the $j^{th}$ set. All other entries are zero. For example, if $M=\mathbf{I}_{n_{v}}$, the result is a hybrid zonotope representing the union of the $n_{v}$ vertices. If $M$ is defined such that $M_{1,1}=M_{1,N}=1$ and $M_{i,i-1}=M_{i,i}=1,\forall i\in\{2,\dots,n_{v}\}$, then the result is a hybrid zonotope representing the line segments between each consecutive vertex in the vertex matrix, including a line segment between the first and last vertices. Finally, if $M=\mathbf{1}_{n_{v}\times 1}$, then the result is a constrained zonotope representing the convex hull of the vertices. In general, with matrices V and M defined, the desired set is created using

where M} is a $1\times 2$ cell array.

Consider a linear, discrete-time, time-invariant system $x_{k+1}=Ax_{k}+Bu_{k}$, where $x_{k}\in\mathcal{R}_{k}\subset\mathbb{R}^{n}$, $u_{k}\in\mathcal{U}\subset\mathbb{R}^{m}$, and $A,B,\mathcal{R}_{k}$, and $\mathcal{U}$ are known. The one-step reachable set $\mathcal{R}_{k+1}$ is computed as

Using zonoLAB, with A, B, Rk, and U predefined, the reachable set lus can be computed using methods mes and s of the tractZono class as

The one-step reachable set $\mathcal{R}_{k+1}$ is also known as the successor set, $\text{Suc}(\mathcal{R}_{k},\mathcal{U})$, which can be defined for the more general nonlinear dynamics $x_{k+1}=f(x_{k},u_{k})$ as

Mathematically, the open-loop state-update set $\Psi\subset\mathbb{R}^{2n+m}$ is defined as

where $\text{D}(\Psi)\subset\mathbb{R}^{n+m}$ is the domain set of $\Psi$, which is chosen as a region of interest for analysis, as in [29].

Using the open-loop state-update set $\Psi$, with domain set defined such that $\mathcal{R}_{k}\times\mathcal{U}\subseteq\text{D}(\Psi)$, the successor set can be computed using projection and generalized intersection operations as

While (6) provides a method for computing the one-step reachable set, a state-update set $\Psi$ can also be used to compute $\mathcal{R}_{k+1}$. Assuming the domain set $\text{D}(\Psi)\in\mathbb{R}^{n+m}$ is known such that $\mathcal{R}_{k}\times\mathcal{U}\subseteq\text{D}(\Psi)$, then

This state-update set and the successor set operation from (9) can be used to compute $\mathcal{R}_{k+1}$ using zonoLAB as

When comparing the use of (9) and (10) with the use of (6), it may appear that there are considerable disadvantages with the state-update set approach, namely $\mathcal{R}_{k+1}$ is only computed accurately if $\mathcal{R}_{k}\times\mathcal{U}\subseteq\text{D}(\Psi)$ and the resulting set is a Zono (due to the use of generalized intersection in (9)) instead of the o object obtained when using (6) (assuming $\mathcal{R}_{k}$ and $\mathcal{U}$ are o objects). However, the use of state-update sets (and set-based mappings in general) allows reachability analysis based on (9) to be easily extended to hybrid systems (including MLD and PWA systems) and nonlinear systems. Additionally, as discussed in [29], state-update sets can also be used to compute precursor sets for backward reachability analysis. The following sections demonstrate how set-based mappings (including state-update sets) provide a unifying framework for several different applications of reachability analysis.

Based on the work from [5], zonoLAB can compute the reachable sets of MLD systems, a modeling framework combining continuous and binary variables with logical relations in mixed-integer inequalities to express complex dynamic systems [33]. A linear discrete-time MLD system is expressed as

where $x\in\mathbb{R}^{n_{xc}}\times\{0,1\}^{n_{xl}}$ are the system states, $u\in\mathbb{R}^{n_{uc}}\times\{0,1\}^{n_{ul}}$ are the control inputs, and $w\in\mathbb{R}^{n_{rc}}\times\{0,1\}^{n_{rl}}$ are auxiliary variables. The number of inequality constraints is denoted by $n_{e}$ such that $E_{aff}\in\mathbb{R}^{n_{e}}$. Assuming knowledge of A, , , ff, , , , and ff along with the sets Rk and U (such that $x_{k}\in\mathcal{R}_{k}$ and $u_{k}\in\mathcal{U}$), the compact set W (such that $w_{k}\in\mathcal{W}\subset{\mathbb{R}^{n_{rc}}}\times\{0,1\}^{n_{rl}}$ must also be provided.⁴⁴4The set W can be generated automatically using the modeling tool Hybrid System DEscription Language (HYSDEL) [34]. Using zonoLAB, the successor set for the MLD system is computed as

using affine mappings (*), Minkowski sums (+), and generalized halfspace intersections (fspaceIntersection) following the procedure from [5] as

While MLD and PWA systems are equivalent [35], it may be more computationally-efficient to compute the reachable set of a PWA system directly. Using zonoLAB, state update sets $\Psi_{i}$ can be defined as in (10) using the linear dynamics over a domain $D_{i}$, where $D_{i}$ corresponds to the $i^{th}$ convex polytope of the PWA system. For a two-state autonomous system with two regions of linear dynamics, the one-set reachable set can be computed using

Based on the work from [21], hybrid zonotopes can exactly represent the piecewise linear feedback control law associated with linear MPC formulations of the form

where $x_{k}\in\mathbb{R}^{n_{x}}$ is the state vector and $u_{k}\in\mathbb{R}^{n_{u}}$ is the input vector, related by linear dynamics with $A\in\mathbb{R}^{{n_{x}}\times{n_{x}}}$ and $B\in\mathbb{R}^{{n_{x}}\times{n_{u}}}$. The sampled state of the system is $x_{0}$. The inputs, predicted states, and predicted terminal state are constrained to the convex polytopic sets $\mathcal{U}\subset\mathbb{R}^{n_{u}}$, $\mathcal{X}\subseteq\mathbb{R}^{n_{x}}$, and $\mathcal{X}_{N}\subseteq\mathcal{X}$ and are penalized in the quadratic cost function with weight matrices $R\succ 0$, $Q\succeq 0$, and $Q_{N}\succeq 0$, respectively. To demonstrate this capability, the mpleDoubleIntegrator.m file provided with zonoLAB computes and plots the MPC control law as a hybrid zonotope for the double integrator example from [21].

To perform closed-loop reachability analysis of MPC, the open-loop state-update set $\Psi$ from (8) can be combined with the hybrid zonotope representation of the feedback control law (referred to as the state-input map in [23]). It is assumed that the hybrid zonotope $\Theta\subset\mathbb{R}^{n+m}$ maps the measured state $x_{k}$ to the applied control input $u_{k}$ such that $(x_{k},u_{k})\in\Theta$ and is defined over a domain $D(\Theta)$ such that $\mathcal{R}_{k}\subseteq D(\Theta)$ for all $k$. Then, the closed-loop state-update set $\Phi\subset\mathbb{R}^{2n}$ such that $(x_{k},x_{k+1})\in\Phi$ is computed as

In addition to forward reachability analysis, this closed-loop state-update set can also be used for backward reachability analysis. For example, in [29], backward reachable sets were used to compute the maximal positive invariant set of a closed-loop system under an MPC control law.

Based on the work from [22], zonoLAB can exactly represent the input-output mapping of an $L$-layered, ReLU-based, feed-forward, fully-connected neural network $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ mapping inputs $x\in\mathbb{R}^{n}$ to outputs $y=f(x)\in\mathbb{R}^{m}$ such that

where $W^{\ell}\in\mathbb{R}^{n_{\ell+1}\times n_{\ell}}$ and $b^{\ell}\in\mathbb{R}^{n_{\ell+1}}$ are the weight matrix and bias vector, respectively, between layers $\ell$ and $\ell+1$, with $n_{0}=n$ and $n_{L+1}=m$. All activation functions $\phi$ are ReLU functions that operate element-wise, i.e., for the pre-activation vector $v^{\ell+1}=W^{\ell}x^{\ell}+b^{\ell}\in\mathbb{R}^{n_{\ell+1}}$,

where the ReLU function is defined as $\varphi(v_{i})=\max\{0,v_{i}\}$. The key insight from [22] is that a single ReLU activation function $x_{i}=\varphi(v_{i})$ can be represented as a hybrid zonotope $\Phi\subset\mathbb{R}^{2}$ containing points $[v_{i}\;x_{i}]^{\top}$ over a predetermined domain $v_{i}\in[-a,a]$. The user-defined parameter $a>0$ is chosen large enough so that $|v_{i}|\leq a$ for all anticipated values of $v_{i}$. Specifically, a single ReLU activation function is represented as a hybrid zonotope with $n_{g}=4$ continuous generators, $n_{b}=1$ binary generator, and $n_{c}=2$ constraints. Over the domain $\mathcal{X}$ such that $x\in\mathcal{X}$, the entire feed-forward ReLU neural network with $n_{N}$ ReLU activation functions is exactly represented as a hybrid zonotope $\mathcal{F}$ with $n_{g}=n_{x}+4n_{N}$ continuous generators, $n_{b}=n_{N}$ binary generators, and $n_{c}=3n_{N}$ constraints, assuming $\mathcal{X}$ is a zonotope with $n_{x}$ generators.

Using zonoLAB, the hybrid zonotope representation of a neural network is computed as

where X is a o object with $n_{x}$ generators defining the domain $\mathcal{X}$,Ws is a $1\times L$ cell array containing the weight matrices, bs is a $1\times L$ cell array containing the bias vectors, and a defines the domain for each reLU activation function. The output NN is the hybrid zonotope $\mathcal{F}$ such that $(x,y)\in\mathcal{F}$ and the output Y is the set of outputs from the neural network produced by inputs in the set X.