On the Surprising Robustness of Sequential Convex Optimization for Contact-Implicit Motion Planning
作者: Yulin Li, Haoyu Han, Shucheng Kang, Jun Ma, Heng Yang
分类: math.OC, cs.RO
发布日期: 2025-02-03 (更新: 2025-04-26)
💡 一句话要点
提出CRISP算法，通过序列凸优化实现鲁棒的隐式接触运动规划
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 隐式接触运动规划 序列凸优化 机器人运动规划 鲁棒优化 互补约束
📋 核心要点
- 隐式接触运动规划能在线发现新接触模式，但其互补约束导致传统求解器难以收敛。
- CRISP算法仅关注原始问题，通过序列凸规划和自适应信赖域半径实现鲁棒求解。
- 实验表明CRISP在隐式接触规划中表现出惊人的鲁棒性，甚至能用全零初始化求解。
📝 摘要（中文）
本文提出了一种鲁棒的隐式接触运动规划方法，称为CRISP，它使用序列凸规划来解决问题。隐式接触运动规划将接触序列嵌入为隐式互补约束，有望利用连续优化在线发现新的接触模式。然而，由此产生的优化问题属于具有互补约束的数学规划，不满足经典约束条件，这对于常用数值求解器的收敛至关重要。CRISP是一种求解器，它不依赖于通常的原始-对偶算法框架，而只关注原始问题。CRISP在每次迭代中求解一个具有自适应信赖域半径的凸二次规划，并通过使用加权惩罚的优点函数来评估其收敛性。我们（i）提供了CRISP收敛到优点函数一阶平稳点的充分条件；（ii）发布了CRISP的高性能C++实现，具有通用的非线性规划接口；（iii）证明了CRISP在用朴素初始化解决隐式接触规划方面的惊人鲁棒性。事实上，CRISP可以用全零初始化解决几个隐式接触问题。
🔬 方法详解
问题定义：论文旨在解决隐式接触运动规划中的鲁棒性问题。传统的隐式接触运动规划方法，由于其互补约束的特性，导致优化问题不满足约束条件，使得常用的数值求解器难以收敛，从而限制了其在实际机器人控制中的应用。现有方法通常依赖于复杂的初始化策略或对问题进行简化，难以保证求解的稳定性和效率。
核心思路：CRISP算法的核心思路是放弃传统的原始-对偶算法框架，转而仅关注原始问题，并通过序列凸规划来逼近非凸的隐式接触运动规划问题。通过在每次迭代中求解一个凸二次规划，并使用自适应信赖域半径来控制迭代步长，从而保证算法的收敛性和鲁棒性。
技术框架：CRISP算法的整体框架是一个迭代优化过程。在每次迭代中，算法首先根据当前状态构建一个凸二次规划问题，然后使用现成的凸优化求解器求解该问题。接着，算法根据求解结果更新状态，并调整信赖域半径。最后，算法使用一个加权惩罚的优点函数来评估收敛性，并决定是否继续迭代。该框架包含以下主要模块：凸二次规划问题构建、凸优化求解、状态更新、信赖域半径调整和收敛性评估。
关键创新：CRISP算法的关键创新在于其对原始问题的关注和序列凸规划的使用。与传统的原始-对偶算法相比，CRISP避免了对偶变量的引入，从而简化了优化问题，并提高了算法的鲁棒性。序列凸规划的使用使得算法能够逐步逼近非凸的隐式接触运动规划问题，从而保证了算法的收敛性。
关键设计：CRISP算法的关键设计包括自适应信赖域半径的调整策略和加权惩罚的优点函数。自适应信赖域半径的调整策略能够根据迭代的进展情况动态调整信赖域的大小，从而保证算法的收敛速度和稳定性。加权惩罚的优点函数能够综合考虑目标函数和约束违反程度，从而有效地评估算法的收敛性。
🖼️ 关键图片
📊 实验亮点
实验结果表明，CRISP算法在解决隐式接触运动规划问题时表现出惊人的鲁棒性。在一些测试案例中，CRISP算法甚至可以使用全零初始化成功求解，而传统的求解器则难以收敛。此外，该论文还发布了CRISP算法的高性能C++实现，为其他研究者提供了便利。
🎯 应用场景
该研究成果可应用于各种机器人运动规划任务，尤其是在复杂地形或存在不确定接触的场景下。例如，它可以用于人形机器人的行走、四足机器人的攀爬、以及机械臂的操作等。该方法能够提高机器人在这些场景下的运动规划能力，使其能够更加安全、高效地完成任务，具有重要的实际应用价值和潜在的未来影响。
📄 摘要（原文）
Contact-implicit motion planning-embedding contact sequencing as implicit complementarity constraints-holds the promise of leveraging continuous optimization to discover new contact patterns online. Nevertheless, the resulting optimization, being an instance of Mathematical Programming with Complementary Constraints, fails the classical constraint qualifications that are crucial for the convergence of popular numerical solvers. We present robust contact-implicit motion planning with sequential convex programming (CRISP), a solver that departs from the usual primal-dual algorithmic framework but instead only focuses on the primal problem. CRISP solves a convex quadratic program with an adaptive trust region radius at each iteration, and its convergence is evaluated by a merit function using weighted penalty. We (i) provide sufficient conditions on CRISP's convergence to first-order stationary points of the merit function; (ii) release a high-performance C++ implementation of CRISP with a generic nonlinear programming interface; and (iii) demonstrate CRISP's surprising robustness in solving contact-implicit planning with naive initialization. In fact, CRISP solves several contact-implicit problems with all-zero initialization.