= Compatibility of bounded endpoint distance queries
<Compatibility of bounded endpoint distance queries> asks whether two uncertain distance readings could arise from any nonnegative clearance function obeying a stated motion bound. It tests consistency of the observations and assumptions; it does not itself prove that the entire motion is collision-free.
Suppose endpoint queries yield intervals $I_0=[\ell_0,u_0]$ and $I_1=[\ell_1,u_1]$ for the true <set distances>, with $0\le\ell_i\le u_i$. Let the interval duration be $h>0$ and clearance have <Lipschitz continuity> constant $L\ge0$. Write $c=Lh$. Compatibility means there exist $a\in I_0$ and $b\in I_1$ satisfying $|a-b|\le c$. The exact condition is
$$
\boxed{\ell_0\le u_1+c,\qquad \ell_1\le u_0+c,}
$$
along with the two intervals being nonempty and nonnegative. Equivalently, the gap between the two intervals, $\max(0,\ell_0-u_1,\ell_1-u_0)$, must not exceed $c$.
Necessity follows because $a\ge\ell_0$, $b\le u_1$ and $a-b\le c$, with the reversed argument for the other inequality. For sufficiency, overlapping intervals allow $a=b$ at any common point. If they are disjoint, choose their nearest endpoints; the boxed condition bounds that separation by $c$. Linear interpolation between the selected nonnegative endpoints has slope at most $L$, proving that at least one admissible continuous clearance function exists.
The feasible endpoint intervals can be tightened to
$$
I_0'=\left[\max(\ell_0,\ell_1-c),\ \min(u_0,u_1+c)\right],
\qquad
I_1'=\left[\max(\ell_1,\ell_0-c),\ \min(u_1,u_0+c)\right].
$$
These are the exact projections of the feasible endpoint-pair set onto each coordinate. A large difference between the lower bounds alone is not a contradiction: lower bounds are not exact distances.
For an original example, take $I_0=[4,8]\,\mathrm{mm}$, $I_1=[15,20]\,\mathrm{mm}$ and $Lh=10\,\mathrm{mm}$. Their nearest endpoints differ by $7\,\mathrm{mm}$, so the data are compatible. Tightening gives $I_0'=[5,8]\,\mathrm{mm}$ and $I_1'=[15,18]\,\mathrm{mm}$. By contrast, $[1,3]$ and $[15,17]\,\mathrm{mm}$ have a $12\,\mathrm{mm}$ minimum gap and are incompatible with the same motion bound.
Incompatibility means that some query enclosure, motion bound, timing or model assumption is wrong. It is not evidence that a collision occurred. Compatibility also need not certify separation: exact endpoint distances of $5\,\mathrm{mm}$ over one second with $L=10\,\mathrm{mm/s}$ permit both constant clearance and a V-shaped clearance touching zero halfway through. The <clearance certificate with bounded distance-query error> evaluates a lower envelope over the full interval to answer that additional question.
For $L=0$, compatibility reduces to overlap of the intervals because clearance is constant. With more query times, <multi-sample consistency of distance-query intervals> must preserve one common clearance model rather than checking unrelated pairs with incompatible bounds. The primary motion-planning formulation requires constraints along a continuous path, motivating these between-sample checks.<Robotic Systems by Kris Hauser>[Chapter 8, Point-to-point path planning; Chapter 9, configuration-space obstacles]{ref}
A proposed checker retains query lower and upper bounds, the clock interval, geometry version and motion allowance. It should report inconsistent inputs separately from undecided clearance intervals and certified margin violations. Tight numerical arithmetic alone cannot turn an unsupported standard uncertainty into a deterministic distance enclosure.
Back to article page
