Plan Before You Go
Taking the cheapest next step feels smart, until you hit a dead end. Watch a greedy robot race a planning robot, then break a step.
Press Step both. The greedy robot grabs the cheapest next step. The planner searches first. These robots are plain code, not a language model.
Greedyready
Plannerready
Challenges
Watch the greedy robot get stuck (try the sandwich).
Make both robots finish the parcel job and see the planner pay less.
Break a step the planner is about to use and watch it fail.
Re-plan after a failure and finish the job.
Break a step, then finish with both robots. Compare their costs.
What just happened?
- The greedy robot only looks at the next step, so it grabbed cheap steps that did not help, or one that used up something it needed.
- The planner thinks ahead: it searches all the ways to reach the goal and picks the cheapest list of steps.
- Steps depend on each other (you cannot butter bread you have not got), so the plan puts them in a working order.
- When a step failed, the old plan was no use. Re-planning from where it stood found a new way.
- The planning here is a plain search. A real agent may let a language model propose the plan and then check it the same way.
For grown-ups: what's really going on
Each action has preconditions, add effects, delete effects and a cost, as in STRIPS planning. A state is a set of true facts.
- Greedy: pick the cheapest applicable action that adds a new fact, not tried before. It never looks ahead, so it can wander or use up a resource (the bread) that has no replacement: a dead end.
- Planner: uniform-cost search (Dijkstra) over states finds the lowest-cost action sequence, so it is optimal for the actions it knows about. The search size is shown. State spaces grow exponentially, so real planners add heuristics (A*).
- Topological order: from the plan we build a dependency graph (action A makes a fact action B needs) and sort it with Kahn's algorithm. Any such order is valid.
- Failure and re-planning: a failed action pays its cost and is marked unavailable; the planner searches again from the current state without it (replanning). This is why agents re-check the world after each step.
- No language model here: this is classical planning code. LLM agents often generate a plan in text, then execute and re-plan in the same way.
Further reading: Russell and Norvig, AI: A Modern Approach, ch. 10-11 · Fikes and Nilsson, STRIPS (1971).