Graphplan

The core data structure is a directed, layered graph with alternating proposition layers (P_i) and action layers (A_i).

• Proposition Layer P_0: Represents all facts true in the initial state.
• Action Layer A_i: Contains all actions whose preconditions are present in P_i, plus special no-op actions that propagate true propositions forward unchanged.
• Proposition Layer P_i+1: Contains all add effects of actions in A_i. Edges connect preconditions to actions and actions to their effects. This structure compactly represents state progression over discrete time steps.

A defining feature is the propagation of mutex relationships, which identify pairs of propositions or actions that cannot be true or executed concurrently in the same layer.

• Action Mutex: Two actions are mutex if they interfere (one deletes the other's precondition or effect) or if their preconditions are mutually exclusive.
• Proposition Mutex: Two propositions are mutex in a layer if all ways of achieving one are mutex with all ways of achieving the other. This explicit tracking of conflicts allows the algorithm to prune vast portions of the search space that contain logical contradictions.

Once the planning graph is expanded until a proposition layer contains all goal facts non-mutex, a backward search begins.

• The algorithm works recursively from the final goal propositions, selecting a non-mutex set of actions from the preceding action layer that support them.
• The preconditions of those actions become the new sub-goals for the previous proposition layer.
• This process continues backward to the initial layer. If at any point a supporting set of non-mutex actions cannot be found, the graph is expanded further and the search restarts. This combines the systematic pruning of the graph with goal-directed search.

The construction of the planning graph layers is a polynomial-time operation in the size of the problem (number of propositions and actions). The graph grows monotonically: propositions and actions are only added, never removed, and mutex relations can only decrease. This guarantees the algorithm will reach a fixed-point layer where the graph structure no longer changes. This phase is highly efficient compared to directly searching the exponentially large state space.

For problems where all actions have equal cost, Graphplan is guaranteed to find a shortest parallel plan. Because the planning graph is expanded one time step at a time, the first plan found during backward search will have the minimal number of layers (parallel steps). Within each layer, multiple non-mutex actions can be executed concurrently. This makes it a powerful algorithm for minimizing makespan in domains with concurrency.

Graphplan offered significant performance improvements over earlier planners like those based on pure STRIPS forward or backward search.

• Early Infeasibility Detection: The mutex mechanism quickly reveals when goals are inherently contradictory.
• Effective Pruning: The graph explicitly encodes what cannot be done together, dramatically reducing the branching factor for the subsequent search.
• Concurrency Modeling: The layered structure naturally represents parallel action execution, a complex feature for sequential state-space searchers. While modern SAT and heuristic search planners often outperform it on large problems, Graphplan's core ideas remain highly influential in automated planning theory.

PDDL is the standardized, first-order logic-based language used to formally define planning problems for algorithms like Graphplan. It provides the syntax for specifying:

• Domains: The predicates (properties) and actions (operators) available.
• Problems: The specific objects, initial state, and goal conditions. Graphplan consumes a PDDL description to construct its initial planning graph layers, parsing the preconditions and effects of each action.

STRIPS (Stanford Research Institute Problem Solver) is the foundational action representation that PDDL extends. A STRIPS action is defined by:

• Preconditions: Logical propositions that must be true for the action to be applicable.
• Add Effects: Propositions the action makes true.
• Delete Effects: Propositions the action makes false. Graphplan's planning graph explicitly tracks the propagation of these propositions (facts) and the mutual exclusion (mutex) relationships between actions that interfere with each other.

SATPlan is a major alternative approach to Graphplan. It encodes the planning problem into a propositional logic formula (a Boolean satisfiability problem).

• The formula asserts that there exists a plan of a given length n.
• A SAT solver (like MiniSat or Glucose) finds a satisfying assignment, which is then decoded into a sequence of actions. While Graphplan builds an explicit graph structure, SATPlan uses a compact logical encoding, often allowing it to solve very large problems by leveraging decades of SAT solver optimization.

These are the classical search paradigms that Graphplan's graph structure aims to improve upon.

• Forward Search (Progression): Starts at the initial state, applies actions, and searches forward through the state space. It can be inefficient due to a large branching factor.
• Backward Search (Regression): Starts at the goal state and applies actions in reverse to find predecessor states. Graphplan's innovation is to build the planning graph once as a compact reachability analysis, then perform a highly focused backward search over this structure, avoiding the exponential state space explosion of naive search.

A core concept in Graphplan's efficiency. Mutexes (mutual exclusions) are constraints identified during graph expansion that prevent certain actions or facts from appearing together in the same plan step.

• Action Mutex: Two actions interfere if one deletes a precondition or effect of the other.
• Fact Mutex: Two facts (propositions) cannot both be true at the same time because no action can achieve them concurrently without conflict. By propagating mutex relations forward through the graph, Graphplan prunes vast portions of the search space, making the subsequent solution extraction phase tractable.

The formal environments in which planning occurs.

• State Space: The set of all possible configurations of the world, defined by the truth values of all propositions. For non-trivial problems, this space is astronomically large.
• Action Space: The set of all ground (instantiated) actions that can be executed. Graphplan does not explicitly enumerate the full state space. Instead, its planning graph provides a polynomial-sized approximation that summarizes reachable facts and actions over time, upon which it performs a structured search.