CS Paper Radar

ContactIPM: A Structure-Exploiting Interior-Point Solver for Contact-Implicit Trajectory Optimization

Yucheng Chen

cs.RO ·submitted 2026-08-12 07:11 UTC · v1
benchmark

Abstract

Contact-implicit trajectory optimization avoids prescribing contact sequences, but yields mathematical programs with complementarity constraints (MPCCs) whose degeneracy challenges conventional primal--dual solvers. Existing contact-specific methods improve robustness to this degeneracy but do not leverage a stagewise optimal-control factorization and primal--dual consistency, while structure-exploiting optimal-control solvers are not designed for complementarity constraints. We show that these capabilities can be combined in a single primal--dual method. ContactIPM identifies complementary inequality pairs, embeds them through a barrier-coupled elastic interior relaxation, eliminates slack and dual variables stagewise, and solves the reduced Newton system using a Riccati recursion. A fixed multi-phase MPCC recovery schedule provides four continuation and restart attempts from naive initializations, while termination is gated by the unrelaxed physical complementarity residual. We compare ContactIPM with two contact-specific MPCC solvers, CRISP and IMPACT, using matched benchmark conditions and common post-solve acceptance criteria. On four fixed CRISP benchmark cases, ContactIPM is $2.17$--$8.87\times$ faster over 20 paired timing repetitions per case and achieves higher success on the Push Box and Push-T robustness suites. Against IMPACT, ContactIPM is \(2.96\times\) faster on Push T and \(4.91\times\) faster on Cart Transport, but \(4.46\times\) slower on Push Box. In 50 closed-loop Push Box rollouts spanning model mismatch, measurement noise, initial-pose errors, and state resets,

Closest papers

Nearest neighbours by meaning across the whole index.

HALO-LP: A Homogeneous All-Shifted Non-Interior-Point Method for Linear Programming

cs.RO ·2026-10-31 ·Jose Rojas, Ana Aguilar, Eusebio Bugarin
similarity 0.64
Abstract

This letter introduces HALO-LP, a novel homogeneous all-shifted non-interior-point method for linear programming (LP). The proposed method combines a homogeneous self-dual (HSD) embedding with all-shifted nonlinear complementarity (NCP) functions and proximal primal-dual regularization, enabling arbitrary primal-dual warm starts without requiring strictly interior iterates. The resulting Newton equations admit a condensation based on a positive-definite matrix that can be efficiently factorized using Cholesky decomposition, while the HSD embedding enables primal and dual infeasibility detection through Farkas certificates. Numerical evaluations on perturbed LP instances derived from the Netlib test set demonstrate state-of-the-art warm-starting performance, outperforming the competing solvers in the evaluated setting. We further validate optimality and infeasibility detection on analytically characterized LP problems. Finally, we demonstrate HALO-LP's applicability to robotic optimal control through sequential linear programming (SLP) for centroidal walking and trotting of quadrupedal robots.

0.30

A Tutorial on Complementarity-Based Contact Models for Robotics

cs.RO cs.GRmath.OC ·2026-11-19 ·Onur Beker, A. René Geist, Michael Posa, Marc Toussaint, Justin Carpentier +1 more
similarity 0.64
Abstract · 32 pages, 9 figures, 3 tables, 14 algorithms

Simulating rigid-body dynamics with contact is fundamental to robotics, from motion synthesis and control to mechanism design. Many widely used simulators rely on cone complementarity formulations, whose physical assumptions and numerical solution require substantial background. While excellent surveys, monographs, and course notes exist, they mostly address computational mechanics or computer graphics or document a single simulator. To the best of our knowledge, a self-contained pedagogical treatment for robotics, bringing these formulations and their solvers together with complete derivations and a unified notation, does not yet exist. This tutorial addresses this gap by connecting rigid-body dynamics, conic optimization, and frictional contact. In particular, we explain how complementarity conditions encode non-penetration and frictional dissipation, determining separation, sticking, and sliding without prescribed contact modes. We distinguish equivalent transcriptions from convex relaxations, showing how the latter can introduce artifacts such as lift-off and creep. We examine the existence and uniqueness of motion and contact forces, including the solver's role in selecting among multiple solutions. We then compare first-order and Newton-based methods, explain regularization and proximal strategies, and discuss trade-offs between computational cost, robustness, and physical fidelity. Connections to widely used simulators, optimal control, and differentiable simulation help readers interpret simulation results, choose suitable formulations and solvers, and develop their own contact dynamics routines.

0.23

Joint Structure Identification and Newton Acceleration via Proximal Line Search for Nonconvex Optimization

eess.SP ·2026-09-16 ·Yiming Zhou, Wei Dai
theory similarity 0.62
Abstract

We consider composite optimization with a smooth, possibly nonconvex function and a separable convex polyhedral term. Such problems have a simple nonsmooth structure but arise widely in applications. Existing Newton-type methods may fail to identify nonsmooth coordinates during direction computation, move coordinates away from those reached by the full step during line search, or rely on separate first-order steps for identification. In this work, we propose a unified inexact proximal Newton method that couples structure identification with second-order acceleration through a proximal line search designed to retain the nonsmooth structure revealed at the local model. In particular, on a predicted working set, we solve a quadratic model inexactly but enforce its constraints exactly, allowing coordinates to reach new kinks without leaving the selected affine intervals. This set also includes small-margin kink coordinates to exploit the Hessian coupling effect. To globalize the direction, we construct a proximal line search using an isotropic proximal model whose linear term is chosen so that the initial trial exactly recovers the full step. Backtracking increases the proximal curvature until sufficient decrease holds, allowing coordinates to remain at kinks reached by the full step while damping other components. Generating each trial point requires only proximal operator evaluations. We prove finite backtracking and finite active-set identification under strict complementarity and a non-singular reduced Hessian, together with local Q-superlinear convergence under a directional Dennis-More condition and vanishing relative inexactness. Numerical results verify the effectiveness of the proposed method.

0.12

Online iLQR-MPC with Whole-Body Control for Robust Humanoid Locomotion

cs.RO ·2026-11-03 ·Xiang Li, Linlin Ou, Ruihan Wu, Xinyi Yu
similarity 0.61
Abstract

Humanoid locomotion requires deciding where to step and how to distribute contact forces. However, a disturbance can invalidate the nominal plan, requiring coordinated revision under constraints that switch with every footfall. To solve this online, the proposed approach employs the single-rigid-body model, which retains attitude dynamics and the full contact wrench. An iterative linear-quadratic-regulator MPC (iLQR-MPC) then jointly optimizes contact forces and footstep locations in a single receding-horizon problem, without a separate step planner. Specifically, contact and motion constraints are incorporated into the backward pass through augmented-Lagrangian and relaxed-barrier penalties. A whole-body controller subsequently maps the plan to joint torques at 500 Hz while preserving contact feasibility. The model-based formulation makes disturbance responses interpretable through explicit costs and constraints, and requires no platform-specific policy training. In MuJoCo simulations, the iLQR-MPC replans at 100 Hz (mean solve time 8.9 ms); the Unitree G1 sustains steady-state walking and recovers from impulsive 245 N forward and 175 N lateral pushes.

0.18

DAOCP: a dual active set solver for optimal control problems

eess.SY math.OC ·2026-09-27 ·Alberto Zaupa, Samuel Erickson, Mikael Johansson
similarity 0.61
Abstract · Submitted to ICRA 2027

We present DAOCP, a dual active set solver for linear quadratic optimal control problems with stage-wise equality and inequality constraints. Active set methods are leading Model Predictive Control benchmarks for full-body robotics, but existing solvers operate on dense QPs, while typical problem dimensions favor methods that exploit the optimal control structure. DAOCP combines the warm-starting capabilities of active set algorithms with the better computational scaling of structure exploiting solvers, by relying on a generalization of the relationship between the Riccati recursion and the Cholesky factorization of the condensed Hessian. This result enables dual active set iterations to operate directly on the original optimal control problem through recursive computations, without explicitly forming the condensed quadratic program. On robotics benchmarks, DAOCP is the fastest of four solvers in four of five scenarios, cutting average solve time on a 58-state Atlas model by 9$\times$ relative to state of the art solvers DAQP and HPIPM.

0.14

Contact-Implicit Stein Projected ADMM for Discovery of Diverse Contact-Rich Manipulation Strategies

cs.RO ·2026-09-23 ·Hrishikesh Sathyanarayan, Christian Hughes, Ian Abraham
hot direction similarity 0.61
Abstract

Contact-implicit trajectory optimization formulates contact-rich manipulation as a single constrained program; however, that single program run collapses onto one local optimum out of many equally valid contact modes, grasps, or push directions. As a consequence, the resulting manipulation strategy is reluctant to change and sensitive to initialization. In order to promote robust manipulation, this paper investigates how contact-implicit solvers can discover diverse contact-rich strategies. Our approach derives a variation of Consensus Alternating Direction Method of Multipliers (ADMM) combined with Stein variational inference methods to output a set of distinct contact-rich solutions. We find that applying the Stein repulsive force to ADMM's split variable (rather than its primal form) allows for effective coverage over the set of feasible contact strategies without prematurely stalling the solver. We demonstrate the effectiveness of our approach on a variety of contact-rich manipulation tasks, including pushing, grasping, and multi-robot handover. Last, we find the proposed solver is simpler in form and capable of discovering unique contact modes when compared with existing solvers. Videos and code with examples are found in https://anon-website-submission.github.io/stein-admm-website/.

0.39

DR-MPC: Fast and Feasible Dynamics-Relaxed Model-Predictive Control for Legged Locomotion

cs.RO eess.SY ·2026-09-17 ·Run Wang, Alapati Tuerxun, Shuo Liu, Wei Xiao, Ján Drgoňa +2 more
code/data similarity 0.60
Abstract · 8 pages, 5 figures, submitted to RA-L

This paper presents dynamics-relaxed model predictive control (DR-MPC), a novel MPC formulation for legged locomotion, and a tailored interior-point method (IPM) solver. The formulation combines online optimization feasibility by construction with a contact-aware input parameterization. DR-MPC moves the dynamics equality and affine input constraints into quadratic penalties and retains only nonempty box constraints. The resulting box-constrained quadratic program (QP) has a block-arrow Hessian that enables the state and affine-output directions to be eliminated through a Schur complement. The solver factors only the reduced control system after swing-force elimination and contact-aligned move blocking. For the evaluated implementations using the same DR-MPC formulation, our method achieves median end-to-end MPC speedups of $16.0\times$ over HPIPM and $4.4\times$ over OSQP, with comparable locomotion performance in simulation. DR-MPC achieves a median onboard MPC end-to-end time of $4.4$ ms and is validated on a Unitree Go1 quadruped. Open-source code will be made available after publication.

0.27

Joint-Feasibility Margin Feedback for Bounded-Input Second-Order Control Barrier Functions

cs.RO ·2026-10-12 ·Siyuan Yang, Shaoming He
code/data similarity 0.60
Abstract · 6 pages, 3 figures

Multiple second-order control barrier function constraints can exhaust their common control authority under bounded acceleration, even when the current state remains feasible. We define a signed local joint-feasibility margin whose sign exactly identifies whether the current barrier half-spaces intersect the admissible input set. For unit-scaled distance constraints, it has acceleration units and a support-function dual that identifies weighted constraint conflicts. We predict the margin one sample ahead for nine task-directed candidates, selecting either the least-deviating candidate that attains a desired margin or the candidate with the largest predicted margin before solving the same hard HOCBF quadratic program. A controlled one-step case shows that, at the state predicted under the hard-QP command, two constraints remain individually feasible but become jointly infeasible, whereas the margin-feedback controller retains a positive next margin. Separately, across 20 paired initial conditions, the margin-feedback controller retains the hard-QP command in a low-pressure task and acts at positive margin in a critical task before the hard-QP problem becomes infeasible; its trajectories remain feasible at that time and complete the task. Source code is publicly available. https://github.com/xirhxq/cbf/tree/robio2026-preventive-regulation

0.26