Introduction
In fields such as robotics and control engineering, determining the "reachable set" of a system is a fundamental challenge. For a drone or spacecraft, the reachable set represents all possible future states given uncertain initial conditions or parameters. Mathematically, this involves finding the image $f(\mathcal{X})$ of a set $\mathcal{X}$ under a smooth mapping function $f$.
Computing this set directly is often computationally intractable. A common practical approach is to sample points $x_i$ from the input set $\mathcal{X}$, compute their images $f(x_i)$, and construct their convex hull—the smallest convex shape containing the sampled points. While effective in practice, providing rigorous theoretical guarantees (error bounds) on how closely this estimate approximates the true convex hull has been difficult. Previous bounds were often too conservative or relied on the assumption that the output set was "well-behaved" (e.g., having a positive reach), an assumption that fails when the mapping causes the set to self-intersect.
Theoretical Framework: Smoothness and Submersions
This research introduces a framework based on differential geometry that shifts the focus from the potentially complex geometry of the output set to the properties of the input set and the mapping function.
$r$-Smoothness
The authors assume the input set $\mathcal{X}$ is $r$-smooth. Geometrically, this means that a ball of radius $r$ can roll freely along both the interior and exterior of the set's boundary without being obstructed by sharp corners or narrow passages.
The Concept of Reach
Traditional geometric proofs often rely on the "reach" of a set—the distance from the set to its medial axis. When a mapping $f$ causes a set to fold or self-intersect, the reach of the resulting image $f(\mathcal{X})$ can drop to zero, rendering standard bounds inapplicable.
Submersion Mappings
The study focuses on "submersions"—smooth maps that do not "collapse" dimensions in a way that introduces sharp corners into the convex hull. This class of functions is sufficiently broad to encompass many physical and dynamical systems.
The Quadratic Error Bound
The core contribution of this work is the proof of a quadratic error bound. The authors demonstrate that the Hausdorff distance $d_H$ (a metric for shape similarity) between the true convex hull and the sampled estimate is $O(\delta^2)$, where $\delta$ represents the maximum distance between samples on the boundary of $\mathcal{X}$.
Specifically, Theorem 1.1 provides the explicit formula: $$d_H \leq \frac{1}{2} \left(\frac{\bar{L}}{r} + \bar{H}\right) \delta^2$$ where $r$ is the smoothness of the input set, and $\bar{L}, \bar{H}$ are Lipschitz constants related to the function and its derivative. This represents a significant improvement over standard linear "Lipschitz" bounds ($O(\delta)$). In practical terms, doubling the sampling density results in a fourfold reduction in error.
Key Insights
- Geometric Healing: Even if the image $f(\mathcal{X})$ is non-convex or self-intersecting, the boundary of its convex hull remains a smooth manifold. This allows the application of differential geometry tools that would otherwise be invalid.
- Boundary Importance: The estimation error is primarily determined by the sampling density on the boundary of the input set, rather than its interior.
- Efficiency: The tighter bound justifies using significantly fewer samples to achieve required safety and precision guarantees.
Applications and Results
The theoretical findings were validated through numerical simulations:
- Spacecraft Planning: In a simulation of a spacecraft with uncertain payload mass and disturbances, the new bound showed that 100 samples provided the same precision guarantee that would have required 3,300 samples under older, more conservative bounds.
- Computational Performance: The increased efficiency allowed robust trajectory optimization to be performed in 200ms, a massive improvement over the 25 seconds required by previous methods.
Limitations and Future Work
The current theory assumes noise-free samples exactly on the boundary of $\mathcal{X}$ and perfect knowledge of the mapping $f$. Future research may address the impact of noisy data and extend the framework to non-submersion mappings or non-convex approximations like Delaunay complexes.
Summary updated