Geometric methods for fast reachability analysis
Reachability analysis is a method of studying the possible behaviours of a dynamical system under the effect of inputs, disturbances or uncertainties. It provides us with the ability to study all possible trajectories of the system's state, allowing us to make definitive assertions about the safety and reliability of perturbed or uncertain systems. However, the reachability analysis of state space models can be computationally demanding. As the number of states in the model increases, the time complexity suffers from Bellman's "curse of dimensionality."
We intend to tackle this problem for smooth nonlinear systems by exploiting separations in time scale. Often in physical systems, trajectories converge quickly to an invariant submanifold of state space. When this is the case, the mathematics of geometric singular perturbation theory allows us to determine the behaviour of the entire system by studying the fast transient dynamics away from the invariant manifold separately from the slow dynamics on the manifold.
Since the complexity is exponential in the state dimension, doing 2 lower-dimensional computations is easier than 1 high-dimensional one. Thus we split the problem into steps:
- Compute the slow manifold.
- Project the initial states onto the slow manifold along trajectories of the system’s flow.
- Perform the reachability analysis in reduced coordinates. Provided that the slow manifold is of small dimension, we can perform this computation using level set methods.