Formally, forward-chaining planning can be described as search through a landscape where each node is defined by a tuple .
is a world state comprised of predicate facts and
is the plan (a series of ordered actions) used to reach
from the initial state. Search begins from the initial problem state, corresponding to a tuple
.
Edges between pairs of nodes in the search landscape correspond to applying actions to lead from one state to another. When an action is applied to a search space node
the node
is reached, where
is the result of applying the action
in the state
and
is determined by appending the action
to
. Forward-chaining search through this landscape is restricted to only considering moves in a forwards direction: transitions are only ever made from a node with plan
to nodes with a plan
where
can be determined by adding (or `chaining') actions to the end of
.
As unguided search in this manner is prohibitively expensive in all but the smallest problems, heuristics are used to guide search. Commonly, a heuristic value is used to provide a goal distance estimate from a node to a node
in which
is a goal state.
Andrew Coles and Amanda Smith 2007-01-09