Auto-discovery of viability envelopes

This work looked at automatically discovering the viability envelope region given only a "black box" that implements the system dynamics. Discovery of the viable region is achieved by random exploration. As the state-space is explored, a graph is constructed of the visited nodes; in the pictures, a magenta edge represents a regular exploration transition, whereas a blue edge indicates a "reconnect" to a previously explored state. A multi-pass approach is used for efficiency, with the initial pass using a coarse simulation time step, while subsequent passes use a smaller one, and only refine the graph at sparsely captured areas or near the estimated envelope edge. The viable region is found from the graph by employing Tarjan's algorithm for finding the Strongly Connected Component.

The images show the computed viability envelope for a vertical rocket (see here for details). The y-axis is the rocket's altitude, whereas x-axis gives the rocket's vertical velocity. Red spheres/circles indicate states in collision, while dimming indicates non-viability. The above images show the viable region for the rocket, whereas the bottom left picture shows the viable-and-reachable region. The bottom right picture shows the computation of the viability envelope for a car on a rectangular track.