Overview of Classical Planning Algorithms

Source slide: C1 Overview of Classical Planning Algorithms

Once planning tasks have a formal semantics, the next question is computational: how can a planner actually find a plan? The induced transition system may contain exponentially many states, so the answer cannot simply be “generate the whole graph and inspect it.”

This chapter gives a map of the main algorithmic families used in classical planning. Later chapters study particular heuristics and search methods in detail. Here the goal is to understand what each family treats as the central object of computation: individual states, propositional formulas, or compactly represented sets of states.

The First Split: Any Plan or the Best Plan

Before choosing an algorithm, we must know what kind of answer is required.

In satisficing planning, the task is to find any valid plan, preferably a good one but not necessarily the cheapest one. In optimal planning, the task is to prove that the returned plan has minimum cost among all possible plans.

This distinction changes the algorithmic burden. A satisficing planner may stop as soon as it reaches a goal. An optimal planner must also rule out cheaper alternatives. As a result, the best techniques for satisficing planning and optimal planning overlap much less than the shared vocabulary suggests.

For example, greedy best-first search may quickly find a plan by following a helpful heuristic estimate, but it does not by itself prove optimality. A* search can prove optimality when supplied with an admissible heuristic, but it may need to explore far more of the state space.

The Three Main Paradigms

Classical planning algorithms in this part of the course can be grouped into three broad paradigms:

• explicit search, which explores one concrete state at a time;
• SAT planning, which asks whether there exists a plan of a chosen length by building a propositional formula;
• symbolic search, which manipulates sets of states using compact data structures.

Each paradigm is a different way of avoiding the same disaster: explicitly materializing an enormous transition system.

Explicit State-Space Search

Explicit search is the most direct view of planning. The planner starts at the initial state and generates successor states by applying applicable operators. Search algorithms such as breadth-first search, A*, greedy best-first search, weighted A*, iterative deepening, and local search can all be used on this graph.

The common interface looks like this:

• init() returns the initial state $I$.
• is_goal(s) tests whether $s \models \gamma$.
• succ(s) returns pairs $\langle o, s\llbracket o\rrbracket\rangle$ for applicable operators $o$.
• cost(o) returns $\mathit{cost}(o)$.
• h(s) returns a heuristic estimate of the remaining cost or distance.

This interface hides the planning syntax behind state generation. Once succ and is_goal are available, the search algorithm can treat the task like a graph problem.

Design Choices in Explicit Search

The first design choice is search direction. A progression planner searches forward from $I$. A regression planner searches backward from the goal condition. A bidirectional planner tries to make the two searches meet. The next chapter focuses on the progression-regression distinction.

The second choice is the search algorithm. Uninformed algorithms use little task-specific guidance: breadth-first search, depth-first search, and iterative deepening are examples. Systematic heuristic algorithms, such as A* and greedy best-first search, use estimates to decide which state to expand next. Local search algorithms, such as hill-climbing or simulated annealing, move through candidate states or plans without necessarily preserving a complete frontier.

The third choice is search control. Heuristics are the most important form of control in this course, but not the only one. Planners may also prune symmetric states, use invariants, prefer helpful actions, or exploit partial-order reductions.

The central research question is therefore not merely how to search. It is how to derive useful guidance from a domain-independent task description.

A Small Explicit-Search Reading

Suppose the current state says that a truck is at the depot and a package is at the depot. The successor function checks every operator. load is applicable if both truck and package are at the depot; drive may also be applicable if the truck can move. Each applicable operator contributes one outgoing edge.

A heuristic might estimate that the package is two steps away from being delivered: load it, then drive or unload depending on the domain model. The search algorithm decides whether to expand this state before others. The semantics define which successors exist; the heuristic affects which ones are considered soon.

SAT Planning

SAT planning changes the question. Instead of directly traversing states, it fixes a horizon $T$ and asks:

Is there a plan of length $T$ that reaches the goal?

For a planning task $\langle V,I,O,\gamma\rangle$, the encoding introduces propositional variables for each time step:

• $v_i$ records the truth value of state variable $v$ after step $i$, for $0 \le i \le T$;
• $o_i$ records whether operator $o$ is chosen at step $i$, for $1 \le i \le T$.

The formula then enforces the initial state, the goal at the horizon, operator preconditions, effects, and the constraints needed to make the time steps behave like a valid execution. A satisfying assignment corresponds to a plan; if the formula is unsatisfiable, no plan of that horizon exists under the encoding.

To search for a plan, a SAT-based planner tries increasing horizons. If the horizon is too short, the formula is unsatisfiable. Once the horizon is long enough, a satisfying assignment can be decoded into a plan.

Some encodings allow several non-conflicting operators to occur at the same time step. This parallel view can reduce the required horizon, because independent actions do not need to be serialized in the formula in the same way.

Symbolic Search

Symbolic search keeps the state-space view but changes the unit of computation. Instead of storing and expanding individual states, it represents sets of states compactly, often using binary decision diagrams (BDDs) or related structures.

A symbolic breadth-first search can be read as follows:

1. Represent the goal set as $\mathit{goal\_states} = \mathit{models}(\gamma)$.
2. Start with $\mathit{reached}_0 = \{I\}$.
3. At layer $i$, test whether $\mathit{reached}_i \cap \mathit{goal\_states}$ is nonempty.
4. If not, compute the next reached set:

$$\mathit{reached}_{i+1} = \mathit{reached}_i \cup \mathit{apply}(\mathit{reached}_i,O).$$

5. If the reached set stops changing, no new states can be found; otherwise continue.

The promise is compression. A set containing exponentially many states may have a compact BDD representation. When this works, symbolic search can process large regions of the state space at once.

The difficulty is that compactness is not guaranteed. The size of a BDD can depend heavily on the structure of the task and on technical choices such as variable ordering. It is also harder to integrate many heuristic ideas into symbolic search than into explicit search.

Planner Examples

The slide deck lists several planning systems to show how these paradigms appear in practice.

Planner	Class	Main approach	Notable idea
FF	Satisficing	Explicit search	Enforced hill-climbing, FF heuristic, helpful actions
LAMA	Satisficing	Explicit search	Weighted A*, landmark heuristics, preferred operators
Fast Downward Stone Soup	Optimal portfolio	Explicit search	A* with strong optimal heuristics such as LM-cut and merge-and-shrink
Madagascar	Satisficing	SAT planning	Parallel SAT encodings and planning-specific SAT choices
SymBA*	Optimal	Symbolic search	Symbolic Dijkstra/A* with BDDs
Ragnarok	Optimal portfolio	Explicit search and related techniques	Portfolio search including cost-partitioning ideas

The important lesson is not to memorize the table. It is to see that planner design combines a planning objective, a representation of the search problem, and a control strategy.

What Can Go Wrong

One common mistake is to identify “heuristic” with “not rigorous.” In planning, a heuristic is a formal function used to guide search. Some heuristics are admissible and support optimality proofs; others are inadmissible but useful for satisficing search.

Another mistake is to assume that SAT planning avoids search. It does move much of the work to a SAT solver, but the planner still searches over horizons and relies on an encoding whose size and structure matter.

A third mistake is to think symbolic search is automatically smaller because it stores sets. Symbolic representations can be exponentially compact, but they can also become large. The benefit depends on the structure of the represented sets.

Chapter Summary

Classical planning algorithms can be organized around three major paradigms. Explicit search explores concrete states and relies heavily on search control, especially heuristics. SAT planning encodes bounded plan existence as propositional satisfiability and increases the horizon until a solution is found. Symbolic search manipulates compact representations of sets of states. Across all three, satisficing and optimal planning impose different requirements, which is why successful planners often use quite different methods for the two settings.

Check Your Understanding

1. Why does optimal planning usually require more than simply finding a goal state?
2. What information must the succ(s) function provide in explicit search?
3. In SAT planning, what does it mean when the formula for horizon $T$ is satisfiable?
4. Why can symbolic search be powerful, and why is that power not guaranteed?