用稀疏半定规划求解高阶接触运动规划，秒级出解且接近全局最优
Global Contact-Rich Planning with Sparsity-Rich Semidefinite Relaxations
- 将接触运动规划转化为多项式优化，挖掘结构与接触模式的稀疏性
- 在多个仿真与真实场景中实现秒级求解，子最优性可认证且极小
- 开源工具箱自动处理稀疏性，适用于机器人及其他领域
我们发现，从多项式优化（POP）视角看，接触丰富的运动规划同样具有稀疏性。除了通用的关联与项稀疏性外，还可利用机器人运动学结构及接触模式的可分性带来的特殊稀疏模式。这种稀疏性支持设计高阶但稀疏的半定规划（SDP）松弛——基于Lasserre的矩与平方和层次——可被现成的SDP求解器在秒级内求解，并对非凸接触丰富规划问题计算出近似全局最优解，且子最优性可认证。在仿真（Push Bot、Push Box、带障碍物的Push Box、Planar Hand）与真实世界（Push T）中广泛实验验证了该方法生成全局接触丰富运动规划的强大能力。作为独立贡献，我们发布了稀疏多项式优化工具箱SPOT——采用C++实现，提供Python与Matlab接口——可自动化处理机器人等领域的稀疏性。
原文摘要 · Abstract (English)
We show that contact-rich motion planning is also sparsity-rich when viewed as polynomial optimization (POP). We can exploit not only the correlative and term sparsity patterns that are general to all POPs, but also specialized sparsity patterns from the robot kinematic structure and the separability of contact modes. Such sparsity enables the design of high-order but sparse semidefinite programming (SDPs) relaxations--building upon Lasserre's moment and sums of squares hierarchy--that (i) can be solved in seconds by off-the-shelf SDP solvers, and (ii) compute near globally optimal solutions to the nonconvex contact-rich planning problems with small certified suboptimality. Through extensive experiments both in simulation (Push Bot, Push Box, Push Box with Obstacles, and Planar Hand) and real world (Push T), we demonstrate the power of using convex SDP relaxations to generate global contact-rich motion plans. As a contribution of independent interest, we release the Sparse Polynomial Optimization Toolbox (SPOT)--implemented in C++ with interfaces to both Python and Matlab--that automates sparsity exploitation for robotics and beyond.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。