Graphplan

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.

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.