Sampling-Based Planning and Model Predictive Control

Imagine a delivery drone waiting at the edge of a windy courtyard. Its world model is a neural network trained on logs from previous flights. The network accepts a state and an action and returns the next state, but it is a black box. With piecewise-linear activations, its input-output map may have derivative discontinuities; its gradients may also be noisy or uninformative in regions poorly covered by training data. More fundamentally, it was trained to predict, not to be optimized. A next-state prediction loss has only an indirect relationship to the outcome we care about: whether the drone reaches the landing pad. How do you use the model to pick what to do?

Learned world models often make this problem more visible than hand-derived dynamics. Some simulators expose analytic derivatives and structure that an optimizer can exploit; others are black boxes too. A differentiable learned model supplies derivatives through backpropagation, but derivatives evaluated on out-of-distribution states can be technically well-defined and still unreliable for planning. A gradient-based planner inherits that weakness.

The core insight of this chapter is that you do not need to differentiate the model to plan with it. You only need to be able to run it forward. Given a candidate sequence of controls, you can roll the model out step by step and ask, "what would happen if I did this?" Then you can compare candidate sequences by the cost of the trajectories they produce and pick the best one. This is sampling-based planning: convert control into search, and search over action sequences by simulation.

The idea is old and appears in several related forms. Evolutionary optimization searches over populations of candidate policies or plans. Shooting methods in optimal control generate trajectories by propagating candidate control sequences through the dynamics. Path-integral methods form a more specific stochastic-control family with additional assumptions and importance-weighted updates. Their shared practical trade is narrower than an equivalence: derivative-free search can query a forward model without requiring analytic gradients, but it offers no general guarantee of finding a global optimum. When model rollouts can be batched efficiently, that trade is often useful for learned dynamics.

A common way to deploy this idea is model predictive control (MPC). Instead of committing to a long plan produced once, MPC plans over a finite horizon, executes the first action or a short block, observes the result, and replans from the new state. This closes the loop between the model and the environment, allowing feedback to correct some disturbances and model mismatch. Receding-horizon control long predates learned models and is widely used in industrial process control, as documented in Qin and Badgwell's industrial survey. Learned-model MPC changes the model inside the loop while retaining the same basic feedback structure.

In this chapter we build up this family of methods from the ground floor. We start with the simplest possible planner, random shooting, which samples many action sequences uniformly and keeps the best. We then introduce the cross-entropy method (CEM), which iteratively narrows a sampling distribution around the actions that worked. From there we assemble a full model predictive controller and see how replanning can compensate for some model error and disturbance. We then look at the design decisions that decide whether an MPC stack works in practice: how long the planning horizon should be, how often to replan, how to enforce constraints, how to warm-start the optimizer from the previous step's plan, and how to fit all of this inside a real-time control budget.

Building on the optimal-control foundations from Part II, this chapter treats MPC as a practical, sampling-based realization of the receding-horizon principle. It sits at the boundary between the pure predictive objectives of Part VI and the learned-policy imagination methods we will meet in Part VII, Chapter 4 and the decision-centric research lineages of Part VIII. Everything here assumes you have a forward model, either a hand-written simulator or a learned one. The chapter is about how to wield it.

It is worth being explicit about how this material lines up with a classical model-based control pipeline. System identification estimates dynamics from input-output data; state estimation enters when the state is not directly measured; and an optimal-control method chooses actions against that model and estimate. Under linear dynamics, quadratic objectives, and convex constraints, an MPC subproblem is often a quadratic program. Learned-model variants retain the decomposition but may replace physical states with latent states and structured dynamics with flexible function approximators. These are tendencies, not a clean classical-versus-learned dichotomy: classical models can be nonlinear and high-dimensional, while learned models can be smooth and structured. The relevant solver depends on the assumptions that the particular model, objective, and constraints satisfy.

One clarification helps before we start. When we say a model is "good," we mean it is good for a specific purpose, and it is worth separating four properties that are often blurred together.

• Predictive fidelity is how accurately the model's one-step or multi-step rollout matches the true system on states and actions that the training distribution covers. This is what a supervised loss measures, and it is the property most papers report.
• Representation quality is whether the model's internal state carries the information a planner needs, even if that representation is not a physically meaningful state vector. A latent model can have excellent representation quality while its decoded states look strange or discontinuous.
• Uncertainty quality is whether the model knows what it does not know, meaning that regions of state and action space far from the training data are flagged as uncertain instead of being confidently extrapolated.
• Decision usefulness is whether the plans that optimize against the model, once executed, make progress on the task. This is the property MPC needs, and it is not implied by the other three.

A model can have high average predictive fidelity and still be poor for planning, because optimization may select action sequences in regions where the model is systematically optimistic. Conversely, a model with mediocre average fidelity but accurate task-relevant local predictions can still support useful control. Sampling-based MPC exposes this separation directly: its decisive test is closed-loop performance under the planner's induced state-action distribution, not prediction loss alone.

Random shooting is the most stripped-down planner you can write. You fix a planning horizon $H$, which is the number of future steps you intend to consider. You fix a control distribution, usually uniform over the admissible action set $\mathcal{U} = [-u_{\max}, u_{\max}]^{d_a}$. You draw $N$ independent action sequences,

roll each sequence through the model to obtain a predicted trajectory $\tau^{(i)}$, evaluate a cost $J(\tau^{(i)})$, and return the sequence with the lowest cost. An open-loop controller may execute the whole sequence. When random shooting is used inside MPC, only the first action or a short block is executed before replanning. That is the entire search algorithm.

Notice what is absent from this recipe. There is no gradient, no Hessian, no linearization, no convexity assumption, and no requirement that the model be differentiable at all. The planner treats the dynamics as an opaque function mapping a state and an action to a next state. It queries that function only in the forward direction. In optimization language this is zeroth-order or derivative-free optimization: it uses function values alone to search. This single property is what makes random shooting compatible with trained neural networks, with simulators that contain lookup tables or branch logic, and with physical systems that can only be probed by experiment. It is also why the method scales so well with parallel hardware: every one of the $N$ rollouts is independent, so the whole batch can be evaluated on a GPU at once.

The reason this works at all is that a model rollout may be cheap relative to acting in the real world. The limitation is the curse of dimensionality of action-sequence space: a regular grid with resolution $\epsilon$ along each coordinate contains $(1/\epsilon)^{H d_a}$ length-$H$ sequences for an action dimension $d_a$. A 10-step horizon with two action coordinates and 100 levels per coordinate would contain $100^{20}$ grid points. Random sampling avoids enumerating that grid but does not remove the dimensional dependence. For a regular grid with $N$ points in a $H d_a$-dimensional unit box, the per-coordinate spacing scales as $N^{-1/(H d_a)}$. Random samples do not form a regular grid, so this curve is a resolution heuristic rather than an exact nearest-neighbor law; it still exposes the exponential dependence on sequence-space dimension.

The shape of that heuristic is worth seeing. The cell below evaluates $N^{-1/(H d_a)}$ over five decades of point budget for three sequence-space dimensions and plots the result on log-log axes.

Two practical notes before we move on. First, the split between samples and CEM iterations matters, not just their product. Iterations let the proposal migrate, whereas samples improve each empirical elite estimate; too few samples can make that estimate unstable. Which split is better therefore depends on dimension, elite fraction, objective, and overhead. Second, in a deterministic open-loop setting, both planners produce a plan calibrated to one starting state. That plan is not a feedback controller: it does not react to disturbances, model error, or unexpected observations. To close the loop, we need MPC.

Model predictive control is what you get when you take the horizon-restricted planner we just built and run it repeatedly in a closed loop. The formal problem statement is the following constrained, finite-horizon optimal control problem, solved from the measured state $s_t$ at each control tick:

The pieces are:

• Stage cost $\ell(s, a)$: the running penalty for being at state $s$ and applying control $a$. In our example, $\ell = \|p - g\|^2 + \alpha \|a\|^2$.
• Terminal cost $\ell_f(s_H)$: an additional penalty on the last state, which shapes the behavior of the plan's tail.
• Dynamics constraint $s_k = f(s_{k-1}, a_{k-1})$: the model. This is the only place the model enters the optimization.
• Control set $\mathcal{U}$: allowed control values.
• State set $\mathcal{S}$: allowed states. In the double integrator, this could be a velocity limit or a region of the plane the robot must stay in.

Each piece deserves a sentence of motivation, because the design of these terms is where most MPC engineering happens. The stage cost is the only term that expresses what it means to do the task well at every intermediate moment; if it is misspecified, the controller optimizes the wrong thing confidently. The terminal cost matters more than its small footprint suggests, because it is the sole representation of everything that happens after the horizon. A well-chosen terminal cost can substitute for a long horizon, and a poorly chosen one can bias the controller into a bad habit, for example a terminal cost that rewards speed at the end of the plan produces controllers that arrive fast and overshoot. The dynamics constraint is where the model lives, and it is written as an equality because the plan must be consistent with the model; a plan that violates the dynamics is not a plan at all, it is a wish. The control set bounds what actuators can physically do. The state set encodes safety and feasibility requirements, such as keeping a drone inside a geofence or a velocity below a structural limit.

Written this way, the problem has $H d_a$ control variables in a single-shooting formulation; a multiple-shooting formulation also represents states explicitly and enforces dynamics with equality constraints. Linear dynamics, a convex quadratic objective, and linear constraints produce a convex quadratic program. Stability guarantees for MPC require additional conditions, such as suitable terminal ingredients, invariant sets, or sufficiently long horizons; they do not follow merely from using a quadratic program. Mayne et al.'s review develops these conditions for constrained MPC. With a learned nonlinear or non-differentiable model, sampling-based single shooting enforces the dynamics by rollout rather than by placing state-transition equalities in the numerical optimizer.

The MPC algorithm is:

1. Observe or estimate the current state $s_t$.
2. Approximately solve the finite-horizon problem for a candidate action sequence $\hat a_{0:H-1}$.
3. Apply only the first action $\hat a_0$ to the real system.
4. Advance time by one step, observe the new state $s_{t+1}$, and go back to step 2.

Applying the first action and solving again at the next state is the receding-horizon principle. This is the same structure introduced in classical optimal control (see Part II, Chapter 4), here implemented with a sampling-based solver. The horizon slides forward with time, so each optimization covers a fixed number of future steps from the current state estimate.

Receding-horizon feedback limits how long the controller follows an uncorrected prediction. Once the actual or estimated state after $a_0^\star$ is available, the next optimization starts from that updated condition rather than the previous predicted state. This can reject some disturbances and model mismatch, but it does not make an inaccurate model harmless. Closed-loop stability and constraint satisfaction depend on the system, estimator, horizon, objective, terminal design, solver quality, and mismatch bounds. Frequent replanning is feedback, not by itself a stability proof.

Open-loop planning applies a sequence without incorporating new state information, whereas MPC observes or estimates the state and replans after the first action or a short block. That feedback can reduce sensitivity to disturbances represented in the measurement and model. It does not automatically confer robustness: unobserved disturbances, estimator error, actuator delay, infeasible replans, or large model mismatch can still defeat the controller. How conservative the resulting policy should be depends on the uncertainty model and constraints, not simply on whether replanning is present.

There is an important connection here to state estimation. When the state is not directly measured, step 1 requires an estimate or belief constructed from observations. Under the standard linear-Gaussian assumptions of LQG control, the separation principle permits an optimal controller to combine a Kalman state estimate with the full-state LQR law. That result does not justify replacing a filter by an arbitrary learned encoder. For nonlinear learned systems, feeding a point estimate or latent state to MPC is an approximation unless the estimator and controller satisfy stronger problem-specific conditions. A confidently wrong estimate can therefore drive a precisely solved plan toward the wrong state. Part VII, Chapter 3 develops planning from beliefs rather than treating an estimate as truth.

Common inner solvers include random shooting, CEM, and MPPI. For a fixed time budget, iterative proposal fitting can outperform uniform random shooting when low-cost controls occupy a region that the chosen proposal can represent. Multi-modal or discontinuous objectives can instead cause a single Gaussian CEM proposal to average incompatible modes or collapse prematurely. Random shooting retains broad coverage but spends no evaluations refining a promising region. A useful mental model is that CEM performs adaptive local search through its proposal, while random shooting preserves a fixed global proposal. The outcome is empirical, so wall-clock budgets and seeds should be matched when choosing between them.

We now assemble the whole thing into a closed-loop controller on our double integrator, with a small amount of process noise to represent the environment not matching the model exactly. The controller will plan, execute one step, replan, and repeat.

For this paired run, MPC ends closer to the goal and its distance-to-goal curve recovers after disturbances, while the open-loop run levels off. The distance curve shows the trajectory of the error rather than only its final value. Neither MPC nor its expected distance is generally monotone without additional assumptions; the point here is simply that the feedback controller retains a mechanism for correcting observed deviation.

The horizon length $H$ and the replanning policy (how often the controller solves a fresh problem) are the two knobs that decide MPC's behavior in practice. Neither is free: both trade off computational cost against the quality of the closed-loop behavior, and the right settings depend on the system, the model quality, and the time budget. It helps to think of them as two different ways of spending the same resource. A longer horizon spends compute to see further ahead; a shorter replanning interval spends compute to correct more often. The two are not interchangeable, because foresight and feedback do different jobs, but they compete for the same clock.

The horizon length defines what "long" means in the phrase "long-horizon planning." A short horizon omits consequences beyond its boundary and may fail to value a maneuver needed for later success. In this double-integrator task, $H=2$ exposes only 0.2 seconds of nominal motion. Under the stated cost and finite sampling budget, that limited lookahead produces a more myopic closed-loop result; the subsequent sweep reports what happens rather than assuming a particular overshoot pattern. A longer horizon can expose acceleration and deceleration together, but raises search dimension and gives model error more time to accumulate.

There is a second subtlety. A longer horizon raises the search dimension and gives model error more opportunities to accumulate. Much of its tail will also be replanned before execution, although it still influences the selected first action through the objective. The useful horizon must expose delayed consequences and allow the relevant maneuver to appear in the rollout. Our undamped double integrator has no finite settling time, so $1/\Delta t$ is only ten discretization steps, not a physical time constant. We therefore treat 15 to 25 steps as an empirical range for this particular target, action bound, cost, and controller budget rather than derive it from "settling." For stable physical modes, time constants can guide an initial horizon; in every case, closed-loop sweeps should test sensitivity.

Let us verify this empirically. We sweep the horizon from 2 to 40 and record the final distance to the goal after 40 control steps.

The figure shows two tuning sweeps from individual seeded experiments. Error falls as the horizon lengthens and then flattens in the first sweep, while the block-size outcome is non-monotonic in the second. A plateau or apparent optimum is a hypothesis to test, not a universal stopping rule: verify it across disturbances and seeds, and also check computation time, constraint violations, and task success before fixing either parameter.

A third design question is what to replan from. A measured or estimated point state is enough only when that representation is sufficient for the control problem. Under partial observability, belief-space planning propagates a distribution over latent states or hypotheses, as Part VII, Chapter 3 develops. The objective may then involve expected cost, risk, information gain, or constraints under that belief. Taking an expectation does not generally make the optimization landscape smoother, and minimizing expectation alone can hide low-probability, high-consequence outcomes.

Closely related is the question of what cost to optimize. Goal reaching may use stage and terminal distance terms; trajectory tracking may penalize deviation from a reference; stochastic objectives may average or otherwise aggregate costs over predicted futures. The objective, model, constraints, estimator, and replanning policy are conceptually separable, but they are not independent: changing one can alter feasibility, stability, and the best settings of the others.

Finally, terminal costs connect MPC to value-based planning: a terminal approximation summarizes consequences beyond the explicit horizon. If the terminal term equals the true optimal cost-to-go, the model is correct, and the same admissible actions and costs are used, a one-step Bellman minimization recovers an optimal action. Learned terminal values can therefore shorten the horizon needed in practice, but approximation error, model error, and constraints prevent an exact equivalence. Methods such as TD-MPC combine latent rollout optimization with learned value estimates, while MuZero uses a learned model inside tree search; later chapters distinguish those planning structures.

We have so far treated the MPC problem as unconstrained except for the box on controls. Real systems often impose joint, velocity, geofence, or clearance constraints. Sampling-based planners have several options: reject infeasible samples, project or transform samples into a feasible parameterization, use a constrained optimizer, or add violation penalties to the objective. We use a finite penalty here. It converts a hard requirement into a soft preference; it neither diverges at the boundary nor guarantees feasibility.

Rejection preserves feasibility among retained samples, but its acceptance rate equals the proposal probability of the feasible set and can become very small in a narrow corridor. It still offers no guarantee that the best retained finite sample is globally optimal. A finite penalty always assigns a numerical cost, but the selected plan may remain infeasible. If violation is unacceptable, a soft-penalty planner needs a separate verified feasibility or safety mechanism rather than an assumption that a small violation is harmless.

Consider an obstacle at position $c$ with radius $r$ for a point-mass robot. A soft constraint for the obstacle is

where $w$ is a positive weight. Any evaluated point inside the disc contributes a quadratic penalty; points on or outside the boundary contribute zero. The squared hinge is continuously differentiable at the boundary, although its second derivative changes there. Because the terms are summed, several shallow violations can outweigh one deeper violation. The obstacle term itself does not reward extra clearance once outside, so the task and effort terms determine whether a plan grazes the boundary or takes a wider route.

Let us add an obstacle directly on the straight-line path from start to goal. The finite penalty makes routing around it compete with goal error and effort; feasibility is checked after optimization.

In the fixed-seed left panel, the warm proposal yields a lower plan cost at the same one-iteration budget. The right panel reports local wall-clock measurements for the two stated workloads; it is a hardware-specific timing check, not an algorithmic ranking.

A few practical notes on budgets. At 100 Hz, one control period is 10 ms, and sensing, state estimation, communication, and actuation consume part of it. Possible overrun policies include returning the best candidate found so far, reducing samples or horizon, or running planning at a lower rate than the low-level controller. For example, a planner at 25 Hz may supply four actions or a local policy to a 100 Hz loop; its planning horizon is a separate design choice and need not equal four. Reusing a previous action can itself be unsafe, so the deadline fallback must be designed and verified for the plant rather than treated as a universal rule.

The deadline is part of the controller model rather than a service-level preference. The plant evolves while planning, so an overrun changes the state and time at which the computed action is applied. The effect need not grow monotonically with every delay, but the implemented input schedule is no longer the one assumed by a synchronous discrete-time design. Timing validation must therefore include tail latency and the specified fallback behavior.

The limitations of sampling-based MPC fall into four buckets: sample complexity, model exploitation, constraint handling, and real-time discipline. Each of these is an obstacle rather than a footnote, and each corresponds to an active area of research. It is also worth keeping the four notions of model quality from the introduction in mind here, because different failure modes are failures of different qualities, and conflating them leads to fixing the wrong thing.

Sample complexity is fundamental. The difficulty of covering action-sequence space grows with action dimension and horizon. Our 2D example uses 800 samples over 15 CEM iterations at $H=25$ and produces a useful plan for one task and seed; it does not establish a general sample requirement. Applying the same independent, diagonal-Gaussian proposal to a 20-dimensional humanoid over $H=100$ would search a 2,000-dimensional sequence space and is unlikely to cover useful modes efficiently. Temporally correlated proposals, spline or skill parameterizations, and learned low-dimensional action representations restrict search to a smaller structured family. They reduce effective dimension only when that family still contains adequate plans.

Model exploitation is the second hazard. Optimization searches for low predicted cost and may select out-of-distribution actions where model error is systematically optimistic. A deterministic conditional-mean predictor also omits outcome dispersion unless uncertainty is modeled separately; that can make risky sequences look safer than they are. Possible mitigations include calibrated uncertainty penalties, ensembles or probabilistic models, conservative objectives, and shorter horizons. Each changes the planning objective or compute cost, and none substitutes for closed-loop evaluation on the planner-induced distribution.

Constraint handling depends on the method. The finite penalties used here trade task cost against violation and cannot guarantee feasibility. Rejection, projection, constrained optimization, robust tubes, invariant sets, barrier-based filters, and supervisory shutdown mechanisms provide different levels of assurance under different assumptions. A safety-critical design must state which layer owns the guarantee and validate that layer against timing, estimation, and model errors.

Real-time discipline is the fourth bucket. A controller is real-time only relative to a stated deadline on its target hardware. Average notebook timing is insufficient; the design needs worst-case or high-quantile latency, an overrun policy, and end-to-end accounting for sensing and actuation. Sampling and iteration budgets are therefore part of the controller specification, not merely performance-tuning details.

MPC is established in process control and widely studied in robotics and autonomous systems. Sampling-based inner solvers extend receding-horizon control to models and objectives for which derivatives or structured solvers are unavailable or inconvenient. Their minimal computational interface is a forward rollout, a scalar evaluation, an action proposal, and a time budget. Practical deployment adds less minimal requirements: state estimation, constraint handling, uncertainty treatment, and a deadline policy.

Looking ahead, differentiable planning (Part VII, Chapter 2) uses model gradients to optimize actions, while belief-space planning (Part VII, Chapter 3) represents uncertainty in the state used for planning. Part VIII then separates several decision-centric lineages rather than forcing them into one loop: PETS and PlaNet use online trajectory optimization, MuZero performs tree search, TD-MPC combines trajectory optimization with learned values, and Dreamer commonly executes a policy trained in imagination without online MPC.

Sampling-based planning and MPC are the workhorses that make a black-box world model useful for control. The key ideas:

• Random shooting samples $N$ action sequences, rolls each through the model, and returns the lowest-cost sampled plan. It requires no gradients and works with a forward-model interface, but finite-budget coverage deteriorates rapidly as horizon and action dimension grow.
• CEM iteratively refits a proposal, here a diagonal Gaussian, to elite low-cost samples. This concentrates later evaluations in regions found promising, but a single proposal can collapse early or average incompatible modes. Its advantage over random shooting must be measured under matched budgets.
• MPPI perturbs a nominal action sequence and forms an importance-weighted update under a stochastic-control derivation. CEM uses a hard elite set instead. Their relative performance is problem- and budget-dependent.
• Model predictive control solves a finite-horizon problem from the current state estimate, applies the first action or a short block, and replans. This receding-horizon feedback can correct some observed disturbances and mismatch, but stability and feasibility require additional conditions.
• Replanning closes the loop by incorporating a new state estimate before choosing later actions. In the paired experiment, the same injected noise produced a larger final error open loop than under MPC; the magnitude is specific to the seed and budgets.
• Horizon length trades omitted delayed consequences against search cost and accumulated model error. Maneuver timescales provide an initial guess, while repeated closed-loop sweeps should check performance, constraints, and timing.
• Finite penalties soften constraints and cannot guarantee feasibility. Rejection, feasible parameterizations, constrained optimizers, and independently verified safety layers provide different alternatives under different assumptions. Discrete rollout checks can also miss violations between time steps.
• Warm starting from the shifted previous plan often gives the optimizer a useful proposal at the next tick. Its benefit depends on how quickly the state, goal, constraints, and model change, so it should be compared with a cold start across matched seeds and budgets.
• Real-time discipline is as important as algorithmic choice. The controller must hit its deadline, degrade gracefully when it cannot, and treat plan quality and plan latency as two halves of the same design problem.

The next chapters continue the arc. Differentiable planning uses gradients through sufficiently smooth models to optimize actions, sometimes alongside sampling. Belief-space planning treats uncertainty over latent state as part of the planning problem. The decision-centric lineages of Part VIII then combine learned models with several distinct planning and policy-learning structures.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about sampling-based planning and model predictive control.