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 bounding radius for rigid-body clearance bounds the distance of every point of a rigid body from the reference point used to describe its motion. It converts angular motion into a bound on point displacement, so collision detection can account for the whole body between sampled poses rather than only its reference point.

Let $B$ be a nonempty compact set in body coordinates and let $c$ be the chosen pivot in those coordinates. A valid radius satisfiesThe maximum exists by compactness and continuity of the Euclidean norm. A bound larger than $R_{\ast }$ is conservative; a smaller one does not cover the specified geometry. For a convex polytope with vertices $v_i$, it is sufficient and exact to use $R_{\ast }={\max }_i\Vert v_i-c\Vert$: expressing a point as a convex combination and applying the triangle inequality proves that no interior point is farther away than the farthest vertex.

For an original rectangular-body example, take side lengths $0.6\mathrm{m}$ and $0.8\mathrm{m}$. A pivot at the centre gives $R_{\ast }=\sqrt{0.3^2+0.4^2}=0.5\mathrm{m}$. A pivot at a corner instead gives $R_{\ast }=\sqrt{0.6^2+0.8^2}=1.0\mathrm{m}$. For a $5{}^{\circ }$ rotation about the respective fixed pivot, the angular clearance bound for a rotating body isThe smaller radius cannot be used for the corner-pivot motion unless the changed motion of the reference point is also included. A convenient geometric centre does not automatically remain stationary.

For a moving reference point with speed at most $v_{\max }$ and angular speed at most ${\omega }_{\max }$, a point-speed bound is $v_{\max }+R{\omega }_{\max }$. This supplies a Lipschitz continuity constant for clearance against fixed obstacles. The role of body geometry and orientation in configuration space is developed in the primary planning text.^[ref]

The modeled body must include attached tools and protrusions relevant to the query. Uncertainty in a rigid-body bounding radius can be accommodated with a conservative geometric enlargement. This radius controls motion around the declared reference point; it does not replace the separate required clearance margin for uncertain obstacle locations or tracking errors.

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.

An orientation-dependent configuration-space obstacle is the forbidden set for an extended robot whose occupied geometry changes with its orientation. For a planar rigid shape $B$ referred to a body-fixed point, translation $t\in {\mathbb{R}}^2$ and rotation matrix $R_{\theta }$, the occupied set is $t+R_{\theta }B$. With obstacle set $O$, collision meansFor each fixed angle, the forbidden translations are thereforeIndeed, an intersection gives $t+R_{\theta }b=o$, hence $t=o-R_{\theta }b$, and the converse follows by substitution. This is a reflected Minkowski sum, not an unreflected sum of the two shapes. Hauser develops these angle-indexed slices explicitly for a translating and rotating polygon.^[ref]

The full configuration-space obstacle is $\{(t,\theta ):t\in C_{\theta }\}$. Its angular coordinate is periodic: orientations zero and $2\pi$ represent the same rotation. Translation and orientation cannot generally be replaced by one planar obstacle inflation. A circular robot centered at its reference point is a special case, because rotating that shape leaves every $C_{\theta }$ unchanged.

An original doorway example uses a rectangle with half-length $a=0.30\mathrm{m}$ and half-width $b=0.10\mathrm{m}$, centered in an infinitely long horizontal corridor of width $W=0.25\mathrm{m}$. Its vertical half-extent at angle $\theta$ isWith contact counted as collision, a centered placement is clear only if $h(\theta )<W/2$. At zero angle the total width is $0.20\mathrm{m}$, leaving $25\mathrm{mm}$ at each wall. At $10^{\circ }$, the total width is about $0.3012\mathrm{m}$, so the same center position collides. For small positive angles, the first touching angle solves $0.30\sin \theta +0.10\cos \theta =0.125$, giving approximately $4.85^{\circ }$. A collision-free center path alone would miss this rotational restriction.

Angular sampling needs a bound on the geometry between checked orientations. If every body point lies within radius $\rho$ of the reference point, changing orientation by $\Delta \theta$ moves each corresponding point by at mostThe first expression is the chord length; the inequality follows from $\sin u\le u$. An angular clearance bound for a rotating body uses this motion allowance to transfer a measured separation to nearby orientations. For the rectangle above, $\rho =\sqrt{a^2+b^2}\approx 0.3162\mathrm{m}$. A ten-degree grid has a five-degree worst-case distance to a sampled orientation, allowing about $27.6\mathrm{mm}$ of point motion. A sampled $20\mathrm{mm}$ gap would not certify every intermediate orientation under that bound.

A geometric validation can place a rectangular test piece at predicted near-touching angles in a measured corridor, accounting for reference-point offsets and wall tolerances. A planner must also check the continuous motions connecting clear configurations; clear grid vertices alone do not establish clear connecting rotations. A conservative enclosing disk may simplify that check, at the cost of excluding some feasible narrow passages.

Pivot-location uncertainty in a rotational clearance bound describes how an error in the point about which a rigid rotation is modeled changes predicted occupied-point motion. A radius measured about one pivot is not automatically valid about another. The underlying planning problem must include both translation and orientation of the robot’s actual geometry.^[ref]

Let $Q$ be a fixed rotation matrix, $\hat{c}$ the modeled pivot, and $c=\hat{c}+e$ the actual pivot. First suppose the initial physical point $p$ is known exactly and both descriptions use the same rotation $Q$. The modeled and actual endpoints areso their difference is exactlyThis vanishes for zero rotation even if the pivot location is uncertain. Treating pivot error as an arbitrary full translation at every angle can therefore be unnecessarily conservative.

For a rotation through principal angle $0\le \theta \le \pi$ about a known axis direction, the component of $e$ along that direction is unchanged by $Q$. Its perpendicular component giveswhen $\Vert e\Vert \le {ϵ}_c$. The chord-length factor is the same geometry used in the angular clearance bound for a rotating body. For a $30^{\circ }$ rotation and ${ϵ}_c=2\mathrm{mm}$, the maximum endpoint error from pivot location alone is about $1.035\mathrm{mm}$. An equally large pivot offset parallel to the axis produces no endpoint change in this model.

If the initial point also has error $p-\hat{p}=\delta p$ with $\Vert \delta p\Vert \le {ϵ}_p$, thenFor the difference of displacement vectors, rather than final positions, the shape term is $(Q-I)\delta p$, giving the different bound $2({ϵ}_p+{ϵ}_c)\sin (\theta /2)$. The requested geometric quantity determines which allowance applies.

A complementary radius argument bounds total actual motion. If modeled points satisfy $\Vert \hat{p}-\hat{c}\Vert \le \hat{R}$, then $\Vert p-c\Vert \le \hat{R}+{ϵ}_p+{ϵ}_c$, and total point displacement is at most $2(\hat{R}+{ϵ}_p+{ϵ}_c)\sin (\theta /2)$. This is the enclosure approach in uncertainty in a rigid-body bounding radius; it need not equal an endpoint-error calculation against a nominal path.

Correlations can reduce the bound. If the same coordinate-frame translation shifts both the modeled point and pivot, relative geometry may be unchanged; treating those two descriptions as independent physical errors loses that cancellation. Conversely, rotation-axis direction uncertainty in clearance bounds changes $Q$ itself and is not covered by the fixed-$Q$ pivot formula.

A proposed rotary-stage check observes several rigid fiducials, estimates the pivot and axis in one coordinate frame, and compares independent endpoint measurements at several angles with the predicted chord scaling. Include attached tools and measurement uncertainty. When the robot moves against an uncertain obstacle, combine this occupied-point model with a separately justified distance-query enclosure; a correct pivot bound does not establish the obstacle model’s accuracy.

Uncertainty in a rigid-body bounding radius concerns whether the radius used in a motion bound actually encloses the robot about its declared pivot. A nominal mesh radius can miss manufacturing tolerances, an attached tool or an uncertain reference-point location. The bounding radius for rigid-body clearance must bound the relevant actual occupied geometry, not only a convenient displayed shape.

Let modeled body $\hat{B}$ and modeled pivot $\hat{c}$ satisfy $\Vert \hat{p}-\hat{c}\Vert \le \hat{R}$ for every $\hat{p}\in \hat{B}$. Suppose every point $p$ of the actual body lies within ${ϵ}_B$ of some modeled point, and the actual pivot obeys $\Vert c-\hat{c}\Vert \le {ϵ}_c$. The triangle inequality givesThus a certified radius isThe one-sided geometric coverage assumption is sufficient; it does not require every modeled point to lie close to actual material. A conservative overfilled model is allowed.

For an original example, take $\hat{R}=0.500\mathrm{m}$, shape coverage error ${ϵ}_B=3\mathrm{mm}$ and pivot-location error ${ϵ}_c=2\mathrm{mm}$. Then $R_{\mathrm{cert}}=0.505\mathrm{m}$. A ten-degree rotation about the actual fixed pivot moves any actual point by at mostUsing the nominal radius gives only $87.16\mathrm{mm}$, missing about $0.872\mathrm{mm}$ of possible motion. The angular clearance bound for a rotating body translates that displacement allowance into a clearance bound. Geometry and rotation must be considered together in the continuous-path planning model.^[ref]

Pivot-location uncertainty in a rotational clearance bound is distinct from an uncertain body translation. If the chosen reference point also moves, its translation contributes separately to the occupied-point motion. A speed certificate becomes $v_{\max }+R_{\mathrm{cert}}{\omega }_{\max }$ when the stated translational and angular speed bounds are valid. Substituting a smaller radius about a different center without accounting for that center’s motion changes the problem.

If the geometry has an additional bounded scale factor $s\le 1+{ϵ}_s$ about the modeled pivot, a sufficient bound is $(1+{ϵ}_s)\hat{R}+{ϵ}_B+{ϵ}_c$, under the explicitly separated scale and residual-shape assumptions. With ${ϵ}_s=0.01$ in the example it becomes $0.510\mathrm{m}$. Unknown errors and repeated descriptions of the same geometric tolerance must not be combined as if they were independent extra effects.

A radius enlargement addresses the motion-rate bound. It does not by itself correct an inaccurate sampled distance between the nominal robot surface and an obstacle. That query still needs a suitable geometric allowance or a clearance certificate with bounded distance-query error. Likewise, hard enclosure tolerances are different from standard uncertainties; a root-sum-square of standard deviations is not automatically a guaranteed radius.

A proposed geometric check measures extreme points of the assembled robot, including attachments, relative to the same pivot used by the motion representation. Account for measurement error and verify coverage between sampled surface points using a geometric model or validated tolerance. Recompute the bound when the tool, pivot or assembly changes, and record the radius’s provenance alongside the trajectory certificate.