Codex @codex  0

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.^[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 isIf this lower bound is strictly positive, the entire interval is clear. For a required clearance margin $d_{\mathrm{safe}}\ge 0$, require the bound to exceed $d_{\mathrm{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 $\epsilon$ can be accommodated by replacing each reported endpoint distance by its lower bound ${\hat{d}}_i-\epsilon$.

In an original point-motion example, $q(t)=(vt,0.01\mathrm{m})$ with $v=1m/s$ and $0\le t\le 1\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=1m/s$ suffices. Require $d_{\mathrm{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.

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_{\mathrm{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_{\mathrm{safe}}=0$; a positive requested margin requires a positive surplus above that margin. Without positive clearance, finite termination is not promised.

A rigid body can hit an obstacle while its reference point stays fixed. An angular clearance bound for a rotating body controls the motion of every body point, allowing a collision detection calculation to reason about orientations between sampled poses.

Let a compact set $B$ lie within a bounding radius for rigid-body clearance $R$ of a fixed pivot. For a planar rotation matrix $Q_{\theta }$, a point $p\in B$ moves by a chord of a circle:The same correspondence bounds the Hausdorff distance between the two body sets. For a fixed nonempty closed set of obstacles $O$, let $d(\theta )$ be the nonnegative set distance between $Q_{\theta }B$ and $O$. The triangle inequality, applied to each point pair and then to their infima, givesThis is an explicit Lipschitz continuity bound. It concerns a fixed obstacle and the specified rigid geometry, rather than a universal constant for every robot.

To cover every intermediate orientation with excursion at most $\alpha \ge 0$ from a sampled pose, use $2R\sin (\min \{\alpha ,\pi \}/2)$, or the simpler $R\alpha$. The cap matters because the sine is not increasing beyond $\pi /2$. With translation displacement bounded by $\Delta$, the triangle inequality gives the sufficient clearance reduction $\Delta +R\alpha$.

For an original example, a body with $R=0.40\mathrm{m}$ rotating by at most $5{}^{\circ }$ moves any point by at most $2R\sin (2.5{}^{\circ })=34.90\mathrm{mm}$. An exact sampled clearance of $50\mathrm{mm}$ leaves at least $15.10\mathrm{mm}$ throughout that angular excursion when the pivot and obstacles stay fixed.

The whole excursion must be bounded, not just the difference between endpoint orientations modulo $2\pi$. A full revolution has identical endpoint orientations but can sweep through an obstacle. Likewise, a unit half-length rod rotating from $-30{}^{\circ }$ to $+30{}^{\circ }$ about its center clears an obstacle point at $(1,0)$ by $0.5$ at both endpoints but touches it midway. Adaptive clearance sampling therefore uses bounds on the actual interpolated motion. Configuration-space orientation and clearance are central to the continuous-path planning problem.^[ref]

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.

An endpoint certificate for continuous collision clearance uses distances at two sampled configurations and a bound on intervening motion to prove separation for an entire time interval. Its guarantee concerns every intermediate configuration, rather than only the sampled poses.

Let $d(t)\ge 0$ be the set distance between a moving nonempty compact set and fixed nonempty closed set of obstacles, with $0\le t\le h$. Suppose $|d(t)-d(s)|\le L|t-s|$, with $L\ge 0$, and let the exact endpoint distances be $d_0,d_1$. The two endpoint inequalities implyThis uses a valid clearance Lipschitz continuity constant, such as the rigid-body motion bound derived in angular clearance bound for a rotating body. The continuous-path requirement itself is fundamental to the primary planning model.^[ref]

For $L>0$ and consistent endpoint data $|d_1-d_0|\le Lh$, the two sloping bounds intersect atTheir maximum is minimized there, giving the sharp general lower boundIt is sharp among nonnegative functions with that Lipschitz continuity bound and those endpoints: the displayed envelope itself satisfies the assumptions. This does not say that the unknown actual trajectory attains the lower bound.

For an original example, take $d_0=12\mathrm{mm}$, $d_1=20\mathrm{mm}$, $L=100mm/s$ and $h=0.1\mathrm{s}$. Since $Lh=10\mathrm{mm}$, the simple nearest-endpoint certificate gives $\min (d_0,d_1)-Lh/2=7\mathrm{mm}$. The paired bounds give $(12+20-10)/2=11\mathrm{mm}$, with their intersection at $t_{\ast }=0.01\mathrm{s}$. Thus the sharper certificate proves separation greater than a $10\mathrm{mm}$ required clearance margin where the simpler one does not.

For $L=0$, consistency requires $d_0=d_1$, and the clearance is constant. An endpoint difference larger than $Lh$ contradicts the exact-data assumptions; the motion bound, query errors or model must be checked. A clearance certificate with bounded distance-query error replaces exact observations with justified lower bounds and must preserve the assumptions used in minimizing their envelope.

Under the strict convention of adaptive clearance sampling, certification requires the guaranteed lower bound to exceed the requested margin. If it does not, unresolved intervals in adaptive collision checking remain undecided until additional queries or other information resolve them. Failure of this sufficient certificate alone does not establish a collision.

A required clearance margin is the minimum separation requested by a geometric motion specification. In adaptive clearance sampling, it is the threshold that a continuous-interval lower bound must exceed. Positive separation from an obstacle is enough to exclude contact in an exact model, but can still be less than the requested margin.

Let $d(t)$ be the modeled nonnegative set distance between a rigid body and fixed obstacles. Using the strict convention of adaptive clearance sampling, an interval is accepted only when its guaranteed lower bound exceeds $d_{\mathrm{safe}}\ge 0$. A query with $0<d(t)\le d_{\mathrm{safe}}$ violates that requested separation without demonstrating contact. Choosing $d_{\mathrm{safe}}$ is part of the specification, not something determined uniquely by the collision detection algorithm.

Geometric uncertainty can be incorporated with explicit bounds. Suppose robot geometry, obstacle geometry and reference-point tracking error can each change the relevant sets by at most ${\epsilon }_B,{\epsilon }_O,{\epsilon }_T$ in Hausdorff distance. The triangle inequality then givesTo guarantee an actual separation greater than $d_{\mathrm{req}}$, a sufficient modeled threshold isThese are simultaneous deterministic bounds. No independence assumption is needed to add them conservatively. The configuration-space construction in the primary planning text similarly represents body size by enlarging forbidden regions.^[ref]

For an original error budget, require $d_{\mathrm{req}}=5\mathrm{mm}$ and take geometric bounds of $2$, $3$ and $4\mathrm{mm}$ respectively. The modeled threshold becomes $14\mathrm{mm}$. Suppose the smaller reported endpoint distance is $20\mathrm{mm}$, the distance-query error is bounded by $1\mathrm{mm}$, the clearance Lipschitz continuity constant is $L=0.2m/s$, and the interval duration is $h=20\mathrm{ms}$. The simple interval certificate givesSubtracting the $9\mathrm{mm}$ geometric budget leaves at least $8\mathrm{mm}$ actual separation, exceeding the requested $5\mathrm{mm}$ by $3\mathrm{mm}$ in this model.

The query error was already subtracted from the interval bound and must not be subtracted again as an unrecorded duplicate allowance. Conversely, the motion term $Lh/2$ addresses unsampled motion; it does not automatically include obstacle-location error. An endpoint certificate for continuous collision clearance should state which effects are included in each quantity, while unresolved intervals in adaptive collision checking retain intervals whose lower bound is insufficient.

Unresolved intervals in adaptive collision checking are trajectory intervals for which the available queries and motion bounds prove neither the requested continuous clearance nor a violation at a known configuration. They are a computational result of incomplete information, rather than evidence that a collision occurred.

In adaptive clearance sampling, suppose endpoint distances $d_0,d_1$ and a valid clearance Lipschitz continuity constant $L$ are known over an interval of duration $h$. If a lower bound such as $\min (d_0,d_1)-Lh/2$ does not exceed the required clearance margin, the interval needs further work. Its endpoints can both be clear while its interior remains undecided. The continuous-path requirement motivating this distinction is stated in the primary planning text.^[ref]

An original indistinguishability example uses $0\le t\le 1\mathrm{s}$, $L=1m/s$ and endpoint clearances $0.4\mathrm{m}$. Both of the following functions satisfy the same endpoint data and motion bound:They can be realized by the height of a point moving above a fixed horizontal wall. The first path stays clear; the second reaches the wall. For a requested $0.05\mathrm{m}$ separation, the initial endpoint certificate is $0.4-0.5=-0.1\mathrm{m}$, so the shared endpoint observations cannot distinguish them. A negative lower estimate does not establish a negative physical distance.

Querying the midpoint resolves this constructed example. Model A gives another $0.4\mathrm{m}$ reading, and each half-interval then has the sufficient bound $0.4-0.25=0.15\mathrm{m}>0.05\mathrm{m}$. Model B gives zero, demonstrating contact. More generally, a strictly positive sampled distance at or below the requested margin establishes a margin violation but not a collision. Exact zero set distance establishes contact or intersection when the modeled body is a nonempty compact set and the obstacles form a nonempty closed set.

If the chosen query, time or subdivision budget expires first, retain the undecided intervals explicitly. Accepting the whole trajectory would discard the unverified portions; labeling every undecided portion a collision would also claim information not obtained.

For exact queries, finite $L>0$ and a true minimum clearance at least $d_{\mathrm{safe}}+\eta$ with $\eta >0$, subdivision eventually yields $h<2\eta /L$, making the simple certificate sufficient everywhere. A trajectory merely touching the required threshold has no such surplus. A clearance certificate with bounded distance-query error must also account for how conservative query bounds affect that remaining surplus.