Convex Hulls of Reachable Sets
This work addresses a fundamental problem in control theory for applications like neural feedback loop analysis and robust MPC, offering a more efficient and accurate method, though it appears incremental as it builds on existing over-approximation tools.
The paper tackles the challenge of computing reachable sets for nonlinear systems with disturbances and uncertain initial conditions, which are critical in control but difficult to compute accurately, by characterizing their convex hulls through an ordinary differential equation, enabling an efficient sampling-based algorithm for over-approximation with derived error bounds.
We study the convex hulls of reachable sets of nonlinear systems with bounded disturbances and uncertain initial conditions. Reachable sets play a critical role in control, but remain notoriously challenging to compute, and existing over-approximation tools tend to be conservative or computationally expensive. In this work, we characterize the convex hulls of reachable sets as the convex hulls of solutions of an ordinary differential equation with initial conditions on the sphere. This finite-dimensional characterization unlocks an efficient sampling-based estimation algorithm to accurately over-approximate reachable sets. We also study the structure of the boundary of the reachable convex hulls and derive error bounds for the estimation algorithm. We give applications to neural feedback loop analysis and robust MPC.