Definition

The simplest classical planning(see Automated planning) algorithms are state space search algorithms. These
are search algorithms in which the search space is a subset of the state space: Each
node corresponds to a state of the world, each arc corresponds to a state transition,
and the current plan corresponds to the current path in the search space.
Forward Search and Backward Search are two of main samples of state space planning.

Forward Search

Forward search is an algorithm that searches forward from the
initial state of the world to try to find a state that satisfies the goal formula.

Forward-search(O, s₀, g)
s = S₀
P = the empty plan
loop
if s satisfies g then return P
applicable = {a | a is a ground instance of an operator in O,and precond(a) is true in s}
if applicable = ∅ then return failure
nondeterministically choose an action a from applicable
s = γ(s,a)
P = P.a

Backward Search

Backward-search(O, s₀, g)
P = the empty plan
loop
if s₀ satisfies g then return P
relevant = {a |a is a ground instance of an operator in O that is relevant for g}
if relevant = ∅ then return failure
nondeterministically choose an action a from relevant
P = a.P
s = γ^-1(s,a)