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