betaFeedback

WorksEngineering

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

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, O~(2nenμT(R/r)n/(ρκ))\tilde{\mathcal O}\bigl(2^ne^{nμT}(R/r)^n/(ρκ)\bigr) independent endpoint samples suffice for Hausdorff accuracy rr using the endpoint cloud. Here, nn is the state dimension, TT is the horizon, RR is the volume-equivalent radius, and ρρ and κκ quantify sampling density and local volume density. For n≥2n\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⋅4n2\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.

Paper details

vlnc:W_9bk7w5ta
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Not recorded for this paper

View statement
Looking for related papers…