
144 Chapter 7 Propositional Satisfiability Techniques
planning in nondeterministic domains. These extensions are described in Part V,
Chapter 18.
7.2 Planning Problems as Satisfiability Problems
We consider a classical planning problem P as defined in Sections 2.1 and 2.2, where
P = (, s
0
, S
g
); = (S, A, γ ) is the planning domain, S the set of states, A the set
of actions, γ the deterministic transition function, s
0
the initial state, and S
g
the set
of goal states.
In the “planning as satisfiability” approach, a classical planning problem is
encoded as a propositional formula with the property that any of its models corre-
spond to plans that are solutions ...