Skip to main content
Back

CMU and MIT's Marble Solves Robot Contact Problems 400x Faster Than Rivals

A new open-source solver from CMU and MIT tackles contact and hybrid robotics planning problems by treating complementarity constraints as a Lie group.

Pro

Paper, Full Access
  • CMU and MIT researchers released Marble, an open-source C++ solver for linear complementarity quadratic programs with Julia and Python bindings.
  • The key idea: relaxed complementarity constraints form a Lie group, so optimization can stay on the manifold by construction.
  • A scaled softplus retraction replaces the exponential map, keeping gradients bounded and avoiding numerical overflow.
  • Fastest on 69% of the 39 MacMPEC benchmark problems, hitting the global optimum on 38 of them.
  • Solves contact, state-triggered, and progress-constraint robotics problems where LCQPow fails to converge.
  • Full derivation and code available in the arXiv paper and project page.

Contact-rich robotics problems have a nasty mathematical habit: they mix smooth continuous dynamics with discrete on/off events like a foot hitting the ground or a gripper closing on an object. A team from Carnegie Mellon and MIT just released Marble, an open-source solver that reframes one of the ugliest constraint types in this space as a smooth manifold. It beats the current state of the art on standard benchmarks and solves problems where existing tools simply give up.

The math behind making and breaking contact

Marble targets a class of problems called linear complementarity quadratic programs, or LCQPs. These are ordinary quadratic programs extended with a constraint of the form 0 ≤ s ⊥ t ≥ 0, meaning two variables must both be non-negative and their product must be zero. LCQPs are expressive enough to capture the local behavior of many non-smooth systems, including bi-level optimization, binary problems, and game-theoretic formulations. In robotics they naturally express contact: either the distance between two bodies is zero or the contact force is zero, but never both nonzero at once.

The catch is that LCQPs are non-convex and hard to solve, and relatively little research has focused on fast local solvers that exploit their specific structure. The feasible set forms an L-shape with a sharp non-smooth corner at the origin, which breaks most nonlinear solvers because it violates a standard regularity condition called LICQ that guarantees unique Lagrange multipliers.

Where existing solvers fall down

Three families of approaches have dominated: mixed-integer reformulations solved with tools like Gurobi (accurate but combinatorially expensive), smoothing methods that gradually relax the constraint, and penalty methods. LCQPow, an open-source package, includes