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

Thomas Lew, Lucas Janson, Riccardo Bonalli, Marco Pavone
Proceedings of The 4th Annual Learning for Dynamics and Control Conference, PMLR 168:1086-1099, 2022.

Abstract

In this work, we analyze an efficient sampling-based algorithm for general-purpose reachability analysis, which remains a notoriously challenging problem with applications ranging from neural network verification to safety analysis of dynamical systems. By sampling inputs, evaluating their images in the true reachable set, and taking their $\epsilon$-padded convex hull as a set estimator, this algorithm applies to general problem settings and is simple to implement. Our main contribution is the derivation of asymptotic and finite-sample accuracy guarantees using random set theory. This analysis informs algorithmic design to obtain an $\epsilon$-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 is more accurate and significantly faster than prior work. Informed by our analysis, we also design a robust model predictive controller that we demonstrate in hardware experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v168-lew22a, title = {A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis}, author = {Lew, Thomas and Janson, Lucas and Bonalli, Riccardo and Pavone, Marco}, booktitle = {Proceedings of The 4th Annual Learning for Dynamics and Control Conference}, pages = {1086--1099}, year = {2022}, editor = {Firoozi, Roya and Mehr, Negar and Yel, Esen and Antonova, Rika and Bohg, Jeannette and Schwager, Mac and Kochenderfer, Mykel}, volume = {168}, series = {Proceedings of Machine Learning Research}, month = {23--24 Jun}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v168/lew22a/lew22a.pdf}, url = {https://proceedings.mlr.press/v168/lew22a.html}, abstract = {In this work, we analyze an efficient sampling-based algorithm for general-purpose reachability analysis, which remains a notoriously challenging problem with applications ranging from neural network verification to safety analysis of dynamical systems. By sampling inputs, evaluating their images in the true reachable set, and taking their $\epsilon$-padded convex hull as a set estimator, this algorithm applies to general problem settings and is simple to implement. Our main contribution is the derivation of asymptotic and finite-sample accuracy guarantees using random set theory. This analysis informs algorithmic design to obtain an $\epsilon$-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 is more accurate and significantly faster than prior work. Informed by our analysis, we also design a robust model predictive controller that we demonstrate in hardware experiments.} }
Endnote
%0 Conference Paper %T A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis %A Thomas Lew %A Lucas Janson %A Riccardo Bonalli %A Marco Pavone %B Proceedings of The 4th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2022 %E Roya Firoozi %E Negar Mehr %E Esen Yel %E Rika Antonova %E Jeannette Bohg %E Mac Schwager %E Mykel Kochenderfer %F pmlr-v168-lew22a %I PMLR %P 1086--1099 %U https://proceedings.mlr.press/v168/lew22a.html %V 168 %X In this work, we analyze an efficient sampling-based algorithm for general-purpose reachability analysis, which remains a notoriously challenging problem with applications ranging from neural network verification to safety analysis of dynamical systems. By sampling inputs, evaluating their images in the true reachable set, and taking their $\epsilon$-padded convex hull as a set estimator, this algorithm applies to general problem settings and is simple to implement. Our main contribution is the derivation of asymptotic and finite-sample accuracy guarantees using random set theory. This analysis informs algorithmic design to obtain an $\epsilon$-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 is more accurate and significantly faster than prior work. Informed by our analysis, we also design a robust model predictive controller that we demonstrate in hardware experiments.
APA
Lew, T., Janson, L., Bonalli, R. & Pavone, M.. (2022). A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis. Proceedings of The 4th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 168:1086-1099 Available from https://proceedings.mlr.press/v168/lew22a.html.

Related Material