PaperlayerView exact revision on arXiv

Source-linked AI summary

LARC: Lazy Adaptive Reachability Certification of Robot Manipulator Trajectories

Yu Feng, Hao Wu, Yuzhe Wang, Jianshu Zhou

arXiv:2608.29767v1cs.RO

TL;DR

Discrete checks can miss collisions between sampled robot states, while uniform reachability partitions waste work where clearance is large. LARC adaptively bisects only inconclusive intervals using Hermite-based capsule envelopes, matching a fixed-fine baseline with substantially fewer evaluations while retaining the shared model’s certification limitations.

  • Problem

    Discrete trajectory checks can miss collisions between sampled robot states, and uniform time partitions waste computation where clearance is large.

  • Method

    LARC adaptively refines inconclusive intervals using midpoint capsules inflated by exact componentwise Hermite speed maxima.

  • Results

    LARC matched all fixed-fine decisions on 160 PIPER trajectories while using 24.8% of baseline interval evaluations and achieving a median paired speedup of 10.28×.

  • Takeaways & Limitations

    Adaptive refinement reduces certification work while retaining the limitations of the shared geometric model.

  • Takeaways & Limitations

    The continuous-time guarantee depends on mesh containment, valid motion bounds, and a static obstacle model, while sampled-clear trajectories can remain uncertified.

Abstract

from arXiv · show

Discrete trajectory checks can miss collisions between sampled robot states. Reachability-based certification bounds motion between states, but uniform time partitions waste computation where clearance is large. We present lazy adaptive reachability certification (LARC), which checks a planned trajectory by bisecting only intervals with an inconclusive clearance test. For piecewise-cubic Hermite joint trajectories, the method bounds link occupancy using midpoint capsules inflated by exact componentwise speed maxima. Certified intervals covering the trajectory provide continuous-time external-obstacle clearance, subject to geometric containment, static obstacles, and a prescribed margin. On 160 AgileX PIPER trajectories from 80 start-goal pairs, LARC matched all decisions of the fixed-fine baseline at depth nine. It used 20328 interval evaluations (24.8% of baseline work), with a median paired speedup of 10.28x. A separate MoveIt/FCL audit checked 158051 states and detected collisions in 21 direct-interpolation controls, none of which LARC certified. The method reduced computation under a shared certificate model, but 27 of 139 sampled-clear trajectories remained uncertified. The sampled audit cannot independently prove continuous-time clearance.

I. INTRODUCTION

Waypoint checks can miss collisions involving upstream manipulator links, while uniform temporal subdivision wastes computation in already-clear regions. LARC addresses this by adaptively refining only inconclusive intervals and providing a clearance guarantee under stated assumptions.

  • Gripper clearance does not ensure that upstream robot links avoid surrounding objects during motion between waypoints.
  • Reachability methods enclose each link’s swept volume over time intervals, balancing enclosure tightness against certification cost.
  • LARC bisects inconclusive intervals until they pass or reach a prescribed depth, without changing the planned trajectory.
  • LARC uses capsule enclosures derived from exact componentwise Hermite speed maxima.
  • The method provides continuous-time external-obstacle clearance under stated containment, static-scene, and margin assumptions.
  • The evaluation compares fixed-resolution certifiers on 160 paired trajectories and includes a separate sampled MoveIt/FCL audit.

II. RELATED WORK

Trajectory certification differs from end-effector reachability because it requires enclosing every link’s swept occupancy. LARC applies deterministic analytic enclosures after planning while fixing trajectories, geometry, margin, and distance evaluation for comparison.

  • Reachability maps describe attainable end-effector poses, whereas trajectory certification additionally requires bounds on every link’s swept occupancy.
  • LARC examines interval allocation after planning using deterministic analytic enclosures rather than changing the planned trajectories.
  • The problem formulation represents each link’s geometry as V_l(q) and seeks an outer envelope containing its forward occupancy over an interval.
  • External obstacles are fixed axis-aligned bounding boxes, and experiments use a prescribed clearance margin of ρ = 10 mm.
  • Figure 1 depicts trajectory reconstruction, midpoint-capsule inflation, clearance testing, binary refinement, and the requirement that all terminal intervals pass.
  • An interval passes only when g(I; k) > 0, and a trajectory is certified when passing leaf intervals cover its full duration.

A. Hermite Trajectories and Speed Bounds

LARC reconstructs recorded joint trajectories as piecewise-cubic Hermite curves and computes exact speed bounds for the reconstructed polynomials. These bounds drive capsule inflation into interval occupancy envelopes.

  • MoveIt trajectories are reconstructed as piecewise-cubic Hermite curves from recorded joint positions and velocities.
  • For cubic joint trajectories, velocity is quadratic, so each component’s maximum absolute speed occurs at a clipped endpoint or an interior acceleration root.
  • The resulting speed bound is exact for the reconstructed polynomial, while tracking error and deviations from that polynomial are outside the model.
  • Eleven capsules fitted to official PIPER collision meshes are transformed to the interval midpoint and inflated using calibrated ancestor-joint motion bounds.
  • Inflating the midpoint capsule by the motion radius produces the interval occupancy envelope.
  • The implementation compares segment–AABB distance against capsule radius, motion inflation, and the single prescribed margin ρ.

C. Adaptive Certificate Tree

LARC recursively certifies a trajectory by testing the root interval and bisecting only intervals whose clearance remains inconclusive, stopping at positive clearance or depth nine. Its offline tree preserves a complete leaf cover without replanning or braking logic.

  • Adaptive recursion: At depth dmax = 9, an inconclusive leaf makes the trajectory UNCERTIFIED.Positive-clearance nodes become certified leaves; otherwise, nodes are bisected until the maximum depth.
  • Adaptive recursion: Algorithm 1 constructs a capsule enclosure and evaluates clearance before either recording a certified leaf or recursively splitting the interval.Both child branches must certify for the parent call to return TRUE.
  • Certificate scope: The tree traverses child branches before combining their results, retaining a complete leaf cover for every trajectory.The offline certifier neither replans the trajectory nor provides braking logic.

D. Fixed-Resolution Baselines

Fixed-resolution certification provides comparison points for adaptive temporal allocation, while the guarantee depends on enclosure and scene assumptions. Positive mesh clearance alone does not ensure eventual certification because capsule-enclosure error can remain.

  • Fixed-resolution baselines: Fixed-coarse evaluates 16 uniform intervals, whereas fixed-fine evaluates 512 intervals under the shared certificate model.LARC can reach the fixed-fine depth but stops refining intervals once they pass.
  • Certificate assumptions: The theorem requires capsule containment, static external obstacles, one fixed margin, and excludes continuous-time self-collision.Under these assumptions, positive clearance on covering leaf intervals implies external-obstacle clearance throughout the horizon.
  • Certificate limitations: Positive collision-mesh clearance alone does not guarantee eventual certification because the gap between the mesh and its enclosing capsule remains.The analysis does not provide a computable maximum refinement depth.

VI. SIMULATION STUDY

The simulation used an AgileX PIPER dataset with four scenes and paired planned and direct trajectories for 80 accepted start–goal pairs. Generation and Hermite recheck failures were retained in the records but excluded from certification rates.

  • Simulation protocol: The six-degree-of-freedom AgileX PIPER model was evaluated with MoveIt 2, OMPL RRTConnect planning, time parameterization, and piecewise-cubic Hermite reconstruction.Trajectories were checked on a 50 Hz grid before acceptance.
  • Dataset: Four scenes contained 20 independent start–goal pairs each, yielding 80 independent units.Each pair produced one OMPL-planned trajectory and one direct smoothstep control with matched endpoints and duration.
  • Dataset: The 115 generation attempts included 9 invalid starts, 16 invalid goals, 6 planning failures, and 4 Hermite recheck failures.Certification rates were computed from 160 trajectories associated with the 80 accepted pairs.

C. Sampled MoveIt/FCL Audit and Computational Timing

A separate MoveIt/FCL audit and repeated runtime measurements evaluated decision agreement, sampled collisions, and computational cost. LARC matched fixed-fine certification decisions while leaving some sampled-clear trajectories uncertified.

  • Sampled audit: 158051 states were checked on a 250 Hz grid plus original waypoints using MoveIt and FCL collision geometry.The audit defined sampled-clear, FCL-detected false-safe, and conservative rejection relative to sampled checks.
  • Computational timing: The reported paired speedup is the median of 160 within-trajectory fixed-fine-to-LARC runtime ratios.Three timing repeats per trajectory were summarized by their within-trajectory median; no significance tests were computed.
  • Decision agreement: LARC and fixed-fine each certified 112 trajectories, while fixed-coarse certified 70; LARC and fixed-fine agreed on all 160 decisions.This agreement is between certifiers, not independently known continuous-time collision status.
  • Sampled audit: 21 direct-control trajectories contained audited collisions, and none were certified by LARC.Among 139 sampled-clear trajectories, 27 remained uncertified, a conservative rejection rate of 19.4%.

B. Interval Work and Runtime

LARC substantially reduced interval evaluations and runtime relative to fixed-fine certification, with savings varying by scene. The largest gains occurred in the obstacle-free open scene, while obstacle scenes required more refinement.

  • 20328 interval evaluations were required by LARC versus 81920 for fixed-fine, a ratio of 0.248 and a 75.2% reduction.Marginal median runtimes were 81.8 ms for LARC and 801.4 ms for fixed-fine, with a median paired speedup of 10.28×.
  • Scene dependence: All 40 open-scene trajectories passed at the root, yielding an evaluation ratio of 0.002 and a median paired speedup of 260.31×.
  • Scene dependence: Obstacle scenes required evaluation ratios from 0.223 to 0.392, with median paired speedups from 3.14× for the medium window to 11.58× for the easy window.
  • The displayed Fig. 3 trajectory for each scene was selected as closest to that scene’s median adaptive evaluation count.The panels show capsule poses, the gripper-base path, world axes, and static AABBs; pose snapshots omit interval motion inflation.
  • Table III reports per-scene trajectory counts, audit-detected collisions, certifications, conservative rejections, evaluation ratios, and median paired speedups.

VIII. DISCUSSION

Adaptive refinement reduced computation without changing the shared geometric model, but certification remained limited by conservative geometry and other assumptions. The results therefore support cheaper certification rather than collision ground truth or universal certification of sampled-clear trajectories.

  • Stopping refinement when intervals passed reduced computation without changing the geometric model, isolating temporal allocation rather than occupancy representations or end-to-end planning.
  • The medium-window and easy-shelf speedups of 3.14× and 4.18× better represent the tested cluttered settings than the obstacle-free control.
  • 27 conservative rejections included sampled-clear trajectories that remained uncertified because of capsule fitting, ancestor-joint bounds, the 10 mm margin, or possible between-sample collisions.These effects were not separated, so the 19.4% rejection rate is not a true false-negative rate.
  • Fig. 4 compares all 160 trajectories using audit outcomes, LARC-to-fixed-fine evaluation ratios, and paired runtime ratios on a logarithmic axis.“Sampled clear” means no collision was detected by the audit, while “uncertified” means LARC did not obtain a certificate.
  • LARC matched all fixed-fine decisions using 24.8% of interval evaluations and a median paired speedup of 10.28×, but 27 of 139 sampled-clear trajectories remained uncertified.The conclusion retains the shared geometric-model limitations and calls for tighter enclosures and additional bounds for broader settings.
Loading 2608.29767v1…