Multiple Shooting

Cutting a long trajectory into segments, integrating each one separately, then stitching them together with continuity constraints.

Multiple shooting is a transcription method for solving trajectory optimization and optimal control problems — turning a continuous-time problem into a finite-dimensional nonlinear program. Consider single shooting first: only the control is treated as an optimization variable, integrated in one continuous run from the initial state to the endpoint, checking whether it ‘hits’ the target and adjusting; over a long trajectory, or with an unstable system, small changes in the control get amplified, making convergence hard. Multiple shooting instead cuts time into several segments, treating each segment's starting state as an optimization variable too, integrating each segment separately, then adding matching conditions: the state at the end of one segment's integration must equal the state at the start of the next. This spreads the nonlinearity across short segments, making the numerics far more stable, and the segments can even be integrated in parallel. Bock and Plitt applied it to optimal control in 1984. It is one of two mainstream transcription methods alongside direct collocation, with the resulting problem commonly solved by sequential quadratic programming (SQP); NMPC tools such as OCS2 and acados both support it.

ExampleANYmal's perceptive NMPC (Grandia et al., 2022) discretizes a future motion window using multiple shooting, solving with SQP at 100 Hz to generate, in real time, motions that cross gaps and step across stepping stones.

Also called

Direct Multiple Shooting

Related

Direct Collocation · Trajectory Optimization · Sequential Quadratic Programming · Nonlinear Model Predictive Control · Optimal Control · acados (fast embedded optimal control solver)

Sources

Wikipedia: Direct multiple shooting method
Perceptive Locomotion through Nonlinear Model Predictive Control (arXiv 2208.08373)