John N. Maidens

Computation of high-dimensional viability kernels

When analysing safety-critical systems we wish to provide a mathematical guarantee that, despite limited control authority, the system’s state can be confined to a region of the state space designated as safe. The largest subset of the safe region for which there exists an admissible control input that keeps the state within the safe region is known as the viability kernel, or maximal controlled invariant set.

Many methods are known for computing viability kernels in low-dimensional systems, but these existing methods rely on gridding the state space and hence their time complexity increases exponentially with the state dimension. Finding a connection between reachability and viability theory has enabled us to approximate the viability kernel using Lagrangian methods which scale well with the state dimension.

We have developed new viability kernel approximation algorithms using polytope-, ellipsoid- and support vector-based set representations. Using the support vector and ellipsoidal techniques, we are able to accurately approximate the viability kernel for systems of much larger state dimension than was previously feasible using existing Eulerian methods.

Related publications:

  1. Computing the Viability Kernel Using Maximal Reachable Sets.
    Shahab Kaynama, John Maidens, Meeko Oishi, Ian M. Mitchell, Guy A. Dumont.
    Hybrid Systems Computation and Control (April 2012).
    • © ACM, 2012. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 15th International Conference on Hybrid Systems: Computation & Control (April 2012), doi: 10.1145/2185632.2185644
  2. Lagrangian methods for approximating the viability kernel in high-dimensional systems.
    John N. Maidens, Shahab Kaynama, Meeko Oishi, Ian M. Mitchell, Guy A. Dumont.
    Under review
  3. Scalable computation of viability kernels and a viability-theoretic approach to guaranteeing safety for closed-loop medical devices.
    John Norman Maidens
    Master of Applied Science Thesis
    University of British Columbia     (July 2012)