💻 computer science

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

This paper establishes that sampling-based reachability analysis for high-dimensional nonlinear systems is fundamentally limited by an exponential dependence on both state dimension and time horizon, proving that neither the geometry of the initial set nor the sampling strategy can overcome this intrinsic sample complexity barrier.

Original authors: Jixian Liu, Ihab Tabbara, Hussein Sibai, Enrique Mallada

Published 2026-07-22

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Jixian Liu, Ihab Tabbara, Hussein Sibai, Enrique Mallada

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to draw a map of a mysterious, shifting island. You can't see the whole thing at once, so you send out a fleet of tiny, fast boats to explore. Each boat starts from a specific spot on the shore and follows the currents for a set amount of time. When they stop, you mark their final positions on your map. The goal? To connect the dots and draw a perfect outline of the entire island that the boats could have reached. This is the heart of reachability analysis, a super-important tool in robotics and self-driving cars. It answers the question: "If I start here, where could I possibly end up?" If a robot thinks it can't crash into a wall, but its map is wrong and it can reach the wall, that's a disaster.

For a long time, scientists tried to draw these maps using complex math equations that worked like a rigid grid. But as the world gets more complicated—like when a robot has many moving joints or a self-driving car has to think about traffic, weather, and pedestrians—this grid method becomes too slow and heavy to use. So, engineers switched to the "boat fleet" method: just sample a bunch of starting points, run them through the simulation, and see where they land. It's fast, flexible, and works on almost any system. But there's a catch: if you only send out a few boats, you might miss a tiny, dangerous cove hidden behind a cliff. The old math could say, "Hey, we covered 99% of the water!" while completely missing that one tiny, deadly cove. The big question for scientists was: How many boats do we actually need to guarantee we haven't missed any part of the island, no matter how weird the shape or how strong the currents?

This paper, written by researchers from Johns Hopkins University and Washington University in St. Louis, dives deep into that exact problem. They treat the reachable set (the island) not just as a collection of points, but as a geometric shape that gets stretched and twisted by the "currents" of the system's dynamics. They discovered that to get a truly accurate map, you need to know two things about your starting point and your currents: the starting area must be "nice" (no infinitely thin, needle-like spikes), and the currents must be predictable (they can't stretch things apart too violently too fast).

The authors found that if these conditions are met, you can turn a simple "we covered most of the area" guarantee into a strict "we are within a tiny distance of every single edge" guarantee. However, they also proved a somewhat sobering truth: the number of samples (boats) you need grows explosively as the system gets more complex. Specifically, the number of samples required depends on the dimension of the system (how many moving parts it has) and the time you are looking at, in a way that is mathematically unavoidable. They showed that no clever trick or smarter sampling method can escape this "curse of dimensionality."

To test this, they ran experiments on a simple 2D system and a complex robot arm with multiple joints. They compared "uniform sampling" (sending boats out randomly) with "adversarial sampling" (a smarter method that tries to hunt for the tricky, hard-to-reach spots). The results were clear: the smarter method did a better job and reduced the error, but it couldn't change the fundamental rule. As the robot arm got more complex (more joints), the number of samples needed to keep the error low still skyrocketed. The paper concludes that while we can make our maps better with smarter sampling, we cannot cheat the math: in high-dimensional, complex worlds, getting a perfect safety guarantee is incredibly expensive in terms of the data we need to collect.

The Core Findings

The paper tackles the problem of sampling-based reachability. In simple terms, this is about figuring out all the possible places a system (like a robot or a car) can end up after a certain time, given a set of starting positions. Instead of solving impossible equations, we simulate many starting points and see where they land.

The Main Discovery:
The authors proved that you can turn a "probability" guarantee (e.g., "we missed less than 1% of the area") into a strict "geometric" guarantee (e.g., "we are within 1 millimeter of every edge") only if two specific conditions are met:

The Starting Shape is "Healthy": The initial set of starting points must have a property called "positive reach." In plain English, this means the shape can't have infinitely thin spikes or sharp inward cusps. It needs to be "thick" enough everywhere.
The Currents are Predictable: The system's movement (dynamics) must be "Lipschitz continuous." This is a fancy way of saying the system doesn't stretch or tear things apart too violently. If a tiny change in the starting point leads to a massive, unpredictable jump in the ending point, the math breaks.

If these conditions hold, the paper provides a formula for how many samples ( $N$ ) you need. The formula shows that the number of samples grows exponentially with the number of dimensions (how complex the system is) and the time horizon.

What They Ruled Out:
The paper explicitly argues against the idea that we can easily "fix" the sampling problem just by being smarter about where we sample.

No Magic Bullet: They proved a "minimax lower bound," which is a mathematical proof that no estimator (no matter how smart) can avoid the exponential growth in sample complexity.
Adversarial Sampling Limits: In their experiments, they used an "adversarial" sampling method (trying to target the hardest-to-reach spots). While this improved the results (made the map more accurate for the same number of samples), it did not change the fundamental scaling law. The error still got worse as the system got more complex, just at a slightly better rate. The "curse of dimensionality" is intrinsic, not an artifact of a bad method.

How Sure Are They?
The authors are very confident in their theoretical results because they proved them mathematically. They derived both an upper bound (a formula showing it is possible with enough samples) and a lower bound (a proof that it is impossible to do with fewer samples). These two bounds meet, meaning they have found the exact limit of what is possible.

For the practical side, they simulated these ideas on:

A 2D system with non-linear dynamics (where the math gets tricky).
A robot arm with 2, 3, and 4 links (simulating higher dimensions).

The simulations confirmed their theory: the error decreased as they added more samples, but the rate of improvement slowed down drastically as the robot arm got more complex. The "adversarial" method helped, but it couldn't break the exponential wall.

The Story in Analogy

Imagine you are trying to paint a giant, invisible wall that is constantly stretching and twisting. You have a bucket of paint and a spray gun. You can't see the wall, so you have to guess where to spray.

The Old Way (Probability): You spray 1,000 random dots. You check and say, "I covered 99% of the wall's surface area!" But wait—what if the wall has a tiny, hair-thin crack that you missed? If a robot tries to walk through that crack, it falls off the edge. The "99% coverage" didn't save you.

The New Way (Geometry): You want to guarantee that every single point on the wall is within a hair's breadth of a paint dot. The paper says: "Okay, we can do that, but only if the wall isn't made of infinitely thin threads (positive reach) and the stretching isn't too crazy (Lipschitz)."

The Catch (The Curse): The paper proves that if your wall is in a 10-dimensional space (like a robot with 10 joints), you don't just need 10 times more paint. You need $10^{10}$ times more paint. It's an explosion.

The "Smart" Spray Gun (Adversarial Sampling): You try to use a smart gun that aims specifically at the cracks and the stretching parts. The paper shows that this smart gun is great! It paints the cracks better than a random gun. However, it cannot stop the explosion. If you double the complexity of the wall, you still need a massive, exponential amount of extra paint. The smart gun just makes the "massive" number a little less massive, but it doesn't make it small.

Why This Matters

This research is a reality check for the field of robotics and AI safety. It tells us that while sampling methods are powerful and necessary for complex systems, we cannot simply "sample our way out" of safety guarantees. If we want to certify that a 100-joint robot won't crash, we need to accept that the amount of data required is enormous.

The paper suggests that instead of just throwing more samples at the problem, future work might need to use "physics-informed" tricks—using our knowledge of how the world works (like energy conservation) to cheat the math a little bit. But for now, the paper establishes the hard limits: geometry and dynamics dictate the cost of safety, and that cost is high.

Technical Summary: On the Limits of Sampling-Based Reachability

Problem Formulation

The paper addresses the fundamental challenge of sampling-based reachability analysis for autonomous continuous-time dynamical systems $\dot{x} = F(x)$ . While classical methods like Hamilton–Jacobi reachability provide strong deterministic guarantees, they suffer from poor scalability with state dimension. Sampling-based methods, which propagate finite sets of initial states through the dynamics to approximate the reachable set $S_T = R_T(S_0)$ , offer a scalable alternative but typically provide only probability-mass coverage guarantees.

The core problem identified is that bounding the probability mass of the missed region (i.e., $P_T(S_T \setminus \hat{S}_N) \le \epsilon$ ) does not imply geometric accuracy in the Hausdorff distance. An estimator may miss a thin, spatially separated region or a low-density "cusp" with negligible probability mass while incurring a large Hausdorff error. This geometric inaccuracy is critical for safety-critical applications. The paper seeks to characterize the sample complexity required to convert probability-mass guarantees into Hausdorff-distance guarantees, specifically analyzing how the geometry of the initial set, the dynamics, and the sampling law influence this recovery.

Methodology

The authors frame reachable-set recovery as a geometric support estimation problem under flow distortion. They define a problem family $\mathcal{F}_{R,L,r_0,\rho}$ characterized by four parameters:

Scale ( $R$ ): The volume-equivalent radius of the initial set $S_0$ .
Regularity ( $r_0$ ): The positive reach of the complement of the initial set ( $\text{reach}(S_0^c) \ge r_0$ ), which excludes inward cusps and thin degeneracies.
Dynamics ( $L$ ): The Lipschitz constant of the vector field $F$ .
Sampling Density ( $\rho$ ): A lower bound on the initial sampling density relative to the set volume.

The methodology proceeds in three logical steps:

Local Mass Bounds: The authors derive a lower bound on the probability mass of local neighborhoods in the reachable set. They show that the positive reach of $S_0^c$ ensures local volume thickness, which, when propagated through the Lipschitz flow, guarantees that any $r$ -neighborhood in $S_T$ contains a non-negligible amount of probability mass.
Upper Bound (Achievability): Using the derived local mass bounds, they apply a random covering argument to establish a sufficient sample size $N$ for an estimator (containing all endpoints) to achieve $r$ -accurate inner coverage.
Lower Bound (Impossibility): They prove a minimax lower bound, demonstrating that for any estimator, there exists an instance within the problem family where a specific number of samples is strictly necessary to achieve a given accuracy. This establishes that the derived scaling is intrinsic to the problem, not an artifact of a specific algorithm.

Key Contributions

Well-Posedness Conditions: The paper identifies that positive reach of the initial set's complement and Lipschitz continuity of the dynamics are sufficient conditions to upgrade probability-mass coverage to Hausdorff-accurate recovery.
Sample Complexity Upper Bound: The authors prove that $\tilde{O}((e^3 L T R / r)^n)$ endpoint samples are sufficient for $r$ -accurate inner coverage. This bound is exponential in both the state dimension $n$ and the time horizon $T$ .
Minimax Lower Bound: They establish a lower bound of $\tilde{\Omega}((e^{LT} R / r)^n)$ , proving that the exponential dependence on dimension and the degradation over the time horizon are intrinsic to the problem. No estimator can circumvent this scaling in the worst case.
Empirical Validation: Experiments on a 2D non-Lipschitz system and a multi-link MuJoCo robot arm confirm that while adversarial sampling improves the constants (finite-sample efficiency), it does not alter the fundamental dimension-dependent scaling predicted by the theory.

Results

Theoretical Scaling: The sample complexity scales as $N \propto (C \cdot e^{LT} \cdot R / r)^n$ . The term $e^{LT}$ reflects the expansion of the flow map over time, while $(R/r)^n$ reflects the geometric covering number of the set.
Geometry vs. Probability: The results demonstrate that geometric regularity (positive reach) is essential. Without it, small probability masses can correspond to large geometric gaps, making Hausdorff recovery impossible with finite samples.
Adversarial Sampling: In experiments, adversarial sampling (directing samples toward geometrically informative regions) reduced the Hausdorff error compared to uniform sampling. However, the log-log slopes of error versus sample size flattened as dimension increased, confirming that targeted sampling improves constants but cannot eliminate the "curse of dimensionality" inherent in the $r^{-n}$ scaling.
Non-Lipschitz Dynamics: The study highlights that for non-Lipschitz systems (e.g., $\dot{x} = x^2$ ), the flow expansion can be super-exponential, leading to rapid growth in Hausdorff error, further emphasizing the role of the flow factor $e^{LT}$ (or its generalization).

Significance and Claims

The paper claims to provide the first explicit characterization of how the geometry of the initial set, the dynamics, and the sampling law jointly determine the accuracy of sampling-based reachability estimators in Hausdorff distance.

Theoretical Limit: The primary significance is the proof that the exponential dependence on dimension and time horizon is unavoidable. This sets a fundamental limit on what sampling-based methods can achieve, regardless of the estimator design.
Bridging Gap: It bridges the gap between probabilistic guarantees (common in learning-based control) and geometric guarantees (required for safety certification), showing that the transition requires specific regularity assumptions (positive reach) and incurs a specific sample cost.
Practical Implication: While the theory proves the curse of dimensionality is intrinsic, the experiments suggest that adversarial sampling remains a valuable practical tool for improving finite-sample performance by optimizing the constants, even if it cannot change the asymptotic scaling.

The authors explicitly state that their analysis is restricted to autonomous systems (including closed-loop systems) and does not directly apply to open-loop reachable sets involving unions over control classes, where injectivity and volume-distortion arguments differ.