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.^[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.