= Clearance certificate with bounded distance-query error
{title2=$\widehat d-\varepsilon_d$}
A <clearance certificate with bounded distance-query error> proves separation over a continuous motion interval when sampled distances are known only within stated error bounds. A positive returned value from <collision detection> is not by itself a lower bound on the true geometric distance. Approximation, floating-point error and model error must be included if they affect the intended claim.
Let true <set distance> $d(t)\ge0$ satisfy $|d(t)-d(s)|\le L|t-s|$ on $[0,h]$. At endpoints, assume certified query errors $|d_i-\widehat d_i|\le\epsilon_i$. Define
$$
\ell_i=\max(0,\widehat d_i-\epsilon_i),\qquad u_i=\widehat d_i+\epsilon_i.
$$
Provided the query bounds are consistent with nonnegative distances, $\ell_i\le d_i\le u_i$. The endpoint lower bounds propagate into
$$
d(t)\ge\max\{0,\ell_0-Lt,\ell_1-L(h-t)\}.
$$
This extends the <endpoint certificate for continuous collision clearance>. The primary planning model requires feasibility along the whole continuous path; checking endpoint poses alone is insufficient.<Robotic Systems by Kris Hauser>[Chapter 8, Point-to-point path planning; Chapter 9, rotational configuration-space obstacles]{ref}
The minimum of this envelope must be computed on the actual interval. Its general closed form, including unequal lower bounds, is
$$
\boxed{d(t)\ge b:=\max\left\{0,\ell_0-Lh,\ell_1-Lh,
\frac{\ell_0+\ell_1-Lh}{2}\right\}.}
$$
For $L>0$ and $|\ell_1-\ell_0|\le Lh$, the two sloping bounds meet inside the interval and the average expression dominates the other nonzero candidates. If $\ell_1-\ell_0>Lh$, their intersection lies before the interval; the minimum is instead $\max(0,\ell_1-Lh)$. The opposite inequality exchanges the endpoints. For $L=0$, the formula reduces to $\max(\ell_0,\ell_1)$ because true clearance is constant.
The lower bounds themselves need not satisfy the consistency condition for exact endpoint distances. For example, $\ell_0=2\,\mathrm{mm}$, $\ell_1=20\,\mathrm{mm}$ and $Lh=10\,\mathrm{mm}$ permit a true clearance rising from $10$ to $20\,\mathrm{mm}$. Rejecting these lower bounds because their difference exceeds $Lh$ would wrongly treat them as exact observations. The general certificate gives $10\,\mathrm{mm}$; using only the intersecting-cone expression would give the weaker $6\,\mathrm{mm}$.
A second original example takes reported distances $12$ and $20\,\mathrm{mm}$, errors $1$ and $3\,\mathrm{mm}$, and $Lh=10\,\mathrm{mm}$. Then $\ell_0=11$ and $\ell_1=17\,\mathrm{mm}$, so $b=9\,\mathrm{mm}$. The error-free formula would have claimed $11\,\mathrm{mm}$. For a required strict margin above $10\,\mathrm{mm}$, the uncertain queries do not certify the interval. Tightening both errors to $0.5\,\mathrm{mm}$ raises the lower bound to $10.5\,\mathrm{mm}$ and supplies the requested certificate.
<Compatibility of bounded endpoint distance queries> also uses the upper bounds. The intervals must obey $\ell_0\le u_0$, $\ell_1\le u_1$, $\ell_0\le u_1+Lh$ and $\ell_1\le u_0+Lh$. A violated condition signals inconsistent assumptions. An upper distance bound at or below a required margin can establish a sampled margin violation; failure of a lower-bound certificate alone does not establish a collision.
A proposed checker records the query’s enclosure guarantee, units and geometric model, propagates the motion bound with the actual interpolation, and leaves uncertified intervals unresolved for further subdivision or stronger queries. A standard deviation is not a deterministic query enclosure. A certificate against a nominal obstacle model also needs a separate justified relation to the actual obstacle geometry before it can be interpreted physically.
Back to article page
