提出首个可验证的图上凸集采样规划方法,确保轨迹零误报。
Sampling-based Certified Planning with Graphs of Convex Sets
- 通过采样重叠与共享面,用无分辨率参数的间隙证书链持续验证路径
- 在14自由度双臂任务中实现0%错误率,优于参考方法的21次失败
- 适合对安全性和可靠性要求极高的机器人操作场景
基于凸集图的规划器生成的轨迹本应无碰撞,前提是凸区域本身无碰撞。然而区域生成仅以概率保证该性质,现有规划器均不验证。我们首次量化了这一差距:在缩放后的14自由度双臂库中,3.2%的接口采样点处于碰撞状态,导致搜索型GCS规划器(\gcsstar)产生62%的答案错误——29个抓取放置任务中有18个轨迹穿过货架,最深达91毫米,仍被报告为成功。修复库无效:十倍严格的标准、平方和认证区域及均匀裕度均在保证正确性前破坏了规划连通性。我们改而构建一个可验证答案的规划器:采样分解中的重叠与共享面,用可接纳的启发式界剪枝,并在每轮搜索中连续验证候选路径,通过一系列无分辨率参数的间隙证书球;失败时采用局部区域内绕行修复,并重新验证凸性。在全部29个任务上,该方法实现零无效答案,优于参考方法的21次错误;首次输出认证结果仅需0.11秒,远快于参考方法的1.59秒;对于参考解物理有效的任务,其精确复现最优解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。