= Multi-sample clearance envelope
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.<Robotic Systems by Kris Hauser>[Chapter 8, Point-to-point path planning; Chapter 9, configuration-space obstacles]{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>, define
$$
\boxed{d_-(t)=\max\{0,\max_i(\ell_i-L|t-t_i|)\},\qquad
d_+(t)=\min_i(u_i+L|t-t_i|).}
$$
Every 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. Put
$$
A_k=\max_{i\le k}(\ell_i+Lt_i),\qquad B_k=\max_{i\ge k+1}(\ell_i-Lt_i).
$$
Then $d_-(t)=\max(0,A_k-Lt,B_k+Lt)$. For $L>0$, its minimum occurs at the crossing $t_*=(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=4\,\mathrm{mm/s}$. On the first segment, $A_0=5$ and $B_0=2$ in the corresponding millimetre/second coordinates. The crossing is $t_*=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.
Back to article page
