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

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 52 references that are in the map.
- First posted on arXiv 10 Dec 2021.

## Builds on (most cited first, 19 of 19)

- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Verisig: verifying safety properties of hybrid systems with neural network controllers](https://mlsanity.com/paper/1811.01828/) (2018)
- [A Statistical Approach to Assessing Neural Network Robustness](https://mlsanity.com/paper/1811.07209/) (2018)
- [Reach-SDP: Reachability Analysis of Closed-Loop Systems with Neural Network Controllers via Semidefinite Programming](https://mlsanity.com/paper/2004.07876/) (2020)
- [Reachability Analysis of Neural Feedback Loops](https://mlsanity.com/paper/2108.04140/) (2021)
- [Reachable Polyhedral Marching (RPM): A Safety Verification Algorithm for Robotic Systems with Deep Neural Network Components](https://mlsanity.com/paper/2011.11609/) (2020)
- [Neural Bridge Sampling for Evaluating Safety-Critical Autonomous Systems](https://mlsanity.com/paper/2008.10581/) (2020)
- [Reachability-based Trajectory Safeguard (RTS): A Safe and Fast Reinforcement Learning Safety Layer for Continuous Control](https://mlsanity.com/paper/2011.08421/) (2020)
- [Safe Active Dynamics Learning and Control: A Sequential Exploration-Exploitation Framework](https://mlsanity.com/paper/2008.11700/) (2020)
- [GoTube: Scalable Stochastic Verification of Continuous-Depth Models](https://mlsanity.com/paper/2107.08467/) (2021)
- [Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling](https://mlsanity.com/paper/2008.10180/) (2020)
- [Learning Approximate Forward Reachable Sets Using Separating Kernels](https://mlsanity.com/paper/2011.09678/) (2020)
- [A fully data-driven method for estimating the shape of a point cloud](https://mlsanity.com/paper/1404.7397/) (2014)
- [Extent of occurrence reconstruction using a new data-driven support estimator](https://mlsanity.com/paper/1907.08627/) (2019)

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

- [Iterative Reachability Estimation for Safe Reinforcement Learning](https://mlsanity.com/paper/2309.13528/) (2023)
- [Distributionally Robust Statistical Verification with Imprecise Neural Networks](https://mlsanity.com/paper/2308.14815/) (2023)
- [Bridging Dimensions: Confident Reachability for High-Dimensional Controllers](https://mlsanity.com/paper/2311.04843/) (2023)
- [Finite-Sample-Based Reachability for Safe Control with Gaussian Process Dynamics](https://mlsanity.com/paper/2505.07594/) (2025)
- [Formal Safety Verification and Refinement for Generative Motion Planners via Certified Local Stabilization](https://mlsanity.com/paper/2509.19688/) (2025)
- [Verification of Unknown Dynamical Systems via Autoencoder Latent Space](https://mlsanity.com/paper/2512.13593/) (2025)
- [Scalable Data-Driven Reachability Analysis and Control via Koopman Operators with Conformal Coverage Guarantees](https://mlsanity.com/paper/2601.01076/) (2026)
- [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)
- [Verified Compositional Neuro-Symbolic Control for Stochastic Systems with Temporal Logic Tasks](https://mlsanity.com/paper/2311.10863/) (2023)
- [Symplectic Inductive Bias for Data-Driven Target Reachability in Hamiltonian Systems](https://mlsanity.com/paper/2604.17213/) (2026)
- [Sampling-Based Safe Reinforcement Learning](https://mlsanity.com/paper/2605.19469/) (2026)

## Abstract (arXiv)

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 ε-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 ε-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.