= Unresolved intervals in adaptive collision checking
<Unresolved intervals in adaptive collision checking> are trajectory intervals for which the available queries and motion bounds prove neither the requested continuous clearance nor a violation at a known configuration. They are a computational result of incomplete information, rather than evidence that a collision occurred.
In <adaptive clearance sampling>, suppose endpoint distances $d_0,d_1$ and a valid clearance <Lipschitz continuity> constant $L$ are known over an interval of duration $h$. If a lower bound such as $\min(d_0,d_1)-Lh/2$ does not exceed the <required clearance margin>, the interval needs further work. Its endpoints can both be clear while its interior remains undecided. The continuous-path requirement motivating this distinction is stated in the primary planning text.<Robotic Systems by Kris Hauser>[Chapter 8, Stating the motion planning problem and Point-to-point path planning]{ref}
An original indistinguishability example uses $0\le t\le1\,\mathrm s$, $L=1\,\mathrm{m/s}$ and endpoint clearances $0.4\,\mathrm m$. Both of the following functions satisfy the same endpoint data and motion bound:
$$
d_A(t)=0.4\,\mathrm m,\qquad
d_B(t)=\max\left\{0,\,0.4\,\mathrm m-(1\,\mathrm{m/s})\min(t,1\,\mathrm s-t)\right\}.
$$
They can be realized by the height of a point moving above a fixed horizontal wall. The first path stays clear; the second reaches the wall. For a requested $0.05\,\mathrm m$ separation, the initial endpoint certificate is $0.4-0.5=-0.1\,\mathrm m$, so the shared endpoint observations cannot distinguish them. A negative lower estimate does not establish a negative physical distance.
Querying the midpoint resolves this constructed example. Model A gives another $0.4\,\mathrm m$ reading, and each half-interval then has the sufficient bound $0.4-0.25=0.15\,\mathrm m>0.05\,\mathrm m$. Model B gives zero, demonstrating contact. More generally, a strictly positive sampled distance at or below the requested margin establishes a margin violation but not a collision. Exact zero <set distance> establishes contact or intersection when the modeled body is a nonempty <compact set> and the obstacles form a nonempty <closed set>.
If the chosen query, time or subdivision budget expires first, retain the undecided intervals explicitly. Accepting the whole trajectory would discard the unverified portions; labeling every undecided portion a collision would also claim information not obtained.
For exact queries, finite $L>0$ and a true minimum clearance at least $d_{\rm safe}+\eta$ with $\eta>0$, subdivision eventually yields $h<2\eta/L$, making the simple certificate sufficient everywhere. A trajectory merely touching the required threshold has no such surplus. A <clearance certificate with bounded distance-query error> must also account for how conservative query bounds affect that remaining surplus.
Back to article page
