Trajectory optimization · Contact dynamics

Lifted Multiple Shooting for
Parallel-in-Time Contact-Rich
Trajectory Optimization

Wei-Chen Li Glen Chou

01 / Sphere reorientationThree stages of an Allegro hand rotating a sphere.

180° rotation · 40 timesteps

02 / Pen reorientationThree stages of an Allegro hand lifting a pen from its palm and rotating it upright.

Grasp, lift, and rotate · 200 timesteps

Planning through contact, without contact-guiding costs.
IP-PAS generates fully dynamic in-hand manipulation trajectories using lifted multiple shooting.
+81.5 ppSuccess-rate improvement1
3.1×Faster solve time, up to2
40,000Timesteps in a planning horizon

Overview

Make contact forces part of the plan.

Contact makes manipulation possible. Its nonsmooth dynamics also make trajectory optimization difficult.

Conventional shooting methods determine contact forces inside the dynamics, leaving trajectory improvement dependent on contact sensitivities. Contact-implicit methods expose those forces, but introduce complementarity constraints that complicate optimization.

Lifted multiple shooting bridges these approaches. It introduces contact impulses as explicit optimization variables and separately enforces their consistency with the contact model. The resulting trajectory optimization problem can be solved directly with nonlinear program solvers.

Read the full abstract

Planning through contact requires accounting for the coupled dynamics of a robot and its environment, including inertial effects, contact forces, and friction. However, the nonsmoothness and multimodality of contact dynamics and contact geometry makes gradient-based optimization challenging. In this work, we propose lifted multiple shooting, a trajectory optimization transcription that can be solved directly using nonlinear program solvers. By explicitly introducing contact forces as optimization variables, our formulation allows the optimizer to satisfy motion consistency using any friction-feasible contact forces, while separately enforcing their attainability through the contact model. Our formulation supports a broad class of contact constitutive relations, with sensitivities computed through implicit differentiation. To enable efficient planning over long horizons and for high-dimensional systems, we further introduce IP-PAS, a parallel-in-time primal-dual interior-point solver that achieves O(log T) parallel computational depth. We evaluate the proposed methods on six fully dynamic contact-rich planning tasks, including nonprehensile pushing and in-hand manipulation, without contact-guiding costs. Lifted multiple shooting improves success rates by up to 81.5% over standard multiple shooting, while IP-PAS achieves solution quality comparable to serial methods with up to a 3.1× speedup and scales to horizons of 40,000 timesteps.

The method

Lift the contact. Parallelize time.

Two complementary ideas improve optimization reliability and computational scalability.

01 / Formulation

Lifted multiple shooting

Optimize states, controls, and contact impulses together. Motion consistency and contact attainability become separate equality constraints, with no complementarity constraints in the outer NLP.

xt+1 = fintegrate(xt, ut, γt)
γt = fcontact(xt, ut)

Contact resolution supports a broad class of constitutive relations, with sensitivities obtained by implicit differentiation.

02 / Solver

IP-PAS

A primal-dual interior-point solver replaces serial backward and forward recursions with associative scans, allowing computation across the planning horizon in parallel.

O(log T) parallel depth · O(T) total work

Temporal parallelism complements stagewise contact dynamics and derivative evaluation on the GPU.

Experiments

More reliable across six contact-rich tasks.

200 randomly sampled initial conditions per task and solver. Zero-trajectory initialization, without task-specific warm starts or contact-guiding costs.

Overlaid trajectories for box pushing, circle pushing, square knob rotation, and planar finger manipulation.
Four planar benchmarks, alongside sphere and pen in-hand manipulation.

The effect of lifting contact impulses

Success rates with IPOPT, holding the solver fixed and changing the transcription.

Success rates from Table II of the paper. MS means multiple shooting; LMS means lifted multiple shooting.
TaskMSLMS (ours)
Push box40.0%98.5%
Push circle33.5%95.5%
Square knob61.5%100.0%
Planar finger89.5%99.5%
Sphere in-hand13.0%94.5%
Pen in-hand20.0%95.5%

Source: Table II. Success requires final goal error below 0.01. In-hand benchmarks use 20-step horizons; the teaser shows separate, longer-horizon examples.

Parallel-in-time performance

Longer horizons.
Less time waiting.

IP-PAS maintains solution quality comparable to serial FATROP, with the largest speedups on high-dimensional in-hand tasks. On square knob rotation, it scales to a horizon of 40,000 timesteps.

IPOPT, FATROP, and IP-PAS use lifted multiple shooting. IMPACT uses a contact-implicit formulation. See the paper for full runtime and backend comparisons.

Solve time versus horizon length: IP-PAS grows more slowly than IPOPT, FATROP, and IMPACT up to 40,000 timesteps.
Figure 3 · Solve time as the planning horizon grows.

1 81.5 percentage points: 13.0% → 94.5% for sphere in-hand manipulation with IPOPT.

2 Pen in-hand manipulation: FATROP 17.6 s → IP-PAS 5.66 s, using the same lifted formulation.

Hardware validation

From a planned trajectory to a physical push.

A box-pushing experiment demonstrates transfer to a physical system, moving the box from its initial configuration toward the target.

Four successive photographs of a robot executing a box-pushing trajectory on a tabletop.
Figure 4 · Physical box-pushing experiment.

Reference

Cite this work

@misc{li_lifted_multiple_shooting,
  title = {Lifted Multiple Shooting for Parallel-in-Time
           Contact-Rich Trajectory Optimization},
  author = {Li, Wei-Chen and Chou, Glen},
  note = {Manuscript}
}

Citation reflects the supplied manuscript; publication details are not specified in the PDF.