Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling

Thomas Lew, Marco Pavone
Proceedings of the 2020 Conference on Robot Learning, PMLR 155:2055-2070, 2021.

Abstract

Reachability analysis is at the core of many applications, from neural network verification, to safe trajectory planning of uncertain 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 guarantees. In this paper, we propose a simple yet effective sampling-based approach to perform reachability analysis for arbitrary dynamical systems. Our key novel idea consists of using random set theory to give a rigorous interpretation of our method, and prove that it returns sets which are guaranteed to converge to the convex hull of the true reachable sets. Additionally, we leverage recent work on robust deep learning and propose a new adversarial sampling approach to robustify our algorithm and accelerate its convergence. We demonstrate that our method is faster and less conservative than prior work, present results for approximate reachability analysis of neural networks and robust trajectory optimization of high-dimensional uncertain nonlinear systems, and discuss future applications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v155-lew21a, title = {Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling}, author = {Lew, Thomas and Pavone, Marco}, booktitle = {Proceedings of the 2020 Conference on Robot Learning}, pages = {2055--2070}, year = {2021}, editor = {Kober, Jens and Ramos, Fabio and Tomlin, Claire}, volume = {155}, series = {Proceedings of Machine Learning Research}, month = {16--18 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v155/lew21a/lew21a.pdf}, url = {https://proceedings.mlr.press/v155/lew21a.html}, abstract = {Reachability analysis is at the core of many applications, from neural network verification, to safe trajectory planning of uncertain 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 guarantees. In this paper, we propose a simple yet effective sampling-based approach to perform reachability analysis for arbitrary dynamical systems. Our key novel idea consists of using random set theory to give a rigorous interpretation of our method, and prove that it returns sets which are guaranteed to converge to the convex hull of the true reachable sets. Additionally, we leverage recent work on robust deep learning and propose a new adversarial sampling approach to robustify our algorithm and accelerate its convergence. We demonstrate that our method is faster and less conservative than prior work, present results for approximate reachability analysis of neural networks and robust trajectory optimization of high-dimensional uncertain nonlinear systems, and discuss future applications.} }
Endnote
%0 Conference Paper %T Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling %A Thomas Lew %A Marco Pavone %B Proceedings of the 2020 Conference on Robot Learning %C Proceedings of Machine Learning Research %D 2021 %E Jens Kober %E Fabio Ramos %E Claire Tomlin %F pmlr-v155-lew21a %I PMLR %P 2055--2070 %U https://proceedings.mlr.press/v155/lew21a.html %V 155 %X Reachability analysis is at the core of many applications, from neural network verification, to safe trajectory planning of uncertain 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 guarantees. In this paper, we propose a simple yet effective sampling-based approach to perform reachability analysis for arbitrary dynamical systems. Our key novel idea consists of using random set theory to give a rigorous interpretation of our method, and prove that it returns sets which are guaranteed to converge to the convex hull of the true reachable sets. Additionally, we leverage recent work on robust deep learning and propose a new adversarial sampling approach to robustify our algorithm and accelerate its convergence. We demonstrate that our method is faster and less conservative than prior work, present results for approximate reachability analysis of neural networks and robust trajectory optimization of high-dimensional uncertain nonlinear systems, and discuss future applications.
APA
Lew, T. & Pavone, M.. (2021). Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling. Proceedings of the 2020 Conference on Robot Learning, in Proceedings of Machine Learning Research 155:2055-2070 Available from https://proceedings.mlr.press/v155/lew21a.html.

Related Material