= Adaptive clearance sampling
<Adaptive clearance sampling> spends more <collision detection> queries on portions of a trajectory that are difficult to certify, instead of accepting a path merely because a fixed set of samples is clear. Its guarantee comes from a bound on motion between samples. A <configuration space> path must satisfy the geometric constraints continuously.<Robotic Systems by Kris Hauser>[Chapter 8, Stating the motion planning problem; Chapter 9, clearance]{ref}
Represent the body by a nonempty <compact set> and the fixed obstacles by a nonempty <closed set>. Let $d(t)$ be their nonnegative <set distance>, and suppose a known <Lipschitz continuity> bound gives $|d(t)-d(s)|\le L|t-s|$. On an interval of duration $h$ with endpoint clearances $d_0,d_1$, each time is at most $h/2$ from one endpoint. Hence an <endpoint certificate for continuous collision clearance> is
$$
d(t)\ge\min(d_0,d_1)-Lh/2.
$$
If this lower bound is strictly positive, the entire interval is clear. For a <required clearance margin> $d_{\rm safe}\ge0$, require the bound to exceed $d_{\rm safe}$ instead. Otherwise query the midpoint and subdivide. A sharper certificate uses both endpoint cones; when $L>0$ and the distances satisfy the assumed bound, its minimum is $(d_0+d_1-Lh)/2$. The simpler bound is sufficient for the example below.
For a translating and rotating <rigid body>, a valid speed estimate is $L=v_{\max}+R\omega_{\max}$, where $R$ is a <bounding radius for rigid-body clearance>, provided these are bounds over the whole interval and the obstacles stay fixed. The <angular clearance bound for a rotating body> proves the rotational contribution. A distance-estimation error bounded by $\varepsilon$ can be accommodated by replacing each reported endpoint distance by its lower bound $\widehat d_i-\varepsilon$.
In an original point-motion example, $q(t)=(vt,0.01\,\mathrm m)$ with $v=1\,\mathrm{m/s}$ and $0\le t\le1\,\mathrm s$ passes the obstacle point $(0.5,0)\,\mathrm m$. Its exact clearance is $d(t)=\sqrt{(vt-0.5\,\mathrm m)^2+(0.01\,\mathrm m)^2}$ and $L=1\,\mathrm{m/s}$ suffices. Require $d_{\rm safe}=0.005\,\mathrm m$. The initial endpoint certificate is positive but below this required margin, so more queries are needed. Recursive midpoint sampling certifies long intervals away from the obstacle and refines only near the closest approach. The stated midpoint rule uses 15 distance queries and certifies 14 intervals. The figure shows the exact function alongside the sampled certificate; the formula is known here only because the example is constructed.
\Image[/adaptive-clearance-sampling.png]
{title=Adaptive endpoint certificates for a trajectory passing 0.01 m from a point obstacle, with a required clearance of 0.005 m. Original exact geometry and recursive midpoint calculation.}
<Unresolved intervals in adaptive collision checking> must remain unresolved if a chosen depth or time budget is exhausted: failure to certify positive clearance does not establish a collision. Conversely, a query with exact zero <set distance> establishes contact or intersection. A sampled positive distance at or below $d_{\rm safe}$ violates the requested margin but does not establish contact. With exact queries, a valid finite $L$ and a trajectory whose clearance has a positive lower bound, subdivision eventually certifies every interval for $d_{\rm safe}=0$; a positive requested margin requires a positive surplus above that margin. Without positive clearance, finite termination is not promised.
Back to article page
