← News
Tech for Good Tech for Good Frontiers

Why a million simulations can still miss the dangerous edge

Why a million simulations can still miss the dangerous edge
Reachable-Set Boundaries Study focus
Sampling Limits Are Intrinsic Main finding
Planar Shapes And Robot Arms Experiments

A set of simulated trajectories can look dense and still fail to reveal the edge of the states a system can reach. That is not just a plotting problem: for safety checks, an omitted sliver may contain the very state that violates a constraint. Liu, Tabbara, Sibai and Mallada show that the number of endpoint simulations needed to rule out such misses can grow exponentially with the system’s dimension—and that, under their assumptions, this is not merely a weakness of today’s algorithms. It is a limit of what independent endpoint samples can tell us.

The result also identifies when the burden gets worse. Sharp corners in the starting region make nearby states harder to sample; expanding dynamics stretch those gaps over time. Contracting dynamics do the opposite. In the paper’s fine-accuracy regime, the endpoint cloud needs on the order of

samples to cover the reachable set to Hausdorff accuracy , subject to logarithmic factors. Here, is state dimension, is the time horizon, represents the initial set’s volume scale, and and describe how much sampling probability and local volume are guaranteed near every point. The Hausdorff distance is a strict geometric test: every point in either set must lie within the stated distance of the other.

That formula is not a forecast of how many runs every real robot or controller needs. It is a worst-case guarantee for a specific information setup: draw independent initial conditions, simulate them, and estimate the reachable set from their endpoints. Its practical message is nonetheless sharp. Probability coverage alone can hide a distant, low-probability region, while convex-hull estimates can fill in holes that are not reachable. A reliable geometric certificate has to confront both omissions and overestimation.

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∘ corners, propagated under two fields. Left: x˙=x2, y˙=0, which is not globally Lipschitz and blows up in finite time; the right tip of the reachable set escapes as t↑1/3, and the panel is clipped. Right: the linear field x˙=2x, 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∈[5×101,5×103] 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 S0 changes the local area fraction, and hence the local sampling probability, even at a fixed horizon.
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∘ corners, propagated under two fields. Left: x˙=x2, y˙=0, which is not globally Lipschitz and blows up in finite time; the right tip of the reachable set escapes as t↑1/3, and the panel is clipped. Right: the linear field x˙=2x, 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∈[5×101,5×103] 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 S0 changes the local area fraction, and hence the local sampling probability, even at a fixed horizon. Source: Jixian Liu, Ihab Tabbara

The Science

Reachability asks a basic safety question: starting from any state in a specified set, where might a system end up after a given amount of time? The answer is the reachable set. If a robot arm might begin anywhere in a range of joint positions, for example, its reachable set collects the configurations it can occupy after the dynamics act for a chosen horizon. Engineers use such sets to check whether a system can enter a forbidden region.

Exact reachability tools can be powerful, but methods based on Hamilton–Jacobi equations or direct set propagation often become expensive as the number of state variables rises. Sampling offers a tempting alternative. Draw initial states, simulate their paths, and use the final points as a picture of what is reachable. Such endpoint methods are parallelizable and can work with complicated dynamics, including learned models. The unresolved question is what their picture guarantees about the actual boundary.

The authors study autonomous continuous-time systems, written as , and estimate the set reached at time from independent endpoint samples. They focus on Hausdorff error rather than merely the share of probability mass missed. A low-mass corner can be far from every sampled point; a missed-mass bound may still look good even when that corner matters to safety.

Two assumptions let them turn sample probabilities into geometric statements. First, the initial region must have enough local volume: every sufficiently small ball centered on the set contains at least a fixed fraction of a full ball’s volume. This condition, called standardness, allows corners but rules out pathologically thin cusps at the scales covered by the guarantee. Convex polytopes qualify; their sharpest vertex angles can make small.

Second, the vector field obeys a one-sided Lipschitz bound. In everyday terms, this bounds how quickly two nearby trajectories can separate, without requiring every aspect of the dynamics to be globally smooth or equally expansive. Its constant can be negative: negative values capture contraction, while positive values allow expansion. Finally, the initial sampling distribution cannot starve any region of the set; is a lower bound on its density relative to uniform sampling.

The argument follows a neighborhood backward through the flow. If two trajectories begin close, the one-sided bound limits how far apart their endpoints can be. Thus, a ball around a reachable point must contain the images of a sufficiently small ball around its starting point. Standardness and the sampling-density floor then guarantee a minimum probability of drawing an initial state from that preimage. Cover the reachable set with enough such neighborhoods, and a union-bound argument gives a probability that all parts have been sampled closely enough.

This establishes inner coverage for any estimator that includes every observed endpoint. A full Hausdorff guarantee needs one more condition: the estimator must not add points arbitrarily far outside the true reachable set. That distinction is important. The theorem does not say that every endpoint-cloud construction automatically gives a two-sided certificate; it spells out what is needed for one.

What They Found

In the fine-accuracy regime, the upper bound’s main burden scales like . Halving the desired geometric error therefore has a steep cost, especially in high dimensions. The factor makes the role of dynamics explicit: for expanding systems, a longer horizon raises the sample requirement exponentially in the product of dimension, expansion rate and time. When , the factor decreases with the horizon, reflecting that contraction makes the set easier to cover.

The initial geometry matters through . The paper’s motivating planar example compares a smooth disk boundary with a star-shaped set whose tips have corners. At a sufficiently small ball centered at a star tip, just of the ball lies inside the set; at a smooth disk boundary, the limiting fraction is . With uniform sampling, the corner neighborhood is consequently much less likely to receive a sample. The paper’s experiments show larger endpoint-cloud Hausdorff errors for the star than for the disk across tested sample sizes, and a slower decline in error for the star under the quadratic flow.

A sharp tip offers less area to sample

Local fraction of a sufficiently small ball inside the initial set, as reported for the star tip and smooth disk boundary.

A sharp tip offers less area to sample
LabelValue
15° star tip4.1667 percent
Smooth disk boundary50 percent

The second central result is a minimax lower bound. For dimension at least two, sufficiently small local-volume parameter, and the stated range of scales and domains, every estimator using only independent endpoints faces a worst-case sample burden with the same dependence on dimension, accuracy, flow expansion, initial scale, sampling density and geometry as the upper bound—up to dimension-dependent constants and logarithmic factors. Put plainly, a cleverer estimator cannot generally erase the exponential dependence while keeping the same endpoint-only information. The gap between the bounds includes a dimension-dependent factor reported as , as well as logarithmic terms.

That does not mean all practical cases are equally hard. The lower bound is a worst-case statement over a family of admissible problems, not a prediction of the average error for a particular robot. Nor does it rule out using more information: structure in the dynamics, adaptive sampling, analytic models or richer observations may help. It says that independent endpoint samples alone cannot promise a uniformly better scaling across the covered class.

The experiments make the distinctions tangible. In planar examples, the authors compare a spiral sink, linear fields and a cubic field that is not globally Lipschitz but meets the relevant one-sided condition. The spiral sink’s contraction produces a different horizon trend from a two-sided Lipschitz estimate, which treats contraction as if it could expand distances just as badly. In another example, the field stretches the reachable set dramatically as time approaches its finite blow-up point; the plotted region is clipped near that limit. These examples illustrate why the flow’s actual distortion, not just a generic smoothness label, matters.

Fig. 3: Four vector fields on the equilateral triangle of area π. Left: S0, ST 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μT for the linear fields and a Lipschitz bound for φT on S0 for the cubic field. Dotted: the growth eLT that a two-sided Lipschitz bound predicts for the spiral sink.
Fig. 3: Four vector fields on the equilateral triangle of area π. Left: S0, ST 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μT for the linear fields and a Lipschitz bound for φT on S0 for the cubic field. Dotted: the growth eLT that a two-sided Lipschitz bound predicts for the spiral sink. Source: Jixian Liu, Ihab Tabbara

A robot-arm experiment then tests how accuracy behaves as dimension rises. The paper reports that empirical convergence deteriorates with dimension, consistent with the theorem’s warning, and that adversarial sampling improves accuracy at larger budgets. The supplied paper text does not give the plotted numerical slopes, so the figure supports a qualitative comparison rather than a precise empirical rate here. The theoretical dimension factor , shown below with other quantities held fixed, is only one component of the full upper-bound expression—not a measured sample count.

The dimension factor grows exponentially

The upper-bound prefactor includes 2^n. Values below evaluate that exact theoretical factor by dimension; all other quantities are held out of this display.

The dimension factor grows exponentially
LabelValue
12
24
38
416
532

Why This Changes Things

The practical shift is from asking “Did we see most of the probability mass?” to “How far could the part we did not see be?” Those questions can have very different answers. Rare states can be operationally decisive: a low-probability collision configuration, a narrow path into an unsafe region, or a corner of a feasible set may be exactly what a safety certificate must account for.

The results are also a guide to where sampling effort should go. A low signals thin local neighborhoods or sharp corners; a low signals a sampling law that undersamples some part of the initial set; positive signals expansion. These are not abstract nuisances. They identify the mechanisms that can leave a reachable boundary unseen. Reporting only the number of trajectories, without describing initial geometry, sampling distribution and flow distortion, can make two very different coverage claims look comparable.

For control and robotics, the implication is not “sampling is useless.” It is that empirical coverage and worst-case certification are different products. Sampling can rapidly reveal likely behavior and guide engineering decisions. But if a claim must hold for every state in a region, a cloud of plausible endpoints needs either a theorem-backed coverage argument, a sound outer approximation, or additional structural information. Convex hulls can be useful, but they can also bridge unreachable gaps; endpoint clouds can preserve geometry, but can miss low-probability tips.

The paper’s one-sided Lipschitz perspective matters beyond a tighter constant. Conventional Lipschitz bounds treat the largest possible separation rate as a uniform property. A one-sided bound can encode net contraction even when the vector field is not globally Lipschitz. That gives theory a way to distinguish a system that compresses uncertainty from one that amplifies it—an important distinction when trajectories are propagated for long periods.

The lower bound is the sobering counterweight to optimism about improved algorithms. If independent endpoints are the only observations and the system class is broad, exponential dependence on dimension is intrinsic in the worst case. It points toward complementary strategies: exploit model structure, sample adaptively near poorly covered boundaries, obtain intermediate trajectory information, or combine simulation with deterministic enclosures. The paper does not prove those alternatives will solve the problem, but it clarifies why they may be necessary.

What’s Next

Several boundaries of the result are worth keeping visible. The geometric regularity condition guarantees a uniform local-volume floor. It includes many practical shapes, including polytopes, but excludes outward cusps at the scales where the stated rate applies. The authors note that such shapes may still be consistently recoverable, just not necessarily at this uniform rate. Likewise, the minimax construction applies only in its stated parameter range and when the state domain is large enough to contain it.

The full Hausdorff guarantee also depends on how the estimator controls its outer edge. The endpoint cloud itself is contained in the reachable set, but other estimators—especially smoothed or inflated ones—need a separate guarantee that they do not stray too far. The paper’s core sample bound is therefore a powerful coverage result, not a universal certificate for every set-reconstruction pipeline.

The next step for the field is to connect these limits to methods that use more than passive, independent endpoints. Adaptive strategies could direct simulations toward corners or regions with weak empirical coverage. Dynamics-aware methods could use contraction, invariants or known constraints to tighten the reachable set without brute-force sampling. A useful benchmark would compare their guarantees—not only their average errors—on systems with controlled geometry and dimension.

For anyone building safer robots or verifying learned controllers, the lasting contribution is a more honest map of the terrain. The difficult cases are not merely where simulations are scarce; they are where geometry makes probability thin and dynamics stretch that thinness into a large blind spot. Knowing when the blind spot is unavoidable is a first step toward designing methods that can see around it.