Blum and Furst introduced the notion of a *planning graph*,
which is a powerful data structure that encodes information about
which states may be reachable [117]. For the logic-based
problem expressed in Formulation 2.4, consider performing
reachability analysis. Breadth-first search can be used from the
initial state to expand the state transition graph. In terms of the
input representation, the resulting graph may be of exponential size
in the number of stages. This gives precise reachability information
and is guaranteed to find the goal state.

The idea of Blum and Furst is to construct a graph that is much
smaller than the state transition graph and instead contains only
partial information about reachability. The resulting *planning
graph* is polynomial in size and can be efficiently constructed for
some challenging problems. The trade-off is that the planning graph
indicates states that can *possibly* be reached. The true
reachable set is overapproximated, by eliminating many impossible
states from consideration. This enables quick elimination of
impossible alternatives in the search process. Planning algorithms
have been developed that extract a plan from the planning graph. In
the worst case, this may take exponential time, which is not
surprising because the problem in Formulation 2.4 is
NP-hard in general. Nevertheless, dramatic performance improvements
were obtained on some well-known planning benchmarks. Another way to
use the planning graph is as a source of information for developing
search heuristics for a particular problem.