Reachability analysis
For autonomous systems: Given a set of initial states \mathcal X_0, determine the set of states \mathcal X_{\mathrm{reach}} that can be reached from X_0 over the time interval (0,t).
For non-autonomous (controlled) system: Given a set of initial states \mathcal X_0, determine the set of states \mathcal X_{\mathrm{reach}} that can be reached from X_0 over the time interval (0,t) using some control.
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
- Checking a feasibility of an optimal control problem for a MLD system. This is used in Hybrid Toolbox (and Hysdel): http://cse.lab.imtlucca.it/~bemporad/hybrid/toolbox/
- Computing the reachable sets by set propagation techniques.
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).