Backward Search (Regression Planning)

Backward search is defined by its goal-directed nature. The algorithm begins with the complete set of goal conditions and searches for actions whose effects can satisfy them. It then recursively treats the preconditions of those actions as new sub-goals, regressing backward through the state space until it reaches the initial state. This contrasts with forward search, which expands from the initial state and can explore many irrelevant paths.

The core computational step is the regression operation. Given a goal set G (a set of logical propositions) and an action A, the algorithm calculates the regressed goal or preimage. This is a new set of sub-goals formed by:

• Removing from G any propositions added by A's add effects.
• Adding to G all propositions in A's preconditions.
• Ensuring no proposition deleted by A's delete effects is required in the new set. This operation efficiently prunes the search space by only considering actions relevant to the current goal.

A key advantage is its inherent focus on relevant actions. An action is only considered if at least one of its effects unifies with a current goal proposition. This avoids the exponential branching often seen in forward search. Furthermore, backward search naturally handles goal interactions—situations where achieving one sub-goal might undo another (negative interactions) or enable it (positive interactions). The regressive process must find an ordering that resolves these interactions to produce a consistent plan.

Backward search is most clearly defined within the STRIPS planning formalism. It operates on a lifted representation, meaning it works with partially instantiated actions and variables during search, only grounding them as necessary. This is more efficient than ground forward search. The algorithm maintains a regression search tree, where nodes are sets of sub-goals and edges are applications of the regression operation via a relevant action.

Backward search principles are central to modern planners like Graphplan. Graphplan's solution extraction phase is essentially a backward search over its planning graph structure. Similarly, the SATPlan approach encodes the planning problem into a Boolean satisfiability formula; the models found by the SAT solver implicitly define a backward-chaining proof that a sequence of actions leads from the initial state to the goal.

While efficient for many classical planning problems, backward search has limitations. It can struggle with problems involving numerical fluents or complex temporal constraints. It also requires the goal to be fully specified as a conjunction of logical facts. In practice, it is often used as a component within a broader planner (like in heuristic state-space planners such as FF or Fast Downward) where backward reasoning is used to compute powerful delete-relaxation heuristics like hFF or hAdd to guide a forward search.

The primary alternative paradigm to backward search. Forward search begins at the initial state and applies actions to generate successor states, exploring the state space forward until a goal state is reached.

• Contrast with Backward Search: Explores the reachable state space from the initial conditions, which can be inefficient if the goal is far away or the branching factor is high.
• Typical Use: Often used with heuristic functions to guide exploration (e.g., A* search).
• Key Challenge: Must reason about all possible future states, which can lead to exploring irrelevant parts of the state space.

The foundational representation for classical planning problems, within which backward search is often defined. STRIPS models the world with:

• States: Represented as sets of ground logical propositions that are true.
• Actions: Defined by preconditions (propositions that must be true to execute), add effects (propositions made true), and delete effects (propositions made false).
• Regression Defined: The regression of a goal through an action is computed by removing the action's add effects from the goal and adding its preconditions, provided the action's delete effects do not conflict with the goal.

A critical efficiency concept in backward search. When regressing from a goal state G, an action A is considered relevant if:

1. A's add effects intersect with G (it achieves some part of the goal).
2. A's delete effects do not delete any proposition in G (it does not undo another part of the goal).

Only relevant actions need to be considered when generating predecessor states, dramatically pruning the search space. This is a key advantage over forward search, which must consider all applicable actions.

The core output of a single regression step. Given a goal description G (a set of propositions) and an action A, the regression set is the predecessor state from which executing A would achieve (part of) G.

• Calculation: Regress(G, A) = (G \ Add(A)) ∪ Precond(A), provided Delete(A) ∩ G = {}.
• Interpretation: This set represents a subgoal—a state that must be reached so that applying action A will then achieve G.
• Search Tree: Nodes in a backward search tree are these regression sets (subgoals), and edges are the relevant actions that connect them.

A major challenge in backward search. Goal interactions occur when achieving one subgoal (e.g., Have(Milk)) deletes a proposition required for another (e.g., Have(Money)).

• Landmarks: A fact that must be true at some point in every valid plan. Backward search can leverage fact landmarks (e.g., Have(Money) must be true before Buy(Milk)) to impose necessary orderings.
• Ordering Constraints: Effective backward planners discover these implicit constraints to avoid generating inconsistent regression sets, guiding the search toward feasible subgoal orderings.

An alternative to state-space planning (forward/backward search). Plan-space planning searches through a space of partial plans, not states.

• Partial Plan: A set of action steps, temporal ordering constraints, and causal links (where one action achieves a precondition for another).
• Refinement: The planner iteratively refines a partial plan by adding actions to achieve open preconditions (flaws) and resolving threats (where an action might delete a needed condition).
• Relation to Backward Search: Can be viewed as a more flexible, lifted representation where backward chaining is used to add actions for achieving subgoals within the plan structure.