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\ge 0$. Write $c=Lh$. Compatibility means there exist $a\in I_0$ and $b\in I_1$ satisfying $|a-b|\le c$. The exact condition isalong 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 toThese 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^{\prime }=[5,8]\mathrm{mm}$ and $I_1^{\prime }=[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=10mm/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.^[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.

Multi-sample consistency of distance-query intervals asks whether every bounded distance reading can belong to one nonnegative clearance function with the claimed Lipschitz constant. The same motion history must explain all samples. Checking each adjacent pair in isolation can select a different intermediate distance for each check and miss a contradiction.

Let strictly increasing times $t_0,\dots ,t_n$ have nonempty intervals $[{\ell }_i,u_i]$, with $0\le {\ell }_i\le u_i$, and let $L\ge 0$ bound clearance change per unit time. Necessary and sufficient conditions areNecessity follows by comparing any feasible distances $d(t_i),d(t_j)$ using Lipschitz continuity. For sufficiency, constructEach envelope has Lipschitz constant at most $L$. The pairwise conditions and the triangle inequality imply $f_{-}(t)\le f_{+}(t)$ everywhere. At each sample time, ${\ell }_i\le f_{-}(t_i)\le u_i$, so $f_{-}$ itself is an admissible nonnegative clearance history. This proves existence, not that this constructed history is the robot's actual history.

The intervals $[f_{-}(t_i),f_{+}(t_i)]$ are exact feasible projections at sample times. Both bounding functions are feasible and convex combinations of them remain feasible, so every intermediate value at one fixed time is attainable. The associated multi-sample clearance envelope also gives between-sample lower bounds for a clearance certificate with bounded distance-query error.

For an original counterexample to adjacent-only testing, let successive times differ by one second, take $L=4mm/s$, and useThe first adjacent pair can use middle distance $0$, and the second can use middle distance $10$; each pair is compatible. Yet the endpoints require a $10\mathrm{mm}$ change in two seconds, exceeding the allowed $8\mathrm{mm}$. No common history exists.

An equivalent linear-time feasibility test propagates a reachable interval. Start $J_0=I_0$ and recursively setStop if an interval becomes empty. In the example, $J_1=[0,4]$ and the next propagated upper bound is $8$, so $J_2$ is empty. Retaining the tightened interval is the key difference from independent adjacent-pair checks. If all intervals remain nonempty, select a final value and work backward through the reachable intervals; piecewise linear interpolation yields a feasible history.

Incompatibility diagnoses inconsistent readings or assumptions, not a demonstrated collision. Compatibility proves only the existence of a scalar clearance history; it does not prove that some rigid robot trajectory realizes that history or that the true clearance stays positive. Continuous collision avoidance remains a constraint along the physical path, as in the primary motion-planning formulation.^[ref] A proposed implementation tests synthetic histories with known bounds, deliberately inconsistent triples and timestamp errors, keeping model inconsistency separate from insufficient clearance.

A multi-sample clearance envelope bounds every possible instantaneous clearance consistent with several uncertain distance queries and a known motion-rate limit. It sharpens isolated endpoint estimates by requiring one Lipschitz continuous clearance history to explain all samples. Such a bound addresses the between-sample gap in continuous robot motion planning, where valid sampled configurations alone do not guarantee a valid path.^[ref]

At times $t_i$, let $0\le {\ell }_i\le d(t_i)\le u_i$, and suppose the nonnegative clearance $d$ has Lipschitz constant $L$. Assuming multi-sample consistency of distance-query intervals, defineEvery admissible history obeys $d_{-}\le d\le d_{+}$. Each lower cone follows from $d(t)\ge d(t_i)-L|t-t_i|$; the upper cones follow by reversing the inequality. Under consistency, both envelope functions themselves satisfy the sample intervals and the same Lipschitz bound. Thus the enclosure is pointwise sharp among the scalar histories allowed by these assumptions.

A positive minimum of $d_{-}$ over a time interval certifies separation throughout it. If that minimum is zero, the assumptions permit a scalar history touching zero; this is lack of a strictly positive certificate, not an observation of collision. Some admissible scalar histories may not correspond to a realizable rigid-body path, so sharpness here concerns the stated scalar model.

The exact interval minimum is inexpensive to compute. On $[t_k,t_{k+1}]$, all sample times lie on one side or the other. PutThen $d_{-}(t)=\max (0,A_k-Lt,B_k+Lt)$. For $L>0$, its minimum occurs at the crossing $t_{\ast }=(A_k-B_k)/(2L)$ if that crossing lies in the interval; otherwise it occurs at the nearer endpoint. Prefix and suffix maxima therefore allow all segment minima to be computed in linear time. For $L=0$, every admissible clearance is constant and the lower envelope is ${\max }_i{\ell }_i$.

For an original example, queries at $0,1,2\mathrm{s}$ give intervals $[5,7]$, $[6,8]$, $[5,7]\mathrm{mm}$, and $L=4mm/s$. On the first segment, $A_0=5$ and $B_0=2$ in the corresponding millimetre/second coordinates. The crossing is $t_{\ast }=0.375\mathrm{s}$ and the lower bound there is $3.5\mathrm{mm}$. Symmetry gives a second minimum at $1.625\mathrm{s}$, so the full interval is certified with margin $3.5\mathrm{mm}$. Using only the two outer queries would give a minimum of $1\mathrm{mm}$.

A proposed checker first tests consistency, then computes segment minima with conservative arithmetic and reports the limiting time and active queries. Keep query errors, timestamps and the bound $L$ traceable to the same geometry and motion. Clearance envelope with segment-dependent speed bounds can use more motion information, but replacing $L|t-t_i|$ by an unsupported smaller number would invalidate the certificate.