TwiddleLab / Artificial Intelligence / Search, Games and Plans
Planning: From Goal to Steps
What you will learn
- Every action has preconditions (what must be true first) and effects (what it makes true).
- A plan is a list of actions where each one's preconditions are met when it runs, and the goal is true at the end.
- A planner can search for plans, for example backwards: which action gives the goal, and what does that action need?
- Wasted moves make a plan longer, not wrong. Planners look for short plans.
How the lesson goes
Tell a robot "make breakfast" and it needs many steps in the right order. How many for a bowl of cereal with milk?
The robot has one hand. The bowl and cereal are in a closed cupboard, the milk in a closed fridge. Bet.
Write the robot's plan. Run it and see where it gets stuck.
Tap actions to add them. Tap a step in your plan to remove it.
A planner finds the order by itself. It starts at the goal.
Step through it: each action's conditions become new goals.
The parts of planning have names.
What must be true before an action is its precondition. What the action changes is its effect. A plan is a list of actions that reaches the goal, and a planner is a program that searches for one.
Give each action its preconditions.
Drag each condition onto the action that needs it.
Each precondition is something the action itself can't do: you can't take the milk with a full hand or from a closed fridge. These rules are all a planner knows about the kitchen.
This plan works, but it takes 13 steps. Cut it to 9.
Tap a step to cross it out. Run to test.
Steps 2 and 3 take the cereal and put it straight back; steps 11 and 12 put the milk back and take it again. Each pair leaves the kitchen exactly as it was, so removing both keeps the plan working.
A plan can also be a program. Where is the cereal box when this one ends?
Each if checks a precondition before the robot acts.
hand_free is true, so the robot takes the bowl; then it holds the bowl, so it puts it on the table. fridge_open is false: skipped. Now the hand is free again, so it takes the cereal and is still holding it at the end.
Two plans for the same breakfast. Which one works?
Run both. Then tap the plan you would trust.
Opening the fridge needs a free hand. Plan A still holds the cereal at that point, so it stops. Plan B opens the fridge at the very start, while the hand is free, and puts the cereal back before taking the milk.
New goal: a cup of tea. Plan it in 8 steps.
The cup is on the table. One action is needed twice.
Previous lesson: Monte Carlo: Play Random Games · Next lesson: Constraint Puzzles · Part of the course: Search, Games and Plans
Lessons are interactive and need JavaScript. Turn it on to play them.
