Fundamental Limits of Sampling-Based Reachability: Geometry and Flow Distortion

Jixian Liu; Ihab Tabbara; Hussein Sibai; Enrique Mallada

eess.SYOct 29, 2026

Fundamental Limits of Sampling-Based Reachability: Geometry and Flow Distortion

Authors: Jixian Liu, Ihab Tabbara, Hussein Sibai, Enrique Mallada

Organizations: Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, MD, USA · Department of Computer Science and Engineering, Washington University in St. Louis, St. Louis, MO, USA

Abstract

Sampling-based reachability estimates reachable sets from finitely many simulated trajectory endpoints. Existing guarantees often control missed probability mass or approximation error relative to the convex hull of the reachable set, leaving the geometric error relative to the reachable set incompletely characterized. We study this error as a problem of support estimation under flow distortion. Our assumptions combine a uniform lower bound on the local volume density of the initial set, a lower bound on the sampling density, and a one-sided Lipschitz constant $μ$ for the vector field. These conditions admit initial sets with corners and dynamics that may expand or contract. In the fine-accuracy regime, $\tilde{\mathcal O}\bigl(2^ne^{nμT}(R/r)^n/(ρκ)\bigr)$ independent endpoint samples suffice for Hausdorff accuracy $r$ using the endpoint cloud. Here, $n$ is the state dimension, $T$ is the horizon, $R$ is the volume-equivalent radius, and $ρ$ and $κ$ quantify sampling density and local volume density. For $n\ge2$ and sufficiently small $κ$ , a minimax lower bound over all estimators based only on independent endpoints matches these dependencies up to a dimension-dependent factor $2\cdot4^n$ and logarithmic factors, within the stated parameter range and when the state domain accommodates the construction. The exponential burden in dimension, and in the horizon for expanding systems, is therefore intrinsic to this observation model. Planar experiments illustrate the predicted effects of corners and contraction; robot-arm experiments show how empirical accuracy deteriorates with dimension.

Figures & tables

Panel of Figure 1 — Fig. 1: Geometry and dynamics. (a) A disk and a nonconvex star of comparable diameter, the latter the union of a circular core of radius $2/3$ of the disk radius and five $15^{\circ}$ corners, propagated under two fields. Left: $\dot{x}=x^{2}$ , $\dot{y}=0$ , which is not globally Lipschitz and blows up in finite time; the right tip of the reachable set escapes as $t\uparrow 1/3$ , and the panel is clipped. Right: the linear field $\dot{x}=2x$ , $\dot{y}=0$ , which is Lipschitz, hence one-sided Lipschitz, and maps the disk to an ellipse. Rows: $t=0$ , $0.16$ , and $0.32$ . Dots: $500$ samples, drawn uniformly by area on each initial set; curves: the exact reachable boundaries. (b) Mean Hausdorff error of the endpoint cloud against $N\in[5\times 10^{1},5\times 10^{3}]$ at $T=0.32$ , and (c) against $T$ at $N=1000$ ; bands: $95\%$ confidence intervals over $50$ trials. Time changes the distortion of neighborhoods, while the geometry of $S_{0}$ changes the local area fraction, and hence the local sampling probability, even at a fixed horizon.

Bound	Range of $\kappa$	Sample complexity
Upper bound	$0<\kappa\leq 1$	$\tilde{\mathcal{O}}\Bigl(\dfrac{1}{\rho\kappa}\Bigl(\dfrac{2e^{\mu T}R}{r}\Bigr)^{n}\Bigr)$
Lower bound	$0<\kappa\leq\kappa_{n}$	$\Omega\Bigl(\dfrac{1}{\rho\kappa}\Bigl(\dfrac{e^{\mu T}R}{2r}\Bigr)^{n}\log\dfrac{1}{2\delta}\Bigr)$

TABLE I: Sample-complexity bounds in the common regime specified above.

Fig. 2: Effect of the corner angle under the spiral sink $F_{-1}$ at $T=1$ . Left: equal-area initial sets. Middle: mean Hausdorff error versus $N$ , with $95\%$ confidence bands and the upper bounds solved for $r$ . Right: mean error and empirical $5$ – $95\%$ ranges at $N=10^{4}$ , together with the upper bound and the minimax lower bound ( 9 ) solved for $r$ at $\delta=0.05$ . The lower curve is a worst-case bound over the admissible family of instances, not a bound on the mean or quantile of the error for each plotted triangle.

Fig. 3: Four vector fields on the equilateral triangle of area $\pi$ . Left: $S_{0}$ , $S_{T}$ at $T=1$ with $250$ endpoints, and the centroid trajectory. Middle: mean Hausdorff error against $T$ at $N=1000$ . Right: error against $N$ at $T=1$ . Bands: 95% confidence intervals. Dashed: the upper bound of Theorem 1 and Corollary 1 solved for $r$ , with $e^{\mu T}$ for the linear fields and a Lipschitz bound for $\varphi_{T}$ on $S_{0}$ for the cubic field. Dotted: the growth $e^{LT}$ that a two-sided Lipschitz bound predicts for the spiral sink.

Field	$\mu$	$L$	rate	ratio	$e^{2\mu}$	$e^{2L}$
$F_{0.5}$	$0.5$	$4.03$	$0.50$	$2.74$	$2.72$	$3.2\times 10^{3}$
$F_{0}$	$0$	$4.00$	$0.00$	$1.00$	$1$	$3.0\times 10^{3}$
$F_{-1}$	$-1$	$4.12$	$-1.00$	$0.134$	$0.135$	$3.8\times 10^{3}$
cubic	$0$	$35.4$	—	$0.256$	$1$	$5.8\times 10^{30}$

TABLE II: Horizon dependence of the Hausdorff error under four planar vector fields.

Fig. 4: Sample complexity against the horizon under the spiral sink $F_{-1}$ . Left: the two initial sets to scale; the dashed arcs have radius $re^{-\mu T}$ , $r=0.03$ , around a point of a corner piece. Right: samples needed for $d_{H}(S_{T},\widehat{S}_{N})\leq r$ in $95\%$ of $200$ trials, on a grid of step $0.005$ in $T$ (solid steps) and at the horizons $T\in\{0,0.25,\dots\}$ (markers); the upper bound (dashed); and the minimax lower bound ( 9 ) (dash-dotted), drawn only where it applies, $r<e^{\mu T}R/16$ , that is, $T<0.73$ . Vertical lines mark the horizons where the preimage scale reaches $\lambda$ and where the one-sample bound begins.

Fig. 5: Robot arm with $n/2$ links at $T=1$ . Left, middle: mean directed Hausdorff error of the convex hull of the endpoints against $N$ under uniform and adversarial sampling (bands: 95% intervals over $30$ seeds; dashed: fitted power laws). Right: inverse rate $1/|\mathrm{slope}|$ against $n$ with its linear fit and the bootstrap intervals of Table III ; dotted: the worst-case exponent $n$ .

$n$	Uniform	Adversarial
$4$	$-0.333$	$-0.422$
	$[-0.342,-0.324]$	$[-0.438,-0.405]$
$6$	$-0.253$	$-0.287$
	$[-0.260,-0.247]$	$[-0.294,-0.279]$
$8$	$-0.216$	$-0.234$
	$[-0.223,-0.211]$	$[-0.240,-0.227]$

TABLE III: Fitted convergence slopes and

95\%

confidence intervals for the robot-arm experiments.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 9 — Fig. 6: Lemma 1 : $\varphi_{T}$ maps $\mathcal{B}_{s}(x)\cap S_{0}$ (shaded, left), $s=e^{-\mu T}r$ , into $\mathcal{B}_{r}(y)\cap S_{T}$ (right), $y=\varphi_{T}(x)$ . Dashed: the boundary of $\mathcal{B}_{s}(x)$ and its image; thin: $\mathcal{B}_{r}(y)$ .

Panel of Figure 10 — Fig. 7: Lemma 2 . Left: a maximal $\beta$ -separated set $\{z_{j}\}$ in $S_{0}$ ; the disjoint shaded sets $\mathcal{B}_{\beta/2}(z_{j})\cap S_{0}$ bound $M$ , and the dashed balls $\mathcal{B}_{\beta}(z_{j})$ cover $S_{0}$ . Right: the images $\varphi_{T}(z_{j})$ form an $r$ -cover of $S_{T}$ , $r=e^{\mu T}\beta$ ; dashed: the image of $\mathcal{B}_{\beta}(z_{j})$ ; thin: the balls of radius $r$ .

Panel of Figure 11 — Fig. 8: Theorem 1 : the centers $z_{j}$ (crosses) of an $\frac{r}{2}$ -net of $S_{T}$ with their balls, and the endpoint samples (dots). When every net ball contains a sample, $d(x,\widehat{S}_{N})\leq\|x-z_{j}\|+\|z_{j}-Y_{i}\|\leq r$ for every $x\in S_{T}$ .

Panel of Figure 12 — Fig. 9: Hard instances of Theorem 2 for thin tips (left) and wide tips (right). $S^{(0)}$ keeps the tip at $q_{0}$ and cuts off the tip at $q_{1}$ by $\mathring{\mathcal{B}}_{\varsigma}(q_{1})$ (dashed); $S^{(1)}$ does the reverse. The instances differ on the sectors $W_{0}$ (shaded) and $W_{1}$ (hatched).

Reachability Analysis

Reachability analysis determines which states a system can enter from given initial conditions, actions, and disturbances.

See all 80 papers

Jul 21, 2026

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

Reachability analysis is central to safety-critical control, robotics, and neural network verification, but classical computational methods, such as Hamilton--Jacobi reachability and set propagation, scale poorly with state dimension. Sampling-based methods have emerged as a promising alternative, often providing finite-sample guarantees that bound the probability-mass left uncovered. However, an explicit account of how the geometry of the initial set, the dynamics, and the sampling law affect the accuracy of the estimator is not fully available in the literature. We study this by casting sampling-based reachable-set recovery as geometric support estimation over a family of problems specified by an initial set, its dynamics, and a sampling law. First, we identify two regularity properties, positive reach of the initial set's complement and Lipschitz continuity of the dynamics, that together make recovery well-posed: a probability-mass coverage guarantee can be upgraded to accuracy

r

in Hausdorff distance. Second, we bound the resulting sample complexity: recovery is achievable with

\tilde{\mathcal{O}}\big((e^{3LT}/r)^n\big)

samples, exponential in both the state dimension and the time horizon. Third, we show that neither can be removed: an minimax lower bound of

Ω\big((e^{LT}/r)^n\big)

holds for every estimator, so the exponential dependence on dimension and the degradation over the horizon are both intrinsic, not artifacts of a particular method. Experiments on nonlinear systems confirm that adversarial sampling improves constants but not the scaling.

Jixian Liu, Ihab Tabbara, Hussein Sibai +1

Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Computer Science, Washington University in St. Louis

Reachability Analysis Sample Complexity

Ask PDF

Apr 14, 2026

Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees

We study finite horizon reachable set estimation for unknown discrete-time dynamical systems using only sampled state trajectories. Rather than treating scenario optimization as a black-box tool, we show how it can be tailored to reachable set estimation, where one must learn a family of sets based on whole trajectories, while preserving probabilistic guarantees on future trajectory inclusion for the entire horizon. To this end, we formulate a relaxed scenario program with slack variables that yields a tunable trade-off between reachable set size and out-of-sample trajectory inclusion over the horizon, thereby reducing sensitivity to outliers. Leveraging the recent results in adversarially robust scenario optimization, we then extend this formulation to account for bounded adversarial perturbations of the observed trajectories and derive a posteriori probabilistic guarantees on future trajectory inclusion. When probability distribution shifts in the Wasserstein distance occur, we obtain an explicit bound on how gracefully the theoretical probabilistic guarantees degrade. For different geometries, i.e.,

p

-norm balls, ellipsoids, and zonotopes, we derive tractable convex reformulations and corroborate our theoretical results in simulation.

Georgios Pantazis, Michelle S. Chong

Dynamics and Control (D&C) section at the Department of Mechanical Engineering, Eindhoven University of Technology, the Netherlands.

Distribution Shift Robustness

Ask PDF

Sep 8, 2026

Online, Reachability-Aware, Sampling-Based Motion Planning

Sampling-Based Model-Predictive Control (MPC) algorithms are a flexible class of controllers used for navigation on a wide range of robotic systems. Historically, such approaches have lacked hard safety guarantees, a shortcoming which we remedy in this work by computing guaranteed reachable-set overapproximations online with a fast, interval-based pipeline. We show that our method achieves similar performance to a state-of-the-art reachability-based planner without the need for the expensive pre-computation step, and can be scaled to systems that are infeasible using existing approaches. Finally, we demonstrate that our technique reduces safety violations by over 99% in a racing simulation and successfully controls a model racecar on real hardware experiments without crashes.

Brendan Gould, Zhiyuan Zhang, Panagiotis Tsiotras +1

Robotic Control Reachability Analysis Robot Safety Model Predictive Control Safe Motion Planning Sampling-Based Motion Planning

Ask PDF

Abstract

Reachability Analysis

Explore similar work

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees

Online, Reachability-Aware, Sampling-Based Motion Planning