Graphplan
Graphplan is a landmark classical planning algorithm that constructs a polynomial-size planning graph alternating between proposition layers and action layers. By explicitly representing mutex (mutual exclusion) relations between actions and propositions across discrete time steps, Graphplan bounds the search space and efficiently extracts valid parallel plans using backward state-space search.
HOW-TO IMPLEMENT & CONFIGURE
- Python 3.10+ runtime environment
- NetworkX library for graph manipulation and cycle verification
- Pytest for unit and invariant testing
Architectural Setup & Data Structures
Define immutable dataclasses for propositions, actions, and mutex constraints to back the graph layers.
from dataclasses import dataclass, field
from typing import FrozenSet, Set, Tuple
@dataclass(frozen=True)
class Action:
name: str
preconditions: FrozenSet[str]
add_effects: FrozenSet[str]
delete_effects: FrozenSet[str]
@dataclass
class PropositionLayer:
propositions: Set[str] = field(default_factory=set)
mutexes: Set[Tuple[str, str]] = field(default_factory=set)
@dataclass
class ActionLayer:
actions: Set[Action] = field(default_factory=set)
mutexes: Set[Tuple[Action, Action]] = field(default_factory=set)Core Algorithm: Graph Expansion & Mutex Propagation
Implement the forward expansion phase, adding applicable actions, propagating their effects to proposition layers, and calculating mutex relations.
class GraphplanEngine:
def __init__(self, initial_state: Set[str], goals: Set[str], actions: Set[Action]):
self.init = initial_state
self.goals = goals
self.actions = actions
self.prop_layers = [PropositionLayer(propositions=frozenset(initial_state))]
self.action_layers = []
def expand_graph(self):
current_prop = self.prop_layers[-1]
next_actions = set()
# Find applicable actions
for action in self.actions:
if action.preconditions.issubset(current_prop.propositions):
# Check mutexes among preconditions
if not any((p1, p2) in current_prop.mutexes or (p2, p1) in current_prop.mutexes
for p1 in action.preconditions for p2 in action.preconditions if p1 != p2):
next_actions.add(action)
action_layer = ActionLayer(actions=next_actions)
# Compute Action-Action mutexes (Inconsistent Effects, Interference, Competing Needs)
acts = list(next_actions)
for i in range(len(acts)):
for j in range(i + 1, len(acts)):
a1, a2 = acts[i], acts[j]
if self._actions_are_mutex(a1, a2, current_prop):
action_layer.mutexes.add((a1, a2))
self.action_layers.append(action_layer)
# Generate next proposition layer
next_props = set()
for a in next_actions:
next_props.update(a.add_effects)
prop_layer = PropositionLayer(propositions=next_props)
# Compute Proposition-Proposition mutexes
for p1 in next_props:
for p2 in next_props:
if p1 != p2 and self._props_are_mutex(p1, p2, action_layer):
prop_layer.mutexes.add((p1, p2))
self.prop_layers.append(prop_layer)
def _actions_are_mutex(self, a1: Action, a2: Action, prop_layer: PropositionLayer) -> bool:
# Inconsistent effects: one deletes add effect of other
if bool(a1.delete_effects & a2.add_effects) or bool(a2.delete_effects & a1.add_effects):
return True
# Interference: one deletes precondition of other
if bool(a1.delete_effects & a2.preconditions) or bool(a2.delete_effects & a1.preconditions):
return True
# Competing needs: preconditions are mutex in previous layer
for p1 in a1.preconditions:
for p2 in a2.preconditions:
if (p1, p2) in prop_layer.mutexes or (p2, p1) in prop_layer.mutexes:
return True
return False
def _props_are_mutex(self, p1: str, p2: str, action_layer: ActionLayer) -> bool:
# All producers of p1 and p2 are pairwise mutex
producers_p1 = [a for a in action_layer.actions if p1 in a.add_effects]
producers_p2 = [a for a in action_layer.actions if p2 in a.add_effects]
if not producers_p1 or not producers_p2:
return False
for a1 in producers_p1:
for a2 in producers_p2:
if a1 != a2 and (a1, a2) not in action_layer.mutexes and (a2, a1) not in action_layer.mutexes:
return False
return TrueVerification & Unit Testing
Validate the graph expansion and mutex propagation mechanisms with structured assertion suites.
def test_graph_expansion():
init = frozenset(["At(A)", "EmptyHand"])
goals = frozenset(["At(B)", "Holding(Package)"])
move = Action("Move", frozenset(["At(A)"]), frozenset(["At(B)"]), frozenset(["At(A)"]))
engine = GraphplanEngine(init, goals, {move})
engine.expand_graph()
assert "At(B)" in engine.prop_layers[1].propositions
assert len(engine.action_layers) == 1Production Hardening & Termination Checks
Implement graph leveling-off conditions to terminate expansion when no new propositions or mutexes are added.
def has_leveled_off(engine: GraphplanEngine) -> bool:
if len(engine.prop_layers) < 2:
return False
curr = engine.prop_layers[-1]
prev = engine.prop_layers[-2]
return curr.propositions == prev.propositions and curr.mutexes == prev.mutexesTheoretical Foundation & Mechanics
Graphplan operates by decoupling plan search into two interacting phases: forward graph expansion and backward plan extraction. The planning graph consists of alternating layers of propositions (P_0, P_1, …, P_k) and actions (A_0, A_1, …, A_k). Each proposition layer contains all propositions that could be true at that time step, while each action layer contains all actions whose preconditions are satisfied and non-mutex at the preceding proposition layer. Mutex constraints are propagated dynamically to ensure polynomial growth guarantees, capturing resource competition and interference.
Mutex Propagation Taxonomy
Mutex relations are categorized into Action-Action and Proposition-Proposition types. Action-Action mutexes occur under three conditions: (1) Inconsistent Effects, where one action deletes the add effect of another; (2) Interference, where one action deletes the precondition of another; and (3) Competing Needs, where preconditions of two actions are mutually exclusive in the prior proposition layer. Proposition-Proposition mutexes arise if all potential producer action pairs for two propositions are mutually exclusive.
Plan Extraction & Backtracking
Once all goal propositions appear in the latest proposition layer and are mutually non-exclusive, Graphplan initiates a backward search from the goal layer to layer zero. It selects a subset of non-mutex actions that achieve the subgoals of the current layer, checks for cross-action mutexes, and sets their preconditions as the new subgoals for the preceding layer. If search fails due to subgoal mutexes, the engine backtracks or continues forward expansion until the graph levels off.
Performance Characteristics & Limits
While Graphplan outperforms naive state-space search in tightly constrained domains due to its admissible heuristic generation via relaxed graph relaxation, it suffers from exponential blowup in deep or densely connected state spaces. Modern adaptations replace Graphplan's exact graph search with heuristic search planners like Fast Forward (FF) using relaxed plan graphs.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Blum, A. L., & Furst, M. L. (1997). Fast Planning Through Planning Graph Analysis. Artificial Intelligence, 90(1-2), 281-300.
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
- Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
