 Clearance bound between trajectory samples

A clearance bound between trajectory samples converts finitely many separation checks into a guarantee over a continuous trajectory, using a justified bound on how quickly clearance can change. Clear endpoints alone are insufficient: a foot or another robot part can approach an obstacle and move away again between them. The primary planning formulation requires constraints along the entire path.^[ref]

Let nominal clearance $c(s)$ have Lipschitz constant $L$ on a checked interval $[s_i,s_{i+1}]$ of length $h$. If both endpoint clearances are at least $c_{\min }$, then every intermediate point is within $h/2$ of an endpoint. ConsequentlyThis follows directly from $c(s)\ge c(s_i)-L|s-s_i|$ using the nearer endpoint. A uniform additional worst-case geometry or execution allowance $e$ gives actual clearance at least $c_{\min }-Lh/2-e$.

A tighter interval certificate retains the two different endpoint values, $a=c(s_i)$ and $b=c(s_{i+1})$. Writing $u=s-s_i$ gives two lower cones,If $L>0$ and $|a-b|\le Lh$, the cones meet inside the interval. Their common height yieldsIf the endpoint difference exceeds $Lh$, the proposed Lipschitz bound and exact endpoint values are inconsistent; simply applying the formula does not repair that inconsistency. With $L=0$, clearance is constant.

For an original example, take $h=0.10\mathrm{s}$, $L=0.20\mathrm{m}{\mathrm{s}}^{-1}$, $a=18\mathrm{mm}$ and $b=26\mathrm{mm}$. The simpler endpoint-minimum bound gives $8\mathrm{mm}$; the two-cone bound gives $12\mathrm{mm}$. Subtracting a $4\mathrm{mm}$ execution allowance leaves a certified $8\mathrm{mm}$ actual gap, sufficient for a requested $5\mathrm{mm}$ margin. These are lower bounds, not assertions that the trajectory reaches their values.

A counterexample explains why the allowance is necessary. On $[0,1]$, $c(s)=1-4s(1-s)$ has endpoint values one but touches zero at the midpoint. Checking only those endpoints misses the contact. Its derivative is bounded in magnitude by four, so a sufficiently fine sample grid with that valid bound can expose the missing guarantee.

The constant must match the geometry and parameter units. For a point moving relative to a fixed closed obstacle set, the distance to that set changes by at most the point’s displacement: the triangle inequality gives $|d_O(x)-d_O(y)|\le \Vert x-y\Vert$. A speed bound therefore supplies a time-based clearance bound. A rotating body requires a bound on every occupied point, such as the angular clearance bound for a rotating body; terrain-height clearance across a discontinuous edge cannot use a finite slope bound across that jump.

Adaptive clearance sampling subdivides intervals that fail the chosen certificate, concentrating computation where the margin or speed bound is least favorable. Failure of a conservative certificate means the interval needs better bounds or further checking; it does not itself prove a collision. For a proposed robot-foot test, validate the motion and geometry error bounds in one coordinate frame and compare the certified interval minima with dense independent measurements. Use the robust swing-foot clearance margin allowances without counting the same uncertainty twice.