Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel sampling-based planner that certifies its outputs while operating on graphs of convex sets, addressing the significant gap in collision-free trajectory generation due to probabilistic guarantees from region generators. In experiments with a 14-DOF bimanual library, the proposed planner achieved zero invalid trajectories across 29 pick-and-place queries, contrasting sharply with a search-based GCS planner that produced a 62% error rate. The method not only improves safety and reliability but also enhances efficiency, with certified answers generated in 0.11 seconds compared to 1.59 seconds for the reference planner.
A new planner achieves zero invalid trajectories in complex bimanual tasks, revealing a staggering 62% error rate in traditional methods.
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.