Planning graph
A planning graph is a specialized data structure used in AI planning to efficiently compute heuristic estimates of how many steps are needed to achieve a g...
Efficient Heuristic Generation for Planning
A planning graph is a specialized data structure used in AI planning to efficiently compute heuristic estimates of how many steps are needed to achieve a goal. It was introduced by Blum and Furst in 1997 as the foundation of the GraphPlan algorithm, which was one of the fastest planners of its era.
The planning graph alternates between two types of layers. Action layers list all actions whose preconditions are satisfied by facts in the preceding fact layer. Fact layers list all facts that could be true given the actions in the preceding action layer. The graph starts from the initial state and expands forward, level by level, until all goal facts appear in a fact layer.
A critical feature of the planning graph is the tracking of mutex (mutual exclusion) relations. Two actions are mutex at a level if they cannot both occur in the same time step — for example, because one action deletes a precondition of the other. Two facts are mutex if no way exists to achieve both simultaneously. These mutex relations are computed efficiently and propagate through the graph.
The planning graph is not itself a plan. It provides a heuristic: the level at which all goal facts first appear without being mutually exclusive gives a lower bound on the number of planning steps required. This heuristic is used by planners like FF (Fast Forward) and LAMA to guide their search.
A concrete example: in a blocks world problem where blocks A and B are on the ground and must be stacked, the planning graph would show that at level one, the pick-up actions become available, and at level two, the stack action achieves the goal. The level count gives the heuristic estimate of two steps.
Exam tip: Know that the planning graph provides an admissible heuristic. Level 1 achievability of all goals (without mutex) gives the heuristic value. GraphPlan uses backward search through this structure.