Skip to main content
Back

Stanford's chreach Turns an Unsolvable Control Problem Into One ODE

A new characterization reduces reachable set estimation for nonlinear systems to integrating an ODE from points on a sphere, cutting samples by orders of magnitude.

  • New paper shows convex hulls of reachable sets equal convex hulls of ODE solutions from the unit sphere.
  • Reduces an infinite-dimensional disturbance search to sampling an (n-1)-dimensional sphere and integrating one ODE each.
  • Published in IEEE Transactions on Automatic Control by Lew, Bonalli, and Pavone.
  • Estimator has quadratic error bound in sample spacing and returns the whole reachable tube in one pass.
  • Demonstrated on neural feedback loop analysis and 7D spacecraft attitude MPC running at 20 Hz.
  • Open-source JAX code available at StanfordASL/chreach.

Reachability analysis is one of those problems in control theory that sounds simple until you try to do it. Given a nonlinear system with bounded disturbances and uncertain starting conditions, what is the set of all states it can end up in at time t? Every serious robust controller design depends on being able to answer that question, and yet the honest answer, in general, has been to over-approximate aggressively and hope the resulting controller is not too conservative.

A recent paper in IEEE Transactions on Automatic Control from Thomas Lew (Toyota Research Institute), Riccardo Bonalli (Paris-Saclay/CNRS), and Marco Pavone (Stanford) offers something unusual for this field: an exact finite-dimensional characterization of the convex hull of a reachable set, along with a sampling algorithm that exploits it. The paper extends their CDC 2023 paper and ships with open-source code.

Why the old tools hurt

The reachable set at time t is, by definition, the image of an infinite-dimensional object: every possible disturbance signal on [0, T] paired with every possible initial state. Existing approaches seek convex over-approximations represented as hyper-rectangles, ellipsoids, zonotopes, or ellipsotopes, using techniques based on conservative linearization, differential inequalities, and Taylor models. These methods scale, but they tend to inflate the estimate well beyond what is actually reachable, which forces controllers to leave large safety margins.

Monte Carlo is the other option: sample a bunch of disturbance sequences, propagate them, and take the convex hull. This works for toy problems, but the sample complexity grows with the number of uncertain variables. Refine your time discretization and the number of uncertain disturbance values grows with it, so naive sampling gets worse the more accurately you model the dynamics.