Reachability analysis

Robust versions exist for cases with uncertain parameters, or disturbances.

Reachability computations for hybrid systems

There are two major approaches to reachibility analysis for hybrid systems

Reachability analysis based on optimal control

The former does not need much discussion here. We have already discussed all the crucial concepts and facts when introducing the MPC for hybrid systems. Infeasibility of the corresponding optimization problem indicates unreachability. Thefefore, we focus on the latter here.

Reachability analysis based on set propagation

Basic computational steps for reachability analysis based on set propagation

Given a set \mathcal X_k of current states \bm x(k), compute the set \mathcal X_{k+1} of next states \bm x(k+1) of a discrete-time (or discretized) system such that
\bm x(k+1) = \mathbf f(\bm x(k)).

In the case of a linear discrete-time system, and the set of initial states characterized by a (multidimensional) interval, the problem is to characterize the set \mathcal X_{k+1} of all possible (reachable) \bm x(k+1) satisfying \begin{aligned} \bm x(k+1) &= \mathbf A \bm x(k),\\ \bm x(k) &\in \mathcal X_k = \{\bm x(k) \in \mathbb R^n \mid \bm x_\mathrm{min} \leq \bm x(k) \leq \bm x_\mathrm{max}\}. \end{aligned}

Typically, inner or outer approximations of the set of all possible next states are used, depending on the context (alowed vs forbidden regions of the state space).

Sets to be propagated

Certain sets are (computationally) easier to propagate than others:

  • Intervals
  • Polyhedra (both in V and H representations)
  • Ellipsoids
  • Zonotopes
Zonotopes

While the first three types of sets are well-known, we will discuss the forth in the list – zonotopes. Zonotopes are a class of polytopes. They are commonly used in reachability analysis because computationally they are often more efficient than general polytopes.

The can be obtained by an affine transformation of a unit box, that is, \mathcal Z = \{\bm x\in\mathbb R^n \mid \bm x = \mathbf A \bm y+\mathbf b, \; \bm y\in\mathbb R^m, \; |y_i|\leq 1\}, but most commonly they are represented using generator representation \mathcal Z = \{\bm x\in\mathbb R^n \mid \bm x = \mathbf c + \sum_{i=1}^p \alpha_i \mathbf g_i, \; \mathbf g_i\in\mathbb R^n, \; \alpha_i\in\mathbb R, \;|\alpha_i|\leq 1\}, where \mathbf c\in\mathbb R^n is the center and \mathbf g_i\in\mathbb R^n are the generators.

Back to top