Left Half-Plane
model predictive control · receding horizon · real-time iteration

Land

A rocket with one gimballed engine, dropped from height and off to one side, and shoved mid-air by a gust it never sees coming. Every tenth of a second the controller solves a short optimal control problem from where it is on the model, flies the first piece, and solves again. That is the whole trick, and it lands. You choose how far ahead each plan looks, how often it is remade, and how much computing each one gets.

world —runs today 0best today —the textbook —
Where you stand today

The rocket is a slender body with its engine at the base: thrust up to about twice its weight, a gimbal of twenty degrees. Each plan is an optimal control problem over the horizon on the model, solved by iterative LQR: a running cost on fuel, on tilt, on sideways speed, on being off the pad, and on straying from a descent profile that the engine could still arrest, a terminal cost on being at the pad and still, and a wall at the ground. The solver gets the sweeps you allow, warm-started from the last plan shifted in time, and a cold start beside it in case the shove made the old plan a bad guess. Cost is fuel in hover-seconds, plus six per metre of miss, twenty per radian of tilt and a little per excess speed at touchdown; a slam, a tumble or a run-off is a hundred. Hidden today: where the gust hits and how hard, and a rocket a few percent heavier or lighter than the model.

The trick

Plan, act, look again

One plan flown blind dies at the shove, because a plan is only as good as its start and the shove moves the start. A linear regulator to the pad does not know the engine has limits or the ground is there, and on a hard day it discovers both. Model predictive control does neither: it plans, which is how it respects the limits and the ground, and it re-plans from the measured state, which is how it is feedback. The horizon is the interesting knob. Too short and the plan cannot see the landing coming, so it dives now and pays later; too long and the far end of the plan is fantasy the shove will rewrite, at the price of computing that a short one would have spent looking again. And the sweeps: a plan solved from the last plan needs almost none, because last plan was nearly right, which is the observation behind the real-time iteration that lets this run at ten hertz in a browser, and would let it run at a kilohertz on a chip.

Cards
Solve a short optimal control problem, apply its first move, and solve again from where you are.mpc
minu₀…uN−1 Σ ℓ(xk, uk) + Vf(xN), xk+1 = f(xk, uk), u ∈ U, x ∈ X; apply u₀, repeatthe receding horizon: the same finite problem at every step, from the current state; constraints handled by construction, feedback by repetition

An optimal control problem over the whole flight is one plan, and a plan is open loop. Cut the problem to a horizon, solve it from the state you have now, keep only the beginning, and next period do it again: the repetition closes the loop, and the horizon keeps the problem small enough to solve in time. Constraints are not an afterthought but part of the problem, which is why the field grew up in chemical plants, where valves have ends and vessels have walls, and why it flies rockets now.

The theory's central worry is the horizon's edge: a plan that ends in a place from which no good continuation exists. The terminal cost Vf and a terminal set are what the stability proofs put there, a guarantee that the truncated problem does not lie about the future; here the descent profile plays that role. Get it wrong and a short horizon dives, which you can watch.

Where this game · the lab's swing-up, one plan tracked, is what MPC is when the plan is never remade · trajopt
Deeper Mayne, Rawlings, Rao & Scokaert, Constrained model predictive control: stability and optimality, 2000 · Rawlings, Mayne & Diehl, Model Predictive Control: Theory, Computation, and Design, 2017 · Garcia, Prett & Morari, 1989

Last plan was nearly right, so this plan needs one sweep, warm-started, and can run fast.real-time-iteration
u(j+1) = u(j) + Δu, one Newton-type step per sampling period, from the previous solution shiftedDiehl 2005: the real-time iteration; iterative LQR is the same idea with a Riccati sweep as the step

Solving a nonlinear optimal control problem to convergence takes many sweeps; doing that every period is what kept MPC slow for thirty years. The observation that broke it is that consecutive problems are nearly the same problem, so the previous solution, shifted by one period, is an excellent initial guess, and one sweep from it is usually enough. The controller then never converges and never needs to: it tracks the moving optimum with a lag of one sweep, and the lag is smaller than the plant's own motion.

The failure mode is a jump, when the state moves far from where the last plan began, as the shove does here. Then the warm start is wrong and one sweep is a step in the wrong basin; this page solves a cold start beside the warm one and keeps the better, which is a small price for a fall a plan cannot see. Iterative LQR is the sweep used here: linearise along the plan, a Riccati pass backwards, a rollout forwards, with a line search so that a bad step is rejected.

Where this game's sweeps knob · tvlqr, the backward pass on its own · the lab's re-planned swing-up, the same solver run once
Deeper Diehl, Bock & Schlöder, A real-time iteration scheme for nonlinear optimization in optimal feedback control, 2005 · Li & Todorov, Iterative linear quadratic regulator design, 2004 · Tassa, Erez & Todorov, 2012

References
  1. J. Richalet, A. Rault, J. L. Testud, and J. Papon, "Model predictive heuristic control: Applications to industrial processes," Automatica, vol. 14, no. 5, pp. 413–428, 1978.
  2. C. R. Cutler and B. L. Ramaker, "Dynamic matrix control — a computer control algorithm," in Proc. Joint Automatic Control Conference, 1980.
  3. C. E. Garcia, D. M. Prett, and M. Morari, "Model predictive control: Theory and practice — a survey," Automatica, vol. 25, no. 3, pp. 335–348, 1989.
  4. D. Q. Mayne, J. B. Rawlings, C. V. Rao, and P. O. M. Scokaert, "Constrained model predictive control: Stability and optimality," Automatica, vol. 36, no. 6, pp. 789–814, 2000.
  5. M. Diehl, H. G. Bock, and J. P. Schlöder, "A real-time iteration scheme for nonlinear optimization in optimal feedback control," SIAM Journal on Control and Optimization, vol. 43, no. 5, pp. 1714–1736, 2005.
  6. W. Li and E. Todorov, "Iterative linear quadratic regulator design for nonlinear biological movement systems," in Proc. ICINCO, pp. 222–229, 2004.
  7. Y. Tassa, T. Erez, and E. Todorov, "Synthesis and stabilization of complex behaviors through online trajectory optimization," in Proc. IEEE/RSJ IROS, pp. 4906–4913, 2012.
  8. B. Açıkmeşe and S. R. Ploen, "Convex programming approach to powered descent guidance for Mars landing," Journal of Guidance, Control, and Dynamics, vol. 30, no. 5, pp. 1353–1366, 2007.
  9. L. Blackmore, "Autonomous precision landing of space rockets," The Bridge, National Academy of Engineering, vol. 46, no. 4, pp. 15–20, 2016.
  10. J. B. Rawlings, D. Q. Mayne, and M. M. Diehl, Model Predictive Control: Theory, Computation, and Design, 2nd ed. Nob Hill, 2017.