PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling-based Certified Planning with Graphs of Convex Sets

Peng Xie, Amr Alanwar

arXiv:2608.29770v1cs.RO

TL;DR

GCS planners assume their generated convex regions are collision-free, although generators provide only probabilistic guarantees and planners do not verify returned trajectories. This paper measures the resulting answer-level failures and introduces sampling-based continuous certification with repair and re-verification. Across 29 queries, the planner returns zero invalid answers, reaches a certified answer faster, and exactly matches valid reference optima.

  • Problem

    GCS planners rely on probabilistically generated collision-free regions without verifying whether returned trajectories are physically collision-free.

  • Method

    The planner samples region interfaces, prunes candidates with an informed bound, continuously certifies paths using clearance balls, repairs failures within convex regions, and re-verifies the polished result.

  • Results

    Across 29 task queries, the planner delivers zero invalid answers versus 21 for the reference and exactly reproduces the reference optimum whenever that answer is physically valid.

  • Takeaways & Limitations

    The approach moves the guarantee from the library to the returned answer, providing certified detours or explicit refusals instead of silent violations.

Abstract

from arXiv · show

Planners on graphs of convex sets return trajectories that are collision-free by construction, provided the convex regions are collision-free. The region generator only promises that property probabilistically, and no planner in the family verifies it. We report the first measurement of what the gap costs. On a scaled 14-DOF bimanual library, $3.2\%$ of interface samples are in collision, and a search-based GCS planner (\gcsstar) turns that volume error into a $62\%$ answer error: $18$ of $29$ pick-and-place queries return trajectories that drive the arms through the shelves, up to $91$\,mm deep, reported as successes. Repairing the library does not work; a ten times stricter acceptance contract, sums-of-squares certified regions, and uniform margins each destroy the connectivity planning needs before they deliver soundness. We instead build a planner that certifies its answers. It samples the overlaps and shared faces of the decomposition, prunes with an admissible informed bound, and verifies the one candidate each search round proposes, continuously, by a chain of clearance certificate balls with no resolution parameter; failures are repaired with local in-region detours, and the convex polish is re-verified. Head-to-head on all $29$ task queries it delivers zero invalid answers against $21$ for the reference, reaches its first certified answer in $0.11$\,s against $1.59$\,s for the reference's unverified one, and reproduces the reference optimum exactly on every query whose reference answer is physically valid.

I. INTRODUCTION

The paper measures how probabilistically unsound convex-region libraries corrupt GCS planning and introduces a sampling-based planner that certifies returned trajectories. On the benchmark, the new planner avoids invalid answers while preserving valid reference optima.

  • GCS planners inherit the assumption that every library region is collision-free, but existing planners do not re-check their returned trajectories.
  • 3.2% of overlap samples are in collision, while GCS∗ reports success on 18 of 29 pick-and-place queries whose trajectories penetrate shelves.The reported penetrations reach 39 mm at the median and 91 mm at the worst.
  • Shortest-path optimization concentrates trajectories near obstacles, where sampling-based generators leave residual collision volume and grasp endpoints create cramped geometry.
  • Stricter acceptance contracts, sums-of-squares certificates, and uniform margins dissolve the region graph before delivering soundness.
  • The proposed planner samples interfaces, prunes with an informed bound, continuously verifies candidate paths using clearance balls, repairs failed segments in-region, and re-verifies the polished path.
  • The planner delivers zero invalid answers across 29 queries and exactly reproduces the reference optimum whenever the reference answer is physically valid.Its first certified answer arrives in a fourteenth of the time required by the reference for an unverified answer.

II. RELATED WORK

The related work spans GCS planners, region generators, and collision-checking certificates. The paper distinguishes prior certificates for programs or regions from its answer-level certification approach.

  • GCS research includes shortest-path formulations, search-based descendants, multi-query bounds, travelling-salesman variants, compression, geodesic generalization, safe boxes, and optimized covers.
  • These planners share the assumption that consumed regions are collision-free, and none checks the returned trajectory against collision geometry.
  • IRIS separates regions from obstacles with hyperplanes, but this is not exact for non-convex configuration-space obstacle preimages.
  • Statistical generators scale to 7- and 14-DOF libraries in minutes, whereas sums-of-squares proofs cost minutes to hours per region at 7–12 DOF.
  • The paper combines clearance-ball certificates and lazy validation with convex decomposition structure, using overlaps to identify crossings and convexity to repair failed segments.
  • Existing certificates describe programs or regions; this planner instead certifies the answer with an ε-gap on cost and continuous path clearance.

III. PROBLEM STATEMENT

This section formalizes why probabilistically accepted convex-region libraries can differ from physical free space, and why the discrepancy becomes operationally important for optimized trajectories. It motivates certified answers as the required response to this gap.

  • Finite cuts cannot generally exclude non-convex configuration-space obstacles, leaving a thin residual inside accepted convex regions.
  • M = ∞ is required for a zero-ε acceptance contract; finite uniform testing therefore tolerates residual colliding volume.
  • At d = 14, a 5% boundary shell contains approximately 51% of a convex body, concentrating tolerated residual near interfaces despite a bounded volume statistic.
  • If the modeled optimum is shorter than the physically free optimum, every optimizer of the modeled problem is physically invalid.
  • Interface contamination grows with dimension while volume statistics remain quiet: contamination is zero through k=5 and 13% at k=14, while task answers collide from k=3.
  • The planner should return either a path proved collision-free over the continuum or an explicit report that no such path was found.

IV. METHOD: SAMPLING AND CERTIFICATION

The method combines interface sampling, informed iteration toward better paths, and a certification layer that proves every delivered answer.

  • The planner samples decomposition interfaces, iteratively improves paths with informed search, and certifies every returned answer.

A. Interface sampling and roadmap

The roadmap samples the interfaces that constrain region-to-region motion, while exploiting convexity for connectivity and local repair. It excludes lower-dimensional contacts that can create physically unusable transitions.

  • Interface sampling and roadmap: A minimum-length path through a sequence of convex regions is piecewise linear, with vertices on the interfaces crossed between regions.
  • Interface sampling and roadmap: Volume overlaps allow crossings anywhere in a d-dimensional shared body, whereas shared faces constrain crossings to a (d −1)-dimensional facet.
  • Interface sampling and roadmap: Lower-dimensional contacts are rejected because a roadmap transition through a point wedged between obstacles may be legal in the model but physically unexecutable.
  • Interface sampling and roadmap: The planner detects each interface’s affine hull and intrinsic dimension, then samples in hull coordinates using center, area, contour, or inward-contour strategies.
  • Interface sampling and roadmap: Roadmap nodes retain their generating regions, and nodes sharing a region are connected with Euclidean edge costs.

B. Informed iteration

The planner searches in rounds: it obtains an incumbent, discards interfaces that cannot improve it using an admissible bound, resamples survivors more densely, and verifies candidates during search.

  • Informed iteration: Round one samples every interface, builds a roadmap with query endpoints, and searches for the first incumbent path.
  • Informed iteration: An interface whose admissible lower bound exceeds the incumbent length lies outside the informed ellipse and can be discarded without losing improving paths.
  • Informed iteration: Surviving interfaces receive increased sampling in later rounds, while the incumbent improves monotonically and the search volume shrinks.
  • Informed iteration: Disabling informed pruning changes no answer but multiplies total planning time by 2.2, making the filter a speed improvement.
  • Informed iteration: Verification is interleaved with search: local detours repair dirty segments, unrepairable edges are blacklisted, and only certified costs drive pruning.

C. Continuous clearance certificate

The planner certifies continuous collision freedom using clearance queries and a Lipschitz bound, chaining adaptive balls along each candidate segment without a resolution parameter.

  • Algorithm 1 applies VERIFYREPAIR to every candidate proposed by the search, using the certificate machinery for answer validation.
  • A clearance query returns ϕ(q), the minimum distance over all 903 filtered body pairs using the same geometry as the boolean checker.
  • The implementation uses L = 6.0 after model-based reach bounds give L ≈3.4, with directional probes measuring a worst-case rate of 1.01.
  • If ϕ(q) > 0 and ϕ is L-Lipschitz, the ball B(q, ϕ(q)/L) is collision-free.
  • Chaining overlapping certificate balls from a to b certifies the entire segment, advancing farther in high clearance and shorter near obstacles.

D. In-region repair

When verification finds a dirty segment, the planner repairs it inside the shared convex region, then re-verifies the modified path and its convex polish.

  • A dirty stretch can be detoured through a via point z in the shared convex region without adding region transitions.
  • Candidate via points are sampled around the dirty stretch, collision-checked, and spliced in when their two resulting segments certify.
  • Convex optimization cannot directly repair a discovered collision: re-solving may reproduce the same invalid optimum, while excluding it changes the generator’s problem.
  • Sampled candidates give the planner ownership of waypoints and edges, so failures become local detours or blacklisted edges followed by millisecond re-search.
  • Raw sampled paths are +41.5% over the corridor optimum, while polished paths are +9.6%; polishing therefore returns through VERIFYREPAIR.

F. Output guarantees

The planner reports deterministic clearance and bounded-cost guarantees, while implementation and benchmark conditions define the scope of the evaluation.

  • The clearance certificate covers the continuum, guaranteeing that the delivered trajectory is collision-free along its entire length.
  • Over fifteen certified benchmark answers, the cost gap γ has median 7.1%, five are within 2%, and one attains its lower bound exactly.
  • Any lower bound LB ≤ m(U) also bounds the feasible collision-free problem, yielding ℓ ≤ (1+γ)m(U ∩ F).
  • Residual contamination widens γ but cannot falsify it, unlike an unvalidated geometric cost assigned to a potentially non-executable trajectory.
  • The benchmark uses 29 task-query pairs, a 60 s reference timeout, and one 32-thread CPU node without a GPU.

B. Interface contamination

Interface contamination grows with scaled, randomly seeded libraries and can become answer-level failure; stricter generation remedies trade soundness against the connectivity needed for planning.

  • 64 of 2,000 scaled-library interface samples collide, producing 3.2% contamination at default settings; the rate varies with regeneration and dimension.
  • 18 of 29 connected queries return colliding reference answers, with median penetration 39.4 mm, deepest penetration 91.3 mm, and one path 51% colliding.
  • A ten-times stricter acceptance contract leaves zero interfaces against 2,757 in the default library, so the surviving regions are pairwise disjoint.
  • Sums-of-squares certification achieves zero contamination on 3,995 samples but costs 17× more, covers 33% rather than 83% of free space, and fragments connectivity.
  • Uniform margins reduce contamination from 3.39% to 2.11% while connected queries fall from 16 to 10 of 16, never reaching soundness.
  • Surgical residual excision also maims the graph while failing to finish, so all four library-level fixes fail before achieving soundness.

E. Comparison on the scaled library

On the scaled library, the certified planner eliminates invalid answers while retaining reference-optimal costs where those answers are physically valid. It also reaches certified answers faster than both the reference planner and the sampling-based comparison.

  • Correctness: 21 reference trajectories fail certification, whereas the proposed planner returns 15 certified paths and 14 explicit refusals with no invalid answer.Every refused pair’s reference answer also fails certification.
  • Speed: 0.11 s is the proposed planner’s median time to its first certified answer, versus 1.59 s for the reference’s unverified answer.Center crossings maximize clearance, making verification settle in about 200 clearance queries.
  • Optimality: On all eight physically valid reference-answer pairs, the certified cost equals the reference cost to four decimal places.Rescued pairs incur a median +9.2% cost, ranging from +5.1 to +50%.
  • Comparison with sampling-based planning: RRT-Connect solves every pair in raw form, but only 45% of shortcut-smoothed runs survive the continuous certificate.Its first certified answer arrives in 10.7 s median, compared with 0.11 s for the proposed layer.
  • Curated library: On the curated 7-DOF library, the first certified incumbent arrives in 0.13 s, 21× before the search baseline’s best answer.Corridor polish reduces the sampling slack from +5.7% to +1.3%.
Loading 2608.29770v1…