A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis

[Paper] [Code] [Video (hardware results)]

Forward reachability analysis is at the core of many applications, from neural network verification, to motion planning and trajectory optimization for uncertain and meta-learned dynamical systems. However, this problem is notoriously challenging, and current approaches tend to be either too restrictive, too slow, too conservative, or approximate and therefore lack accuracy guarantees.

We previously proposed an efficient sampling-based algorithm for general-purpose reachability analysis. By (1) sampling inputs, (2) evaluating their images in the true reachable set, and (3) taking their ε-padded convex hull as a set estimator, this algorithm applies to general problem settings. This algorithm is deceptively simple to implement, yet outperforms other more complex algorithms in many applications. Why is this the case?

In this paper, we derive asymptotic and finite-sample accuracy guarantees using random set theory. This analysis informs algorithmic design to obtain an ε-close reachable set approximation with high probability, provides insights into which reachability problems are most challenging, and motivates safety-critical applications of the technique.

On a neural network verification task, we show that this approach (RandUP) is more accurate (in Hausdorff distance dH) and faster (given a sufficient number of samples M) than prior work.

We also design a robust model predictive controller (MPC) that we demonstrate in hardware experiments. By explicitly considering uncertainty, our controller ensures constraints satisfaction despite model missmatch, in contrast to a baseline that collides with an obstacle.

Bibtex

@inproceedings{LewJansonEtAl2022,
	author = {Lew, T. and Janson, L. and Bonalli, R. and Pavone, M.},
	title = {A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis},
	year = {2022},
	booktitle = {Learning for Dynamics \& Control Conference},
}