Chapter
4
State-Space Planning
4.1 Introduction
The simplest classical 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.
In this chapter, Section 4.2 discusses algorithms that search forward from the
initial state of the world to try to find a state that satisfies the goal formula. Section 4.3
discusses algorithms that search backward from the goal formula to try to find the
initial state. Section 4.4 describes an algorithm that combines elements of both
forward and backward search. Section 4.5 describes ...