Direct Multiple Shooting

The core of the method involves dividing the prediction horizon into N multiple shooting intervals. The continuous-time OCP is discretized at these shooting nodes, creating a structured, finite-dimensional optimization problem. This segmentation is the primary distinction from single shooting methods and is key to handling unstable dynamics and path constraints effectively.

On each shooting interval, an initial value problem (IVP) is solved independently, integrating the system dynamics from an initial state guess at the node. This allows for:

• Parallel computation of trajectories, significantly speeding up function evaluations.
• Natural embedding of sophisticated, adaptive ODE/DAE solvers for accurate simulation.
• Isolation of numerical instability; a problem on one interval does not corrupt the entire solution.

To ensure the overall solution represents a physically continuous trajectory, continuity constraints are enforced at the boundaries between shooting intervals. These are equality constraints of the form: x_{i+1}(t_i) - x_{i+1}^0 = 0 where the simulated end state of interval i must match the initial state variable for interval i+1. The optimizer adjusts the initial state guesses at all nodes to satisfy these constraints, yielding a continuous, feasible solution.

By breaking the long integration into shorter segments, direct multiple shooting dramatically reduces the sensitivity to initial guesses compared to single shooting. This decouples the simulation from the optimization, preventing the "tail-wagging-the-dog" problem where small changes at the start cause exponentially large deviations at the end. It is particularly robust for systems with unstable modes or long horizons.

The transcribed NLP problem has a characteristic block-banded sparsity structure in its constraint Jacobian and Lagrangian Hessian. This structure arises because variables and constraints from one shooting interval primarily couple only with neighboring intervals. High-performance NLP solvers (like IPOPT or SNOPT) and QP solvers within Sequential Quadratic Programming (SQP) exploit this sparsity using specialized linear algebra, enabling the solution of large-scale problems.

State and input constraints can be enforced directly at the discretization nodes (and optionally at intermediate points via collocation). This explicit, pointwise enforcement is more straightforward and often more accurate than in single shooting, where constraints must be enforced along an entire, highly sensitive integrated trajectory. It provides direct control over constraint satisfaction throughout the horizon.

The Optimal Control Problem (OCP) is the foundational mathematical formulation that direct multiple shooting solves. It defines the goal of finding a control input trajectory and corresponding state trajectory that:

• Minimize a cost function (e.g., energy, time, tracking error).
• Obey the system's dynamic model (differential or difference equations).
• Satisfy path constraints (state/input limits) and boundary conditions (initial/final states). Direct multiple shooting is a discretization method that transforms this continuous-time OCP into a structured, finite-dimensional Nonlinear Programming (NLP) problem.

Nonlinear Programming (NLP) is the class of optimization problems with a nonlinear objective function and/or nonlinear constraints. After discretization via direct multiple shooting, the OCP becomes a large, sparse NLP. Key characteristics include:

• Decision Variables: The states and controls at each shooting node.
• Nonlinear Equality Constraints: The system dynamics and continuity conditions between shooting intervals.
• Inequality Constraints: Physical limits on states and controls. Solving this NLP requires specialized algorithms like Sequential Quadratic Programming (SQP) or Interior-Point Methods, which exploit the problem's sparse, block-structured nature for computational efficiency.

Sequential Quadratic Programming (SQP) is a leading iterative algorithm for solving the NLP generated by direct multiple shooting. At each iteration, it:

1. Approximates the original NLP with a Quadratic Programming (QP) subproblem (quadratic cost, linearized constraints).
2. Solves this QP to find a search direction.
3. Performs a line search to update the variables. The real-time iteration (RTI) scheme is a variant of SQP crucial for Nonlinear MPC. It performs only one SQP iteration per control time step, using a warm start from the previous solution, to meet strict timing requirements for physical systems.

Direct single shooting is a simpler alternative discretization method where only the control inputs are discretized as decision variables. The state trajectory is obtained by forward simulation of the dynamic model from the initial condition. Compared to direct multiple shooting:

• Pros: Fewer decision variables (only controls). Simpler constraint handling.
• Cons: Poor numerical stability for unstable systems or long horizons (simulation errors propagate). Less efficient for problems with path constraints on states. Direct multiple shooting's segmentation acts as a numerical stabilization technique, making it the preferred method for challenging, real-world control problems.

Collocation methods are another major class of direct transcription techniques for solving OCPs. Instead of solving initial value problems on intervals (like shooting), they parameterize the state and control trajectories with polynomial functions (e.g., Lagrange polynomials) within each segment. Key points:

• Discretization: Dynamics are enforced as equality constraints at specific collocation points within each element.
• Continuity: States are required to be continuous at element boundaries.
• Comparison to Shooting: Collocation often leads to even larger but more structured NLPs. It can provide higher-order accuracy and is often favored for problems requiring very precise trajectory representation.

Moving Horizon Estimation (MHE) is the dual problem to MPC. While MPC optimizes future control inputs, MHE optimizes past state estimates using a window of recent measurements. It is frequently formulated and solved using the direct multiple shooting method.

• Problem Structure: Similar to an OCP, but over a past horizon, minimizing the deviation between model predictions and sensor data.
• Advantages: Explicitly handles system nonlinearities and constraints on states (e.g., physical limits), outperforming classical observers like the Extended Kalman Filter in constrained, nonlinear settings.
• Implementation: The same numerical software (e.g., ACADO Toolkit, CasADi) and NLP solvers used for NMPC are typically employed for MHE.