What Is Planning?

Source slide: A2 What is Planning?

Planning begins with an ordinary question: what should an agent do before it starts acting? In automated planning we make that question precise enough for an algorithm. The planner is given a model of the current situation, a model of the available actions, and a description of what should become true. Its answer is a plan: a finite sequence of actions that is predicted to reach the goal.

If the actions are $a_1,\ldots,a_n$, we write the plan as

$$\pi = \langle a_1,\ldots,a_n\rangle .$$

This notation is simple, but it already contains the central idea of the course. A plan is not just a label saying “solve the problem”; it is an ordered recipe whose correctness depends on how actions change the world.

Planning as Model-Based Reasoning

Automated planning is part of AI, but it is not mainly a data-fitting problem. A planner does not start by observing many example solutions and learning a black-box policy. Instead, it reasons from an explicit model.

The ingredients of a planning problem are:

• an initial state, describing where execution starts;
• a set of actions, describing possible changes;
• a goal condition, describing what counts as success.

The planner combines these ingredients by search and logical reasoning. It asks which actions are applicable, what state would result, and whether some sequence eventually reaches a goal.

This model-based view is what makes domain-independent planning possible. The algorithm should not be custom-built for a single domain such as satellites, delivery trucks, or card games. Instead, each domain is written in a formal language, and a general planner works from that description.

Definition: Domain-independent automated planning

Domain-independent automated planning studies general algorithms that solve planning tasks from formal descriptions of states, actions, and goals, rather than from domain-specific procedural code.

The domain description says what the world is like and what actions mean. The planner decides how to put actions together.

Where Classical Planning Fits

Planning is one member of a larger family of sequential decision problems.

Different fields make different assumptions. Some systems plan while acting; some must deal with hidden information; some optimize long-term reward in stochastic environments; some must schedule durative or concurrent actions. Classical planning chooses a restricted but very important corner of this space.

Definition: Classical planning

Classical planning studies offline, discrete, deterministic, fully observable, single-agent problems whose solutions are sequential action plans.

Each word in that definition removes one complication:

• Offline means the whole plan is computed before execution begins.
• Discrete means states and actions are represented symbolically, not as continuous trajectories.
• Deterministic means the same action in the same state has one predicted outcome.
• Fully observable means the planner knows the complete state.
• Single-agent means there is no strategic opponent or teammate choosing actions.
• Sequential means the solution is a sequence, not a concurrent schedule or policy.

These assumptions are deliberately clean. They do not make planning trivial. They give us a foundation where the main mathematical objects can be studied without first handling uncertainty, sensing, time, or strategic interaction.

What a Planning Task Produces

At this point we can describe a planning task informally. Later chapters make the tuple precise.

Definition: Planning task, informal

A planning task describes an initial state, actions that can transform states, and a goal condition. A solution is an action sequence that transforms the initial state into a goal state.

One abstract form is

$$\Pi = \langle S, A, \gamma, s_0, S_G\rangle .$$

Here $S$ is the set of states, $A$ is the set of actions, $\gamma$ is the transition behavior, $s_0$ is the initial state, and $S_G$ is the set of goal states. If $\gamma^*(s_0,\pi)$ denotes the state reached by executing all actions in $\pi$ from $s_0$, then $\pi$ solves the task exactly when

$$\gamma^*(s_0,\pi) \in S_G .$$

If no such sequence exists, the correct answer is not a bad plan. The correct answer is that the task is unsolvable.

A Small Example of the Idea

Suppose a package is at the left location, a truck is also at the left location, and the goal is for the package to be at the right location. A planning model might contain actions such as load, drive, and unload. A candidate plan is

$$\langle \mathit{load}, \mathit{drive\_left\_to\_right}, \mathit{unload}\rangle .$$

To check the plan, we do not merely read the names. We simulate the model:

1. load is allowed because the package and truck are together.
2. after loading, the package is inside the truck.
3. drive_left_to_right moves the truck, and the package moves with it.
4. unload makes the package be at the right location.

The plan succeeds because the final state satisfies the goal. If the first action were unload, the model would reject it because unloading is not applicable when the package is not inside a truck.

Planning Domains

The examples in the lecture slides range across very different surface stories: Earth observation satellites, construction robots, cybersecurity adversary emulation, ecological conservation, bridge traversal, greenhouse control, and FreeCell-style puzzles.

The common structure is not that these domains look alike. It is that each can be described in terms of states, actions, and goals.

A satellite domain may include actions for pointing, waiting, and taking images. A construction domain may include actions for moving robots and placing blocks. A conservation domain may include interventions that change ecological conditions. Once written as a planning task, each domain induces a search problem: find a path from the initial state to a goal state.

Why Planning Is Hard

The natural way to picture planning is as a graph. Nodes are states. Edges are action applications. The initial state is the start node, and goal states are acceptable destinations. A plan is a path through this graph.

This picture is useful because it explains correctness. It is also dangerous because the graph is usually enormous.

With propositional descriptions, a task with $n$ Boolean facts may have up to $2^n$ states. Classical planning is PSPACE-complete in the general case. The point of the course is therefore not simply that a planner could search the graph. The point is how to search intelligently using structure: compact representations, heuristics, abstractions, landmarks, and other techniques.

Common Mistake

A common first mistake is to confuse a plan with a goal. “Put the package at the right location” is not a plan; it is a goal condition. A plan must say which actions to execute and in which order. Another mistake is to treat an action name as self-explanatory. In planning, the action’s formal preconditions and effects determine what it really means.

Chapter Summary

Automated planning is model-based reasoning about action. A planning task gives a planner an initial state, available actions, and a goal. The planner returns an action sequence that reaches the goal or reports that no plan exists. Classical planning focuses on a restricted setting: offline, discrete, deterministic, fully observable, single-agent, sequential planning. Even under these assumptions, the induced state spaces can be huge, which motivates the algorithmic methods studied throughout the course.

Study Check

1. Why is automated planning called model-based?
2. Which assumptions define classical planning?
3. In the state-space picture, what are the nodes and what are the edges?
4. Why is “reach the goal” not itself a plan?
5. Why can a compact planning description still induce an enormous search space?