= Multi-sample consistency of distance-query intervals
<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,\ldots,t_n$ have nonempty intervals $[\ell_i,u_i]$, with $0\le\ell_i\le u_i$, and let $L\ge0$ bound clearance change per unit time. Necessary and sufficient conditions are
$$
\boxed{\ell_i\le u_j+L|t_i-t_j|\quad\text{for every pair }i,j.}
$$
Necessity follows by comparing any feasible distances $d(t_i),d(t_j)$ using <Lipschitz continuity>. For sufficiency, construct
$$
f_-(t)=\max\bigl(0,\max_i[\ell_i-L|t-t_i|]\bigr),\qquad
f_+(t)=\min_i[u_i+L|t-t_i|].
$$
Each 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=4\,\mathrm{mm/s}$, and use
$$
I_0=[0,0],\qquad I_1=[0,10],\qquad I_2=[10,10]\quad\mathrm{mm}.
$$
The 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 set
$$
J_i=I_i\cap[\inf J_{i-1}-L(t_i-t_{i-1}),\ \sup J_{i-1}+L(t_i-t_{i-1})].
$$
Stop 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.<Robotic Systems by Kris Hauser>[Chapter 8, Point-to-point path planning; Chapter 9, configuration-space obstacles]{ref} A proposed implementation tests synthetic histories with known bounds, deliberately inconsistent triples and timestamp errors, keeping model inconsistency separate from insufficient clearance.
Back to article page
