378 Chapter 10.

Classical Planning

Figure 10.6 Two state spaces from planning problems with the ignore-delete-lists heuris-
tic. The height above the bottom plane is the heuristic score of a state; states on the bottom
plane are goals. There are no local minima, so search for the goal is straightforward. From
Hoffmann (2005).

DECOMPOSITION A key idea in defining heuristics is decomposition: dividing a problem into parts, solv-
SUBGOAL
INDEPENDENCE ing each part independently, and then combining the parts. The subgoal independence as-
sumption is that the cost of solving a conjunction of subgoals is approximated by the sum
of the costs of solving each subgoal independently. The subgoal independence assumption
can be optimistic or pessimistic. It is optimistic when there are negative interactions between
the subplans for each subgoal—for example, when an action in one subplan deletes a goal
achieved by another subplan. It is pessimistic, and therefore inadmissible, when subplans
contain redundant actions—for instance, two actions that could be replaced by a single action
in the merged plan.
Suppose the goal is a set of fluents G, which we divide into disjoint subsets G1 , . . . , Gn .
We then find plans P1 , . . . , Pn that solve the respective subgoals. What is an estimate of the
cost of the plan for achieving all of G? We can think of each Cost (Pi ) as a heuristic estimate,
and we know that if we combine estimates by taking their maximum value, we always get an
admissible heuristic. So maxi C OST (Pi ) is admissible, and sometimes it is exactly correct:
it could be that P1 serendipitously achieves all the Gi . But in most cases, in practice the
estimate is too low. Could we sum the costs instead? For many problems that is a reasonable
estimate, but it is not admissible. The best case is when we can determine that Gi and Gj are
independent. If the effects of Pi leave all the preconditions and goals of Pj unchanged, then
the estimate C OST (Pi ) + C OST (Pj ) is admissible, and more accurate than the max estimate.
We show in Section 10.3.1 that planning graphs can help provide better heuristic estimates.
It is clear that there is great potential for cutting down the search space by forming ab-
stractions. The trick is choosing the right abstractions and using them in a way that makes
the total cost—defining an abstraction, doing an abstract search, and mapping the abstraction
back to the original problem—less than the cost of solving the original problem. The tech-
Section 10.3. Planning Graphs 379

niques of pattern databases from Section 3.6.3 can be useful, because the cost of creating
the pattern database can be amortized over multiple problem instances.
An example of a system that makes use of effective heuristics is FF, or FAST F ORWARD
(Hoffmann, 2005), a forward state-space searcher that uses the ignore-delete-lists heuristic,
estimating the heuristic with the help of a planning graph (see Section 10.3). FF then uses
hill-climbing search (modified to keep track of the plan) with the heuristic to find a solution.
When it hits a plateau or local maximum—when no action leads to a state with better heuristic
score—then FF uses iterative deepening search until it finds a state that is better, or it gives
up and restarts hill-climbing.

10.3 P LANNING G RAPHS

All of the heuristics we have suggested can suffer from inaccuracies. This section shows
PLANNING GRAPH how a special data structure called a planning graph can be used to give better heuristic
estimates. These heuristics can be applied to any of the search techniques we have seen so
far. Alternatively, we can search for a solution over the space formed by the planning graph,
using an algorithm called G RAPHPLAN .
A planning problem asks if we can reach a goal state from the initial state. Suppose we
are given a tree of all possible actions from the initial state to successor states, and their suc-
cessors, and so on. If we indexed this tree appropriately, we could answer the planning ques-
tion “can we reach state G from state S0 ” immediately, just by looking it up. Of course, the
tree is of exponential size, so this approach is impractical. A planning graph is polynomial-
size approximation to this tree that can be constructed quickly. The planning graph can’t
answer definitively whether G is reachable from S0 , but it can estimate how many steps it
takes to reach G. The estimate is always correct when it reports the goal is not reachable, and
it never overestimates the number of steps, so it is an admissible heuristic.
LEVEL A planning graph is a directed graph organized into levels: first a level S0 for the initial
state, consisting of nodes representing each fluent that holds in S0 ; then a level A0 consisting
of nodes for each ground action that might be applicable in S0 ; then alternating levels Si
followed by Ai ; until we reach a termination condition (to be discussed later).
Roughly speaking, Si contains all the literals that could hold at time i, depending on
the actions executed at preceding time steps. If it is possible that either P or ¬P could hold,
then both will be represented in Si . Also roughly speaking, Ai contains all the actions that
could have their preconditions satisfied at time i. We say “roughly speaking” because the
planning graph records only a restricted subset of the possible negative interactions among
actions; therefore, a literal might show up at level Sj when actually it could not be true until
a later level, if at all. (A literal will never show up too late.) Despite the possible error, the
level j at which a literal first appears is a good estimate of how difficult it is to achieve the
literal from the initial state.
Planning graphs work only for propositional planning problems—ones with no vari-
ables. As we mentioned on page 368, it is straightforward to propositionalize a set of ac-
380 Chapter 10. Classical Planning

Init (Have(Cake))
Goal (Have(Cake) ∧ Eaten(Cake))
Action(Eat (Cake)
P RECOND : Have(Cake)
E FFECT: ¬ Have(Cake) ∧ Eaten(Cake))
Action(Bake(Cake)
P RECOND : ¬ Have(Cake)
E FFECT: Have(Cake))

Figure 10.7 The “have cake and eat cake too” problem.

S0 A0 S1 A1 S2
Bake(Cake)
Have(Cake) Have(Cake) Have(Cake)
¬ Have(Cake) ¬ Have(Cake)
Eat(Cake) Eat(Cake)
Eaten(Cake) Eaten(Cake)
¬ Eaten(Cake) ¬ Eaten(Cake) ¬ Eaten(Cake)

Figure 10.8 The planning graph for the “have cake and eat cake too” problem up to level
S2 . Rectangles indicate actions (small squares indicate persistence actions), and straight
lines indicate preconditions and effects. Mutex links are shown as curved gray lines. Not all
mutex links are shown, because the graph would be too cluttered. In general, if two literals
are mutex at Si , then the persistence actions for those literals will be mutex at Ai and we
need not draw that mutex link.

tion schemas. Despite the resulting increase in the size of the problem description, planning
graphs have proved to be effective tools for solving hard planning problems.
Figure 10.7 shows a simple planning problem, and Figure 10.8 shows its planning
graph. Each action at level Ai is connected to its preconditions at Si and its effects at Si+1 .
So a literal appears because an action caused it, but we also want to say that a literal can
PERSISTENCE
ACTION persist if no action negates it. This is represented by a persistence action (sometimes called
a no-op). For every literal C, we add to the problem a persistence action with precondition C
and effect C. Level A0 in Figure 10.8 shows one “real” action, Eat(Cake), along with two
persistence actions drawn as small square boxes.
Level A0 contains all the actions that could occur in state S0 , but just as important it
records conflicts between actions that would prevent them from occurring together. The gray
MUTUAL EXCLUSION lines in Figure 10.8 indicate mutual exclusion (or mutex) links. For example, Eat(Cake) is
MUTEX mutually exclusive with the persistence of either Have(Cake) or ¬Eaten(Cake). We shall
see shortly how mutex links are computed.
Level S1 contains all the literals that could result from picking any subset of the actions
in A0 , as well as mutex links (gray lines) indicating literals that could not appear together,
regardless of the choice of actions. For example, Have(Cake) and Eaten(Cake) are mutex:
Section 10.3. Planning Graphs 381

depending on the choice of actions in A0 , either, but not both, could be the result. In other
words, S1 represents a belief state: a set of possible states. The members of this set are all
subsets of the literals such that there is no mutex link between any members of the subset.
We continue in this way, alternating between state level Si and action level Ai until we
reach a point where two consecutive levels are identical. At this point, we say that the graph
LEVELED OFF has leveled off. The graph in Figure 10.8 levels off at S2 .
What we end up with is a structure where every Ai level contains all the actions that are
applicable in Si , along with constraints saying that two actions cannot both be executed at the
same level. Every Si level contains all the literals that could result from any possible choice
of actions in Ai−1 , along with constraints saying which pairs of literals are not possible.
It is important to note that the process of constructing the planning graph does not require
choosing among actions, which would entail combinatorial search. Instead, it just records the
impossibility of certain choices using mutex links.
We now define mutex links for both actions and literals. A mutex relation holds between
two actions at a given level if any of the following three conditions holds:
• Inconsistent effects: one action negates an effect of the other. For example, Eat(Cake)
and the persistence of Have(Cake) have inconsistent effects because they disagree on
the effect Have(Cake).
• Interference: one of the effects of one action is the negation of a precondition of the
other. For example Eat(Cake) interferes with the persistence of Have(Cake) by negat-
ing its precondition.
• Competing needs: one of the preconditions of one action is mutually exclusive with a
precondition of the other. For example, Bake(Cake) and Eat(Cake) are mutex because
they compete on the value of the Have(Cake) precondition.
A mutex relation holds between two literals at the same level if one is the negation of the other
or if each possible pair of actions that could achieve the two literals is mutually exclusive.
This condition is called inconsistent support. For example, Have(Cake) and Eaten(Cake)
are mutex in S1 because the only way of achieving Have(Cake), the persistence action, is
mutex with the only way of achieving Eaten(Cake), namely Eat(Cake). In S2 the two
literals are not mutex, because there are new ways of achieving them, such as Bake(Cake)
and the persistence of Eaten(Cake), that are not mutex.
A planning graph is polynomial in the size of the planning problem. For a planning
problem with l literals and a actions, each Si has no more than l nodes and l2 mutex links,
and each Ai has no more than a + l nodes (including the no-ops), (a + l)2 mutex links, and
2(al + l) precondition and effect links. Thus, an entire graph with n levels has a size of
O(n(a + l)2 ). The time to build the graph has the same complexity.

10.3.1 Planning graphs for heuristic estimation

A planning graph, once constructed, is a rich source of information about the problem. First,
if any goal literal fails to appear in the final level of the graph, then the problem is unsolvable.
Second, we can estimate the cost of achieving any goal literal gi from state s as the level at
which gi first appears in the planning graph constructed from initial state s. We call this the
382 Chapter 10. Classical Planning

LEVEL COST level cost of gi . In Figure 10.8, Have(Cake) has level cost 0 and Eaten(Cake) has level cost
1. It is easy to show (Exercise 10.10) that these estimates are admissible for the individual
goals. The estimate might not always be accurate, however, because planning graphs allow
several actions at each level, whereas the heuristic counts just the level and not the number
SERIAL PLANNING
GRAPH of actions. For this reason, it is common to use a serial planning graph for computing
heuristics. A serial graph insists that only one action can actually occur at any given time
step; this is done by adding mutex links between every pair of nonpersistence actions. Level
costs extracted from serial graphs are often quite reasonable estimates of actual costs.
To estimate the cost of a conjunction of goals, there are three simple approaches. The
MAX-LEVEL max-level heuristic simply takes the maximum level cost of any of the goals; this is admissi-
ble, but not necessarily accurate.
LEVEL SUM The level sum heuristic, following the subgoal independence assumption, returns the
sum of the level costs of the goals; this can be inadmissible but works well in practice
for problems that are largely decomposable. It is much more accurate than the number-
of-unsatisfied-goals heuristic from Section 10.2. For our problem, the level-sum heuristic
estimate for the conjunctive goal Have(Cake) ∧ Eaten(Cake) will be 0 + 1 = 1, whereas
the correct answer is 2, achieved by the plan [Eat(Cake), Bake(Cake)]. That doesn’t seem
so bad. A more serious error is that if Bake(Cake) were not in the set of actions, then the
estimate would still be 1, when in fact the conjunctive goal would be impossible.
SET-LEVEL Finally, the set-level heuristic finds the level at which all the literals in the conjunctive
goal appear in the planning graph without any pair of them being mutually exclusive. This
heuristic gives the correct values of 2 for our original problem and infinity for the problem
without Bake(Cake). It is admissible, it dominates the max-level heuristic, and it works
extremely well on tasks in which there is a good deal of interaction among subplans. It is not
perfect, of course; for example, it ignores interactions among three or more literals.
As a tool for generating accurate heuristics, we can view the planning graph as a relaxed
problem that is efficiently solvable. To understand the nature of the relaxed problem, we
need to understand exactly what it means for a literal g to appear at level Si in the planning
graph. Ideally, we would like it to be a guarantee that there exists a plan with i action levels
that achieves g, and also that if g does not appear, there is no such plan. Unfortunately,
making that guarantee is as difficult as solving the original planning problem. So the planning
graph makes the second half of the guarantee (if g does not appear, there is no plan), but
if g does appear, then all the planning graph promises is that there is a plan that possibly
achieves g and has no “obvious” flaws. An obvious flaw is defined as a flaw that can be
detected by considering two actions or two literals at a time—in other words, by looking at
the mutex relations. There could be more subtle flaws involving three, four, or more actions,
but experience has shown that it is not worth the computational effort to keep track of these
possible flaws. This is similar to a lesson learned from constraint satisfaction problems—that
it is often worthwhile to compute 2-consistency before searching for a solution, but less often
worthwhile to compute 3-consistency or higher. (See page 211.)
One example of an unsolvable problem that cannot be recognized as such by a planning
graph is the blocks-world problem where the goal is to get block A on B, B on C, and C on
A. This is an impossible goal; a tower with the bottom on top of the top. But a planning graph
Section 10.3. Planning Graphs 383

cannot detect the impossibility, because any two of the three subgoals are achievable. There
are no mutexes between any pair of literals, only between the three as a whole. To detect that
this problem is impossible, we would have to search over the planning graph.

10.3.2 The G RAPHPLAN algorithm

This subsection shows how to extract a plan directly from the planning graph, rather than just
using the graph to provide a heuristic. The G RAPHPLAN algorithm (Figure 10.9) repeatedly
adds a level to a planning graph with E XPAND -G RAPH . Once all the goals show up as non-
mutex in the graph, G RAPHPLAN calls E XTRACT-S OLUTION to search for a plan that solves
the problem. If that fails, it expands another level and tries again, terminating with failure
when there is no reason to go on.

function G RAPHPLAN( problem) returns solution or failure

graph ← I NITIAL -P LANNING -G RAPH( problem)
goals ← C ONJUNCTS(problem.G OAL)
nogoods ← an empty hash table
for tl = 0 to ∞ do
if goals all non-mutex in St of graph then
solution ← E XTRACT-S OLUTION (graph, goals, N UM L EVELS(graph), nogoods)
if solution = failure then return solution
if graph and nogoods have both leveled off then return failure
graph ← E XPAND -G RAPH(graph, problem)

Figure 10.9 The G RAPHPLAN algorithm. G RAPHPLAN calls E XPAND -G RAPH to add a
level until either a solution is found by E XTRACT-S OLUTION, or no solution is possible.

Let us now trace the operation of G RAPHPLAN on the spare tire problem from page 370.
The graph is shown in Figure 10.10. The first line of G RAPHPLAN initializes the planning
graph to a one-level (S0 ) graph representing the initial state. The positive fluents from the
problem description’s initial state are shown, as are the relevant negative fluents. Not shown
are the unchanging positive literals (such as Tire(Spare )) and the irrelevant negative literals.
The goal At(Spare , Axle) is not present in S0 , so we need not call E XTRACT-S OLUTION —
we are certain that there is no solution yet. Instead, E XPAND -G RAPH adds into A0 the three
actions whose preconditions exist at level S0 (i.e., all the actions except PutOn(Spare , Axle)),
along with persistence actions for all the literals in S0 . The effects of the actions are added at
level S1 . E XPAND -G RAPH then looks for mutex relations and adds them to the graph.
At(Spare , Axle) is still not present in S1 , so again we do not call E XTRACT-S OLUTION .
We call E XPAND -G RAPH again, adding A1 and S1 and giving us the planning graph shown
in Figure 10.10. Now that we have the full complement of actions, it is worthwhile to look at
some of the examples of mutex relations and their causes:
• Inconsistent effects: Remove(Spare , Trunk ) is mutex with LeaveOvernight because
one has the effect At(Spare , Ground ) and the other has its negation.
384 Chapter 10. Classical Planning

S0 A0 S1 A1 S2
At(Spare,Trunk) At(Spare,Trunk) At(Spare,Trunk)
Remove(Spare,Trunk)

Remove(Spare,Trunk) ¬ At(Spare,Trunk) ¬ At(Spare,Trunk)

Remove(Flat,Axle) Remove(Flat,Axle)

At(Flat,Axle) At(Flat,Axle) At(Flat,Axle)

LeaveOvernight ¬ At(Flat,Axle) ¬ At(Flat,Axle)
LeaveOvernight

¬ At(Spare,Axle) ¬ At(Spare,Axle) ¬ At(Spare,Axle)

PutOn(Spare,Axle) At(Spare,Axle)
¬ At(Flat,Ground) ¬ At(Flat,Ground) ¬ At(Flat,Ground)
At(Flat,Ground) At(Flat,Ground)
¬ At(Spare,Ground) ¬ At(Spare,Ground) ¬ At(Spare,Ground)
At(Spare,Ground) At(Spare,Ground)

Figure 10.10 The planning graph for the spare tire problem after expansion to level S2 .
Mutex links are shown as gray lines. Not all links are shown, because the graph would be too
cluttered if we showed them all. The solution is indicated by bold lines and outlines.

• Interference: Remove(Flat , Axle) is mutex with LeaveOvernight because one has the
precondition At(Flat , Axle) and the other has its negation as an effect.
• Competing needs: PutOn(Spare , Axle) is mutex with Remove(Flat , Axle) because
one has At(Flat , Axle) as a precondition and the other has its negation.
• Inconsistent support: At(Spare , Axle) is mutex with At(Flat , Axle) in S2 because the
only way of achieving At(Spare , Axle) is by PutOn(Spare , Axle), and that is mutex
with the persistence action that is the only way of achieving At(Flat , Axle). Thus, the
mutex relations detect the immediate conflict that arises from trying to put two objects
in the same place at the same time.
This time, when we go back to the start of the loop, all the literals from the goal are present
in S2 , and none of them is mutex with any other. That means that a solution might exist,
and E XTRACT-S OLUTION will try to find it. We can formulate E XTRACT-S OLUTION as a
Boolean constraint satisfaction problem (CSP) where the variables are the actions at each
level, the values for each variable are in or out of the plan, and the constraints are the mutexes
and the need to satisfy each goal and precondition.
Alternatively, we can define E XTRACT-S OLUTION as a backward search problem, where
each state in the search contains a pointer to a level in the planning graph and a set of unsat-
isfied goals. We define this search problem as follows:
• The initial state is the last level of the planning graph, Sn , along with the set of goals
from the planning problem.
• The actions available in a state at level Si are to select any conflict-free subset of the
actions in Ai−1 whose effects cover the goals in the state. The resulting state has level
Si−1 and has as its set of goals the preconditions for the selected set of actions. By
“conflict free,” we mean a set of actions such that no two of them are mutex and no two
of their preconditions are mutex.
Section 10.3. Planning Graphs 385

• The goal is to reach a state at level S0 such that all the goals are satisfied.
• The cost of each action is 1.
For this particular problem, we start at S2 with the goal At(Spare , Axle). The only choice we
have for achieving the goal set is PutOn(Spare , Axle). That brings us to a search state at S1
with goals At(Spare , Ground ) and ¬At(Flat , Axle). The former can be achieved only by
Remove(Spare , Trunk ), and the latter by either Remove(Flat , Axle) or LeaveOvernight.
But LeaveOvernight is mutex with Remove(Spare , Trunk ), so the only solution is to choose
Remove(Spare , Trunk ) and Remove(Flat , Axle). That brings us to a search state at S0 with
the goals At(Spare , Trunk ) and At(Flat , Axle). Both of these are present in the state, so
we have a solution: the actions Remove(Spare , Trunk ) and Remove(Flat , Axle) in level
A0 , followed by PutOn(Spare , Axle) in A1 .
In the case where E XTRACT-S OLUTION fails to find a solution for a set of goals at
a given level, we record the (level , goals) pair as a no-good, just as we did in constraint
learning for CSPs (page 220). Whenever E XTRACT-S OLUTION is called again with the same
level and goals, we can find the recorded no-good and immediately return failure rather than
searching again. We see shortly that no-goods are also used in the termination test.
We know that planning is PSPACE-complete and that constructing the planning graph
takes polynomial time, so it must be the case that solution extraction is intractable in the worst
case. Therefore, we will need some heuristic guidance for choosing among actions during the
backward search. One approach that works well in practice is a greedy algorithm based on
the level cost of the literals. For any set of goals, we proceed in the following order:
1. Pick first the literal with the highest level cost.
2. To achieve that literal, prefer actions with easier preconditions. That is, choose an action
such that the sum (or maximum) of the level costs of its preconditions is smallest.

10.3.3 Termination of G RAPHPLAN

So far, we have skated over the question of termination. Here we show that G RAPHPLAN will
in fact terminate and return failure when there is no solution.
The first thing to understand is why we can’t stop expanding the graph as soon as it has
leveled off. Consider an air cargo domain with one plane and n pieces of cargo at airport
A, all of which have airport B as their destination. In this version of the problem, only one
piece of cargo can fit in the plane at a time. The graph will level off at level 4, reflecting the
fact that for any single piece of cargo, we can load it, fly it, and unload it at the destination in
three steps. But that does not mean that a solution can be extracted from the graph at level 4;
in fact a solution will require 4n − 1 steps: for each piece of cargo we load, fly, and unload,
and for all but the last piece we need to fly back to airport A to get the next piece.
How long do we have to keep expanding after the graph has leveled off? If the function
E XTRACT-S OLUTION fails to find a solution, then there must have been at least one set of
goals that were not achievable and were marked as a no-good. So if it is possible that there
might be fewer no-goods in the next level, then we should continue. As soon as the graph
itself and the no-goods have both leveled off, with no solution found, we can terminate with
failure because there is no possibility of a subsequent change that could add a solution.
386 Chapter 10. Classical Planning

Now all we have to do is prove that the graph and the no-goods will always level off. The
key to this proof is that certain properties of planning graphs are monotonically increasing or
decreasing. “X increases monotonically” means that the set of Xs at level i + 1 is a superset
(not necessarily proper) of the set at level i. The properties are as follows:
• Literals increase monotonically: Once a literal appears at a given level, it will appear
at all subsequent levels. This is because of the persistence actions; once a literal shows
up, persistence actions cause it to stay forever.
• Actions increase monotonically: Once an action appears at a given level, it will appear
at all subsequent levels. This is a consequence of the monotonic increase of literals; if
the preconditions of an action appear at one level, they will appear at subsequent levels,
and thus so will the action.
• Mutexes decrease monotonically: If two actions are mutex at a given level Ai , then they
will also be mutex for all previous levels at which they both appear. The same holds for
mutexes between literals. It might not always appear that way in the figures, because
the figures have a simplification: they display neither literals that cannot hold at level
Si nor actions that cannot be executed at level Ai . We can see that “mutexes decrease
monotonically” is true if you consider that these invisible literals and actions are mutex
with everything.
The proof can be handled by cases: if actions A and B are mutex at level Ai , it
must be because of one of the three types of mutex. The first two, inconsistent effects
and interference, are properties of the actions themselves, so if the actions are mutex
at Ai , they will be mutex at every level. The third case, competing needs, depends on
conditions at level Si : that level must contain a precondition of A that is mutex with
a precondition of B. Now, these two preconditions can be mutex if they are negations
of each other (in which case they would be mutex in every level) or if all actions for
achieving one are mutex with all actions for achieving the other. But we already know
that the available actions are increasing monotonically, so, by induction, the mutexes
must be decreasing.
• No-goods decrease monotonically: If a set of goals is not achievable at a given level,
then they are not achievable in any previous level. The proof is by contradiction: if they
were achievable at some previous level, then we could just add persistence actions to
make them achievable at a subsequent level.
Because the actions and literals increase monotonically and because there are only a finite
number of actions and literals, there must come a level that has the same number of actions
and literals as the previous level. Because mutexes and no-goods decrease, and because there
can never be fewer than zero mutexes or no-goods, there must come a level that has the
same number of mutexes and no-goods as the previous level. Once a graph has reached this
state, then if one of the goals is missing or is mutex with another goal, then we can stop the
G RAPHPLAN algorithm and return failure. That concludes a sketch of the proof; for more
details see Ghallab et al. (2004).
Section 10.4. Other Classical Planning Approaches 387

Year Track Winning Systems (approaches)

2008 Optimal G AMER (model checking, bidirectional search)
2008 Satisficing LAMA (fast downward search with FF heuristic)
2006 Optimal SATP LAN, M AX P LAN (Boolean satisfiability)
2006 Satisficing SGPLAN (forward search; partitions into independent subproblems)
2004 Optimal SATP LAN (Boolean satisfiability)
2004 Satisficing FAST D IAGONALLY D OWNWARD (forward search with causal graph)
2002 Automated LPG (local search, planning graphs converted to CSPs)
2002 Hand-coded TLPLAN (temporal action logic with control rules for forward search)
2000 Automated FF (forward search)
2000 Hand-coded TAL P LANNER (temporal action logic with control rules for forward search)
1998 Automated IPP (planning graphs); HSP (forward search)

Figure 10.11 Some of the top-performing systems in the International Planning Compe-
tition. Each year there are various tracks: “Optimal” means the planners must produce the
shortest possible plan, while “Satisficing” means nonoptimal solutions are accepted. “Hand-
coded” means domain-specific heuristics are allowed; “Automated” means they are not.

10.4 OTHER C LASSICAL P LANNING A PPROACHES

Currently the most popular and effective approaches to fully automated planning are:
• Translating to a Boolean satisfiability (SAT) problem
• Forward state-space search with carefully crafted heuristics (Section 10.2)
• Search using a planning graph (Section 10.3)
These three approaches are not the only ones tried in the 40-year history of automated plan-
ning. Figure 10.11 shows some of the top systems in the International Planning Competitions,
which have been held every even year since 1998. In this section we first describe the transla-
tion to a satisfiability problem and then describe three other influential approaches: planning
as first-order logical deduction; as constraint satisfaction; and as plan refinement.

10.4.1 Classical planning as Boolean satisfiability

In Section 7.7.4 we saw how SATP LAN solves planning problems that are expressed in propo-
sitional logic. Here we show how to translate a PDDL description into a form that can be
processed by SATP LAN . The translation is a series of straightforward steps:
• Propositionalize the actions: replace each action schema with a set of ground actions
formed by substituting constants for each of the variables. These ground actions are not
part of the translation, but will be used in subsequent steps.
• Define the initial state: assert F 0 for every fluent F in the problem’s initial state, and
¬F for every fluent not mentioned in the initial state.
• Propositionalize the goal: for every variable in the goal, replace the literals that contain
the variable with a disjunction over constants. For example, the goal of having block A