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

arXiv: https://arxiv.org/abs/2008.10180 · HTML: https://mlsanity.com/paper/2008.10180/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Aug 2020.

## Built on by (most cited first, 11 of 11)

- [Data-Driven Reachability Analysis from Noisy Data](https://mlsanity.com/paper/2105.07229/) (2021)
- [A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis](https://mlsanity.com/paper/2112.05745/) (2021)
- [Learning Density Distribution of Reachable States for Autonomous Systems](https://mlsanity.com/paper/2109.06728/) (2021)
- [Finite-Sample-Based Reachability for Safe Control with Gaussian Process Dynamics](https://mlsanity.com/paper/2505.07594/) (2025)
- [Data-Driven Abstractions via Binary-Tree Gaussian Processes for Formal Verification](https://mlsanity.com/paper/2407.21029/) (2024)
- [LUCID: Learning-Enabled Uncertainty-Aware Certification of Stochastic Dynamical Systems](https://mlsanity.com/paper/2512.11750/) (2025)
- [Case Studies for Computing Density of Reachable States for Safe Autonomous Motion Planning](https://mlsanity.com/paper/2209.08073/) (2022)
- [Shallow Representation is Deep: Learning Uncertainty-aware and Worst-case Random Feature Dynamics](https://mlsanity.com/paper/2106.13066/) (2021)
- [Learned Risk Metric Maps for Kinodynamic Systems](https://mlsanity.com/paper/2302.14803/) (2023)
- [Convex Hulls of Reachable Sets](https://mlsanity.com/paper/2303.17674/) (2023)
- [Feasibility-Aware Pessimistic Estimation: Toward Long-Horizon Safety in Offline RL](https://mlsanity.com/paper/2505.08179/) (2025)

## Abstract (arXiv)

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.