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 , compute the set \mathcal X_{k+1} of next states 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 box, 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 \in \mathbb R^n \mid \bm x_\mathrm{min} \leq \bm x \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
    • Subclass of polytopes.
    • Often more efficient than general polytopes.
    • Affine transformation of a unit box.
    • Commonly represented using generator representation (a center and a finite number of generator vectors).
Back to top