M7-T4 — Planning with a Model: Random Shooting and CEM

Learning objectives

After this lesson, you should be able to:

• State the planning problem: choose an action sequence that minimises a cost under a model rollout.
• Run random shooting and CEM by hand on a small sample, including the elite refit of the mean and standard deviation.
• Design a cost with a goal term, a collision penalty and an action cost, and say what each does and what happens when one is removed.
• Count the model calls and time a plan needs, and explain why an open-loop plan from an imperfect model drifts.

The intuition

A chess player does not know the future; she imagines some. She tries a few sequences of moves in her head, judges where each leaves the board, and plays the first move of the one she likes best. Planning with a learned model is that, with one difference: the imagination is a function you fit from data, and it is fast enough to try thousands of futures per decision.

The simplest search is to guess. Draw N random action sequences, score each, keep the best. The figure shows how slowly this improves. From a start at (3, 3) with Scout at rest, the best of one sequence gains 0.02 m toward the goal in 12 steps; the best of 1024 gains 0.88 m. Each fourfold increase in N buys a smaller gain. The cross-entropy method does something smarter with the same kind of samples: it looks at which ones were good, moves the sampling distribution toward them, and samples again. With 48 samples per round and 3 rounds (144 in total) it gains 0.98 m, more than random shooting with 1024.

The mathematics

The planning problem

State x = [x, y, vx, vy], action a in [-1, 1]². A model f predicts the next state. For a horizon H, an action sequence is A = (a₀, …, a_H-1), and the model turns it into a predicted trajectory x₁, …, x_H. A cost scores it. Planning is the optimisation

The sequence has 2H numbers, 24 for H = 12. The function J is not differentiable in any convenient sense here (the collision term is a step), so we search rather than differentiate.

The cost used in this module

RLCore.planCost is, for each step t from 1 to H, the distance from the predicted position to the goal (9, 3), plus 50 if the position lies inside the pillar’s collision circle (radius 0.95 about (5, 3)), plus 0.02 |a_t|² for each action:

N, H

Number of sampled sequences, and the horizon in steps of 0.25 s. H = 12 is 3 s.

elite

One of the E lowest-cost samples in a round (E = 6 or 8 here).

iters

Number of CEM rounds. Random shooting is CEM with one round and no refit.

mean, std

The Gaussian over each action number: one mean and one standard deviation per time step and dimension. Initially mean 0 and std 0.7. Samples are clipped to [-1, 1].

Random shooting

1. Draw N sequences, each action number from N(mean, std²), clipped to [-1, 1].
2. Roll each through the model and compute J.
3. Return the sequence with the lowest J.

The cross-entropy method

CEM repeats that with a changing distribution. After each round, sort the samples by cost, keep the E elites, and refit the Gaussian to them:

The standard deviation uses the elites’ spread (divided by E, not E − 1) and is floored at 0.05 so the search never freezes completely. The next round samples from the new Gaussian. The returned plan is the best sample ever seen, not the final mean. Chua et al. (2018) use this planner with learned models in a robotics-flavoured benchmark setting, and Nagabandi et al. (2018) use random shooting; both are listed below.

Gradient-based trajectory optimisation

If the model and cost are differentiable you can instead compute the gradient of J with respect to the action sequence (by back-propagating through the rollout) and descend it, as you did for network weights in lesson M2-T3. Each step costs one rollout and one backward pass, and it converges in tens of steps, far fewer model calls than sampling. The price is local minima and non-smooth costs. A collision term that is a step has no useful gradient; it must be replaced by a smooth barrier. Sampling methods ignore all of this and are easy to write, which is why they are the usual first choice. This lesson does not implement the gradient version; lab M7-L2 uses sampling only.

A worked example

Every number below is a real output of Node running RLCore.planCEM (or a local copy of it, checked to give identical plans, with a settable collision weight) in the floor dynamics. Random numbers are SLAMCore.rng(seed).next. Different seeds give different numbers; where I give means they are over the seeds stated.

1. Random shooting against N. Start (3, 3) at rest, the goal 6.00 m away, floor model (gain 2.2, drag 3.4), horizon 12, 100 seeds per row. The gain is how much closer to the goal the end of the best plan is. N = 1: 0.02 m (sd 0.36, and one plan in a hundred enters the pillar circle). N = 4: 0.33 m; 16: 0.52; 64: 0.69; 256: 0.80; 1024: 0.88 (sd 0.13). Mean best cost: 73.2, 69.7, 67.9, 66.6, 65.7, 64.9. Each fourfold increase in N gains less. A hard heavy search (CEM with 400 samples, 40 elites and 8 rounds, seed 1) reaches cost 62.4, so even 1024 random samples were about 2.5 cost units from what search can find.

2. CEM at equal effort. Same start. Random shooting with 144 samples: 0.75 m gained (sd 0.17). CEM with 48 samples x 3 rounds and 6 elites (also 144 rollouts): 0.98 m (sd 0.08). CEM with 48 x 6: 1.06; 400 x 8: 1.19. At equal rollouts CEM gains 31% more and varies half as much.

3. A worked refit with 6 samples. Seed 4, horizon 12, 6 samples, 2 elites. Only the first two time steps are shown. Round 1 costs, sorted: 68.77, 71.83, 72.92, 73.22, 75.18, 75.47. The two elites are the first two:

Refit for step 0, x axis: mean (1.000 + (−0.296))/2 = 0.352, std |1.000 − (−0.296)|/2 = 0.648. Y axis: mean (0.475 − 1.000)/2 = −0.262, std 0.738. Step 1, x axis: mean 0.244 and std 0.030, which is below the floor, so the std is set to 0.05. Y axis: mean 0.344, std 0.336. The std fell where the elites agreed (step 1, x) and stayed wide where they did not (step 0). With only two elites the refit is noisy: the y mean at step 0 moved to −0.26 on the strength of one sample that went down. Round 2 (6 new samples from this Gaussian) had best cost 68.73 and elite mean 69.20, against 68.77 and 70.30 in round 1: a small improvement from a very small sample. Real planners use 40 to 400 samples and 5 to 10% of them as elites.

4. Cost per CEM round for a real plan. 64 samples, 8 elites, 6 rounds, same start, mean of 30 seeds. Best cost so far: 66.61, 64.95, 63.98, 63.64, 63.42, 63.22. Mean elite cost: 68.29, 65.89, 64.56, 63.99, 63.69, 63.44. The mean sampling std at step 0 shrinks 0.51, 0.36, 0.26, 0.21, 0.18, 0.16 (it starts at 0.7). Most of the gain comes in the first three rounds; rounds 4 to 6 add 0.8 cost units. Seed 7 alone: best cost 65.31, 64.22, 64.04, 63.49, 63.65 in rounds 1 to 5. The last value is higher than the one before it because the printed value is the best of that round, not the best so far.

5. What each cost term does (closed loop). Here I replan at every step (lesson M7-T5) with the floor model, 48 samples, 6 elites, 3 rounds, 20 starts from starts(11, 20, 'all') and the same 20 starts' 'near' region (start y between 2 and 4). Full cost: 20 of 20 reach the goal in both regions (54.6 steps on average for 'all'). No collision term (weight 0): 1 of 20 reaches the goal, 19 of 20 crash; for 'near' starts, 0 of 20 reach it and 20 of 20 crash. The goal term pulls Scout straight at the goal and the pillar is in the way. A collision weight of 5 instead of 50 still gave 20 of 20, so 50 is generous here. No action cost: 20 of 20, 53.6 steps: the action term barely mattered. Action cost 1 instead of 0.02: 11 of 20 reach the goal in 80 steps, none crash, nine time out: the planner would rather barely move than spend effort. The same effect shows in a single open-loop plan: from (2.5, 3) with a 20-step horizon, 46 of 50 plans made without a collision term entered the pillar circle, against 0 of 50 with it.

6. Compute. A plan costs samples x horizon x rounds model steps. 48 x 12 x 3 = 1728 steps took 0.6 ms (Node, this sandbox, mean of 300 plans after warm-up). 1024 x 12 x 1 = 12 288 steps: 4.3 ms. Horizon 6, 12, 24, 48 with 48 x 3: 0.3, 0.6, 1.1, 2.1 ms: linear in H. 192 samples x 24 steps x 5 rounds = 23 040 steps: 7.7 ms. The module notes quote about 40 ms per plan for the 1728-step plan; I did not reproduce that, and suspect a slower machine or a browser. Treat absolute times as machine-specific and the count of model steps as the portable number.

7. Open-loop plans fail. I planned 12 steps with the nominal model (gain 3.0, drag 3.0) from each of 20 starts, then executed the same actions on the floor (gain 2.2, drag 3.4). The model predicted the end position; the floor ended on average 0.62 m away (range 0.50 to 0.76). For a constant full command along x from (1, 3), the model-to-floor position error at steps 1, 3, 6 and 12 is 0.05, 0.21, 0.48 and 1.00 m: it grows faster than linearly at first, as the speed difference accumulates into distance. Step 12 is 4.8 times step 3. The pillar’s collision circle has radius 0.95, so an error of this size can turn a safe plan into a collision.

What this simulation simplifies. A point mass with linear drag, one obstacle, a known cost, and a model that is a clean linear function. The worked refit has two elites, a size chosen to be readable and not to be sensible. Results depend on the start and the budget, and I checked only the starts named here.

Engineering implications and limitations

Choosing and tuning the planner

• Samples. More samples reduce the variance of the plan, not just its cost: random shooting at N = 1024 had a standard deviation of 0.13 m in gain against 0.36 at N = 1. Decide a compute budget first, then split it between samples and rounds; at equal rollouts CEM beat random shooting here.
• Elite fraction. Too few elites (two, as in the worked example) give a noisy refit and collapse the std quickly; too many pull the mean back toward the average sample. 10 to 20% is a common starting point (6 of 48 and 8 of 64 here).
• The std floor and initial std. The 0.05 floor keeps some exploration. An initial std of 0.7 covers the action range of [−1, 1]; a much smaller one looks like the tiny-std failure of lesson M6-T7, where the planner never tries anything far from its start.
• Clip, do not rescale. Samples are clipped to the action limits. A plan that depends on commands the robot cannot execute is wrong at the root.
• Horizon. Long enough that the cost sees the consequence of an action. Lesson M7-T5 sweeps it.

Cost design

The cost is the specification (lessons M5-T1 and M5-T4 made the same point for rewards). The planner optimises exactly what it is given, including loopholes.

Constraints versus penalties

A penalty of 50 is a price, not a wall. If the goal term can pay for it, the planner will accept a collision. With the figures here (distance changes of about 0.2 m per step) 50 is rarely worth paying, but a cost of 50 against a goal of distance 100 would be. When a hard limit matters, enforce it outside the planner (a clip, a check before executing, a shield: lesson M5-T5) and use the penalty only to steer the search.

Compute

Count model steps, not seconds: samples x horizon x rounds. The sampling is trivially parallel (a batch of rollouts on a GPU is how learned-model planners run at tens of hertz). The model itself is often the dominant cost when it is a neural network, so a model that is 100 times more expensive per step is a plan that is 100 times slower. The rate at which a robot can replan is set by this number (lesson M7-T5).

Why an open-loop plan is not enough

A plan is a promise made in the model. Executing it without looking at the result passes the model’s error straight into the robot’s path, and (example 7) that error grows with the number of steps. Two things limit the damage: use only the early part of the plan, where the error is small, and look at the state again. That is model predictive control, the subject of lesson M7-T5 and the lab M7-L3.

Common misconceptions

Engineering takeaways

1. Planning picks the action sequence with the lowest model-predicted cost; random shooting samples sequences, CEM resamples around the elites.
2. At 144 samples CEM gained 0.98 m against 0.75 m for random shooting; random shooting needed 1024 samples to reach 0.88.
3. The cost is the specification: with no collision term 19 of 20 closed-loop runs crashed, and with an action weight of 1 the robot idled.
4. A plan costs samples x horizon x rounds model steps (1728 for 48 x 12 x 3, 0.6 ms here); time is machine-specific.
5. An open-loop plan inherits the model error, which grows with the horizon (0.05 m at step 1, 1.00 m at step 12 for a constant command), so plans are re-made as the robot moves.

References and further reading

Chua et al. and Nagabandi et al. plan with learned models by sampling; Williams et al. derive a sampling-based controller (MPPI).

• K. Chua, R. Calandra, R. McAllister and S. Levine, “Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models”, Advances in Neural Information Processing Systems (NeurIPS), 2018.
• A. Nagabandi, G. Kahn, R. S. Fearing and S. Levine, “Neural Network Dynamics for Model-Based Deep Reinforcement Learning with Model-Free Fine-Tuning”, IEEE International Conference on Robotics and Automation (ICRA), 2018.
• G. Williams, N. Wagener, B. Goldfain, P. Drews, J. Rehg, B. Boots and E. Theodorou, “Information Theoretic MPC for Model-Based Reinforcement Learning”, IEEE International Conference on Robotics and Automation (ICRA), 2017.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next, lesson M7-T5 closes the loop: plan, apply the first action, observe, and plan again. It sweeps the horizon, shows how replanning corrects a wrong model, and puts the plan’s compute time against the control rate. Lab M7-L2 has you build the cost, the shooting and the CEM refit yourself.

Related content

Nothing below is required to finish this lesson.

• Before
  M7-T3: Learned Dynamics and Model Error

  Train a one-step model and show how its error compounds over a prediction horizon.

• Lab
  M7-L2: Plan with Random Shooting

  Reach the pharmacy using only a learned model: sample action sequences, score them and refine with CEM.