AI planning explained: how machines plan their actions

AI planning is the branch of artificial intelligence that works out a sequence of actions to reach a goal. Wikipedia files it under automated planning and scheduling, and says the plans are typically carried out by intelligent agents, robots or unmanned vehicles. You give a planner a start, a goal and a list of possible actions, and it searches for a plan.

If you would rather plan against a fictional AI race yourself, Contain ASI is a browser story strategy game for 1 to 4 players where you try to keep four fictional AI labs from crossing into recursive self-improvement before 2027.

What AI planning means

The article defines the planning problem in three parts. You describe the possible starting states of the world, the goals you want, and the actions available. The planner's job is to find a plan that, from any of those starting states, reaches a state where the goals hold. That state is called a goal state.

Unlike classical control and classification problems, the article says, the answers here are complex and have to be found and tuned in a space with many dimensions. Planning is related to decision theory. In a known world with a good model, planning can happen offline: the plan is built and checked before anything is done. In an unknown world that keeps changing, the plan often has to be revised while acting, using trial-and-error methods such as dynamic programming and reinforcement learning.

The questions that make planning hard

How hard a planning problem is depends on what you are allowed to assume. The article lists the questions that sort problems into classes:

• Do actions always have the same result, or can they turn out differently?
• Are the state variables discrete or continuous?
• Can the agent see the current state clearly, or only part of it?
• Do actions take time, and can several happen at once?
• Is the aim a goal state, or the most reward?
• Is there one agent or several, and do they cooperate?

The simplest case is called classical planning. It has one known starting state, actions with sure results that take no time and happen one at a time, and a single agent. Because the start is known and every action is certain, a plan can simply be a list of actions in order. Once actions can turn out differently, the possible runs form a tree, and the plan has to say what to do at every branch.

Planners, domains and the languages they use

Many planners are domain independent. They take a domain model, which describes the actions possible in some area, plus the problem to solve. The same planner can then work on block stacking, logistics, workflow management or robot tasks. A route planner, by contrast, is the article's example of a domain-specific planner.

The most used languages for writing these problems, such as STRIPS and PDDL, describe the world with state variables. A state is one assignment of values to those variables, and each action changes some of them. The catch is size: the number of possible states grows exponentially with the number of variables, so planning suffers from what the article calls the curse of dimensionality and combinatorial explosion. Writing knowledge down this way is a form of knowledge representation.

One alternative is the hierarchical task network. Instead of states, you give tasks, and each task is either a basic action or breaks down into smaller tasks.

How a planner searches

For classical planning the article lists a few main methods:

• Forward search: start from the initial state and try actions, often guided by a heuristic that guesses which states are closer to the goal.
• Backward search: start from the goal and work back to what must be true before it.
• Partial-order planning: fix only the order of actions that matters, and leave the rest open.

Planning can also be turned into other problems. One method rewrites it as a logic satisfiability problem, and another as model checking, since both come down to moving through a space of states.

There is a related question: where does the action model come from? Writing by hand what every action needs and changes is, the article says, often difficult, slow and error-prone. Action model learning lets an agent learn those preconditions and effects from what it observes. Unlike reinforcement learning, it lets the agent reason about actions instead of making costly trials in the world. Our post on the frame problem covers a related difficulty: describing what an action leaves unchanged.

Planning when the world is uncertain

Real worlds are rarely classical, so the field has many variants. The table sums up the ones the article describes.

A Markov decision process allows chance outcomes with known odds and aims for the most reward. When the agent cannot see the whole state, it becomes a partially observable version, planned over beliefs. Small cases can be solved with methods called value iteration and policy iteration. Our post on AIXI shows a theoretical agent built on this kind of reward-seeking.

Conditional planning adds if-then steps, so a plan can react to what sensors report: if an object is found, do A, otherwise do B. An early conditional planner, Warplan-C, came in the mid 1970s. In contingent planning the sensors can be wrong, and the plan becomes a decision tree. The article's example: if it rains, take the umbrella. Michael L. Littman showed in 1998 that with branching actions the problem becomes much harder, in a complexity class called EXPTIME-complete. In conformant planning the agent cannot observe at all, so it needs one sequence that works whatever the true state is.

Temporal planning lets actions take time and overlap, which brings it close to scheduling. Preference-based planning looks for plans that also meet as many of the user's wishes as it can, such as cheap, quick and safe. The article's example of planning in use is the Hubble Space Telescope, which uses a short-term system called SPSS and a long-term planning system called Spike.

Try it: plan a block stack by hand

Block stacking is one of the article's example domains. Work this classical problem with forward search on paper.

1. Start state: blocks A, B and C are all on the table. Nothing is on top of any block.
2. Goal: A is on B, and B is on C.
3. Actions: "move X onto Y" needs X and Y to have nothing on top. Its effect: X is on Y, and Y no longer has a clear top. "Move X to the table" needs X to have nothing on top.
4. Search forward. From the start, you could move A onto B first. Now B is covered, so you cannot put B on C without undoing your work. That branch is a dead end.
5. Back up and try again. Move B onto C first. Then move A onto B. Both goals hold, so the plan is: move B onto C, move A onto B.

Notice what you did: you tried a branch, saw it fail, and backtracked. With three blocks that is quick. With thirty, the number of states explodes, which is why planners need heuristics.

Frequently asked questions

What is AI planning?

It is the branch of AI that finds a sequence of actions, or a strategy, that takes an agent from a starting state to a goal.

What is classical planning?

The simplest kind: one known start, actions with certain results taken one at a time, no durations and a single agent, so a plan is a list of actions.

What are STRIPS and PDDL?

They are widely used languages for writing planning problems, describing the world with state variables that actions change.

How is planning different from reinforcement learning?

A planner reasons with a model of what actions do. Reinforcement learning is one of the trial-and-error methods used when that model is missing or the world keeps changing.

Get started with Contain ASI

AI planning is about machines choosing their next moves. In Contain ASI the planning is yours, in a work of fiction about four labs in a race. It runs in your browser and needs WebGL 2, so use a recent Chrome, Edge, Firefox or Safari. The game is not a course and does not teach this topic.

Play Contain ASI: a story strategy game for 1 to 4 players that runs in your browser. Its labs, people and events are all fictional.