Progression and Regression Search

Source slide: C2 Progression and Regression Search

Explicit search still leaves an important design choice open: which direction should the search go? A planner can start from the initial state and move forward through applicable operators, or it can start from the goal description and reason backward about what must have been true before the last action.

These two choices are called progression and regression. They solve the same planning task, but their search states have different meanings.

Progression Search

Progression is forward search. Its search states are ordinary world states: complete truth assignments over the planning variables. From a state $s$, the planner applies an applicable operator $o$ and generates the successor state $s\llbracket o\rrbracket$.

For a task $\Pi=\langle V,I,O,\gamma\rangle$, the progression interface is:

• init() returns $I$;
• is_goal(s) tests whether $s \models \gamma$;
• succ(s) returns each pair $\langle o,s\llbracket o\rrbracket\rangle$ such that $o$ is applicable in $s$;
• cost(o) returns $\mathit{cost}(o)$.

This is the most direct implementation of the induced transition system. The nodes of the search graph are the states of the planning task, and the edges are operator applications.

How to Read a Progression Step

Suppose the current state satisfies the precondition of an operator $o$. Progression asks only one local question:

What state results if $o$ is executed now?

The answer is determined by the operator semantics from the formal-definition chapter. Preconditions are checked in the current state, effects fire according to their effect conditions, and unaffected variables keep their values.

Progression is simple and efficient because successor generation is concrete. Given $s$ and $o$, there is at most one resulting state. The drawback is that the search may branch over many applicable operators and may still need to visit a large number of individual states.

Regression Search

Regression is backward search, but backward search in planning is not just forward search with arrows reversed. The reason is that the goal is usually not a single complete state. It is a formula $\gamma$ that describes a set of acceptable states.

So regression search states are formulas, often called subgoals. A subgoal $\varphi$ represents all world states that satisfy $\varphi$. Regressing $\varphi$ over an operator $o$ asks:

What must have been true before applying $o$ so that $\varphi$ is true afterward?

The high-level regression interface is:

• init() returns the goal formula $\gamma$;
• is_goal(\varphi) tests whether $I \models \varphi$;
• succ(\varphi) returns predecessor subgoals $\mathit{regr}(\varphi,o)$ for relevant operators $o$;
• cost(o) returns $\mathit{cost}(o)$.

A solution is found when the backward search reaches a subgoal that is already true in the initial state. Reading the resulting operator sequence in the forward direction gives a plan.

Why Regression Is Harder in General

Regression can be attractive because one formula may represent many states. The formula $delivered \land paid$, for instance, represents every complete state where both atoms hold, regardless of all unrelated variables.

The cost is that search operations become logical operations. Duplicate detection may require asking whether two formulas describe the same set of states. Pruning may require checking entailment. These problems can be NP-complete or coNP-complete for general formulas.

This is why the course immediately pays attention to STRIPS regression. STRIPS keeps subgoals in a very simple syntactic form: conjunctions of atoms.

STRIPS Regression

Assume $\varphi$ is a conjunction of atoms:

$$\varphi = \varphi_1 \land \cdots \land \varphi_n$$

Let $o$ be a STRIPS operator with add effects $a_1,\ldots,a_k$ and delete effects $d_1,\ldots,d_l$. The STRIPS regression of $\varphi$ over $o$ is:

$$\mathit{sregr}(\varphi,o) := \begin{cases} \bot & \text{if }\varphi_i = d_j\text{ for some }i,j \\ \mathit{pre}(o) \land \bigwedge(\{\varphi_1,\ldots,\varphi_n\}\setminus\{a_1,\ldots,a_k\}) & \text{otherwise.} \end{cases}$$

This formula is easier to read as an algorithm.

1. Check whether $o$ deletes anything required by $\varphi$. If it does, $o$ cannot be the last action for this subgoal, so regression returns $\bot$.
2. Remove from $\varphi$ the atoms that $o$ adds. Those atoms need not be true before $o$, because $o$ will make them true.
3. Add the preconditions of $o$. They must be true before $o$ can be applied.

The result is again a conjunction of atoms, unless regression fails. That closure property is the main reason STRIPS regression is clean.

A Small Regression Example

Suppose the current subgoal is:

$$delivered \land paid$$

Consider an operator deliver with:

$$\mathit{pre}(deliver) = in\_truck \land at\_destination$$ $$\mathit{add}(deliver)=\{delivered\}$$ $$\mathit{del}(deliver)=\{in\_truck\}$$

The operator does not delete $delivered$ or $paid$, so it is not rejected by the conflict check. It adds $delivered$, so that atom is removed from the subgoal. Its preconditions are then added. The regressed subgoal is:

$$in\_truck \land at\_destination \land paid$$

This means: if, before executing deliver, the package is in the truck, the truck is at the destination, and payment has already been made, then after executing deliver, the original subgoal $delivered \land paid$ will hold.

Now suppose deliver deleted $paid$. Then it could not be the final action for the subgoal $delivered \land paid$, because it would destroy something the goal needs. Regression would return $\bot$.

The Regression Property

The correctness of STRIPS regression is captured by the regression property:

$$s \models \mathit{sregr}(\varphi,o) \quad\text{if and only if}\quad s\llbracket o\rrbracket \models \varphi.$$

The left side talks about the state before applying $o$. The right side talks about the state after applying $o$. The property says that the regressed formula is exactly the weakest kind of subgoal we need before $o$ for $\varphi$ to hold afterward, within the STRIPS setting used here.

This equivalence is what makes backward search meaningful. If a backward path reaches a formula true in the initial state, then applying the selected operators forward will satisfy each later subgoal and finally the original goal.

Choosing a Direction

Progression and regression expose different structure.

Progression is usually straightforward to implement because it works with concrete states and concrete successor generation. It can use standard graph-search machinery directly.

Regression can focus on facts relevant to the goal. Instead of considering all consequences of actions from the initial state, it asks which actions could have achieved the current subgoal. In STRIPS, it is common to consider only operators that add at least one atom in the current subgoal.

The trade-off is that regression search states are formulas, not world states. In general planning this makes the machinery more expensive. In STRIPS, the formula shape stays simple enough that regression becomes a practical concept to study.

What Can Go Wrong

A common mistake is to remove delete effects from the subgoal in the same way as add effects. That is backwards. If an operator deletes an atom required by the subgoal, the operator conflicts with being the last step and regression fails.

Another mistake is to forget that regression produces a condition on the predecessor state. The regressed formula is not what becomes true after the operator; it is what must already be true before the operator.

Finally, progression and regression do not necessarily explore the same intermediate objects. Progression visits complete states. Regression visits formulas that denote sets of states. This difference affects duplicate detection, pruning, and heuristic design.

Chapter Summary

Progression search moves forward from the initial state through concrete world states. Regression search moves backward from the goal through formulas that describe sets of possible predecessor states. General regression requires logical reasoning over formulas, which can be expensive. For STRIPS tasks, regression has a simple form: reject operators that delete required atoms, remove atoms achieved by the operator, and add the operator preconditions. The regression property connects the backward formula to the forward execution semantics.

Check Your Understanding

1. What is the search state in progression, and what is the search state in regression?
2. Why is backward search in planning not just the reverse of forward search?
3. In STRIPS regression, why are added atoms removed from the subgoal?
4. What does it mean when $\mathit{sregr}(\varphi,o)=\bot$?
5. How does the regression property justify using backward search to find a forward plan?