Sampling-based Certified Planning with Graphs of Convex Sets

TL;DR: The "collision-free by construction" guarantee at the heart of Graphs of Convex Sets (GCS) motion planning is quietly probabilistic, and this paper measures what that costs for the first time: on a 14-DOF bimanual library, a 3.2% contamination of region interfaces gets amplified by the optimizer into a 62% answer failure rate — 18 of 29 pick-and-place queries drive arms through shelves, up to 91 mm deep, all reported as successes. The authors show the defect can't be fixed in the region library (every tightening strategy destroys graph connectivity first), then build a sampling-based planner that certifies each answer with a resolution-free chain of clearance balls. The certified planner produces zero invalid answers and is faster than the unverified baseline: first certified answer in 0.11 s vs 1.59 s.

The assumption nobody was checking

GCS planning, introduced by Marcucci et al. and now a whole family (GCS*, IxG*, GHOST, shortest walks, geodesic variants), works like this: pre-decompose the collision-free configuration space \mathcal{F} into a library of overlapping convex polytopes \mathcal{U} = \bigcup_i X_i, build a graph where regions are nodes and overlaps are edges, and solve shortest-path queries as convex programs. Any trajectory that stays inside \mathcal{U} is collision-free — provided the regions are actually inside \mathcal{F}.

That proviso is where the bodies are buried. The region generators used in practice (IRIS-NP, IRIS-ZO) can't prove a region is collision-free. They test it: draw M uniform samples inside a candidate polytope, and if all come back clean, accept. The math is a plain Bernoulli bound — acceptance certifies that the colliding volume fraction is at most \varepsilon with confidence 1-\delta, with shipped defaults \varepsilon = 1\%, \delta = 5\%. Zero contamination would require infinite samples. So every scaled GCS library ships with a residual: a thin sliver of \mathcal{U} \setminus \mathcal{F} that the acceptance test tolerates by design. As the authors put it: "The residual is not a breach of the contract; it is the contract."

The paper surveys how five representative GCS works handle this. The original motion planning paper devotes one sentence ("does not provide a rigorous certification, but … appears to be very reliable in practice"); the rest state guarantees relative to the mathematical program and consume the regions as given. None checks the returned trajectory.

Why the residual is exactly where paths go

The interesting part is not that the residual exists but why an optimizer reliably finds it. Three geometric facts conspire, and this is the paper's sharpest conceptual contribution.

First, the residual is structural, not an implementation bug. IRIS grows a region by adding separating hyperplanes ("cuts") at discovered collisions. Against a convex workspace obstacle, this is exact. But in configuration space, the C-obstacle O = \{q : B(q) \cap W \neq \emptyset\} — the preimage of a workspace obstacle under forward kinematics — is generically non-convex. A cut removes a half-space; the parts of O that curve back around the cut stay inside the region. Finitely many cuts cannot excise a non-convex set. Uniform samples then miss the thin lens-shaped remainder, and the statistical test accepts.

Second, high-dimensional geometry pushes the residual into the planner's way. Cuts are tangent at discovered collisions, so undiscovered slivers hug the polytope faces — the residual lives in the boundary shell. And in d dimensions, boundary shells hold most of the volume: shrinking a convex body by 5% leaves 0.95^d of it, so at d = 14 the outer 5% shell contains 1 - 0.95^{14} \approx 51\% of the volume. Region interfaces — the overlaps a trajectory must cross — are double boundary shells. That's how an interface measurement can read 3.2% contamination against a 1%-volume contract with no contradiction: the interfaces oversample exactly the geometry the test undersamples.

Third, the planner is an optimizer, and the paper compresses the consequence into a one-line proposition: if the modeled optimum m(\mathcal{U}) is strictly cheaper than the physical optimum m(\mathcal{U} \cap \mathcal{F}), then every optimizer of the modeled problem is physically invalid — any path attaining the cheaper cost must leave \mathcal{F}. Shortest paths hug obstacles; the residual hugs obstacles; wherever the residual offers a shortcut, the optimum moves there deterministically. This isn't bad luck — it's adversarial selection of the model error by the objective.

The dimension dependence is measured cleanly on a planar k-link arm with everything fixed except k: interface contamination reads exactly zero through k = 5, yet task-style answers already collide from k = 3 on, and contamination reaches 13% at k = 14. The volume statistic is blind to the failure mode long after answers have gone bad.

The failure, measured

On the scaled 14-DOF bimanual library (219 regions, 903 filtered collision pairs, default generator settings), feeding the library to GCS* yields: 18 of 29 connected pick-and-place queries return colliding trajectories, with 39.4 mm median penetration, 91.3 mm worst-case, and one path spending 51% of its length in collision — all reported as successes. The result reproduces across machines and across four fresh library regenerations (colliding on 83–84% of connected grasp pairs). Notably, every violation is a contiguous mid-path interval with both endpoints clear by ≥38 mm: the grasps are fine; it's the path between them that enters the shelving.

Why you can't fix the library

The obvious objection — just tighten the generator — is where the paper does its most valuable dirty work, running three remedies to completion (Sec. V-D):

Stricter acceptance (\varepsilon = 0.1\%, \delta = 1\%, 4× particles, 10× iterations, no admitting unfinished regions): only 47 of 222 seeds survive, just 3 of 22 shelf-adjacent grasp seeds among them, and the survivors are pairwise disjoint — zero interfaces versus 2,757 in the default library. The graph evaporates. The authors note they had predicted the opposite.

Sums-of-squares certification (C-IRIS): the certificate is real — zero contamination on ~4,000 samples — but at 17× generation cost, the certified regions cover 33% of free space versus 83% for the statistical generator, fragment into seven connected components even at 2.7× the seed budget, and answer none of 30 queries. And this is on a 2-DOF testbed; SOS costs minutes-to-hours per region at 7–12 DOF.

Uniform margins: eroding regions by up to 0.10 rad drops contamination only from 3.39% to 2.11% while connected queries fall from 16/16 to 10/16. The residual hides in overlap volumes deeper than any margin connectivity survives.

The unifying reason: certainty about a d-dimensional volume must be paid wherever the volume meets obstacles — which is exactly where regions must also meet each other. Soundness and connectivity compete for the same real estate, and soundness loses first.

The fix: certify the answer, not the model

The constructive move is to accept the contaminated library as-is and relocate the guarantee from the regions to the delivered trajectory. Three components make this work, and the design is tight enough to sketch from scratch.

Interface sampling. Inside one convex region, the optimal path is a straight segment. So a shortest path through regions X_{v_1}, \dots, X_{v_k} is piecewise linear with vertices on the interfaces X_{v_i} \cap X_{v_{i+1}}. The interfaces hold every free variable of the problem — sampling them discretizes the decision itself, not the space around it. Each sample is a concrete configuration you can test against the true collision checker before it enters the roadmap; the optimum of a convex program offers no such handle. Interfaces of dimension below d-1 (edge and corner contacts) are rejected outright, since they encode zero-clearance passages the model considers legal. Chebyshev-center samples — maximally cleared crossings — anchor the benchmark.

Informed anytime search. Rounds of sample-search-verify, with the incumbent cost c pruning interfaces via the admissible bound \ell(F) = \min_{x \in F} \|x - q_s\| + \|x - q_g\|: any interface with \ell(F) > c lies outside Gammell-style informed ellipse and can't be on an improving path, so discarding it is lossless. Sample budgets double per round on the survivors. Crucially, only certified costs tighten the ellipse — an unverified short path would prune illegally.

Continuous clearance certificates. The clearance function \phi(q) (minimum distance over all body pairs) is L-Lipschitz with L = \sqrt{\sum_i r_i^2}, where r_i is the reach distal of joint i — measured L \approx 3.4, implemented conservatively as 6.0, against an empirically probed worst-case rate of 1.01. Then one distance query at q certifies the entire ball B(q, \phi(q)/L). To verify a segment: query \phi, advance by \phi/L, repeat. The balls overlap by construction, so their union covers the continuum — no resolution parameter, no sliver between test points for the residual to hide in. Strides self-adapt: long where clearance is large, short near obstacles. Verifying a 14-DOF candidate costs ~200 clearance queries at 2.3 ms each.

When verification fails on a segment (a,b), convexity becomes the repair kit: both endpoints lie in the same region X, so any via point z \in X yields a detour (a,z),(z,b) that stays in X and needs no new corridor. Since the residual is thin, a legal detour usually exists centimeters away. The paper's contrast with convex-program pipelines is worth internalizing: given a discovered colliding configuration q^*, re-solving returns the same invalid optimum (by the proposition above), adding an excluding cut just replays the generator's failure online, and deleting the region blacklists a corridor for a sliver. A sampled candidate is piecewise and the planner owns its waypoints — feedback lands surgically at the failure site.

Finally, a corridor SOCP polish removes sampling slack (+41.5% raw → +9.6% polished over the corridor optimum), and — since the polish optimizes the flawed model and its waypoints drift back toward the residual — the polished path goes through verification again.

The evidence

Head-to-head on all 29 connected task queries, same machine, same library, both planners' outputs judged by the same continuous certificate plus 2,000 boolean probes:

Three results stand out beyond the headline:

Certification is a speedup, not a tax. First certified answer in 0.11 s median versus 1.59 s for the reference's unverified one — 14× faster. The mechanism: center crossings maximize clearance, so the first candidate's certificate balls are the largest available and verification settles quickly. Eager roadmap validation would cost 2–3 orders of magnitude more; the lazy scheme checks one path per search round, and it usually passes because its waypoints were pre-validated.

Exact agreement where the reference is right. On all eight queries whose reference answer is physically valid, the certified cost matches to four decimal places. The layer adds soundness without sacrificing optimality within the corridor. Rescued queries pay a median +9.2% (range +5.1 to +50%) — the price of a legal detour around an obstacle the reference passes through.

Versus classical sampling. RRT-Connect with the same checker solves every pair raw, but only 45% of shortcut-smoothed runs survive the continuous certificate, first certified answer takes 10.7 s median, and on three shelf-interior pairs it certifies zero of thirty runs while this planner delivers. Where both certify, costs agree within 1.4% — the decomposition concedes almost nothing in quality while answering deterministically, two orders of magnitude faster.

What changes, and what to be skeptical about

If this holds, the practical upshot is blunt: any deployed GCS pipeline built on statistical region generation is returning some fraction of silently colliding trajectories, and that fraction grows with DOF even while the generator's own volume statistics read clean. The 7-vs-14-DOF split matters — hand-curated 7-DOF demos live at 0.3% contamination, the regime the family's published results inhabit, while scaled 14-DOF libraries with random seeds and iteration caps sit at ~3%. The paper's answer-level protocol (certify the delivered path, not the model) seems likely to become standard practice, and the certificate-ball verifier is cheap and drop-in enough to adopt independently of the rest of the planner.

Caveats worth holding onto. The core evidence is one 14-DOF task library and 29 queries (plus regenerations reaching 46–56 pairs, a curated 7-DOF library, a 2-DOF C-IRIS testbed, and an aerial benchmark mentioned in passing) — the amplification law from Fig. 3 is compelling but rests on a planar k-link family plus one real system. The 3.2% figure reflects default generator settings with an iteration cap that admits regions with the acceptance test unfinished; a deployment that tunes the generator per-scene may sit elsewhere on the curve, though Sec. V-D suggests the tuning headroom before connectivity collapses is small. The cost-optimality guarantee is modest — the lower bound is just joint-space distance, giving a median gap of 7.1% — and 14 of 29 queries end in refusal, which is honest but means roughly half the task set gets no answer from this planner either (though 13 of those 14 reference answers were themselves invalid). The Lipschitz constant is derived from a rigid kinematic model; payloads are handled by lengthening reaches, but deformables or contact-rich tasks are out of scope.

Where to spend your reading time: Section III is the gem — the non-convexity argument, the boundary-concentration arithmetic, and Proposition 1 together form a clean, general lesson about optimizers and model error that extends well beyond GCS: an optimizer is a search procedure for the flaws in your feasibility model. Section V-D (the failed remedies) is the most decision-relevant for practitioners, since "just tighten the generator" is everyone's first instinct and the paper kills it with data.