3. Heuristics

Search without Domain Heuristics

Fast Forward is a forward-chaining heuristic search-based planner. It uses the Relaxed Planning Graph (RPG) heuristic to guide search. This involves finding a plan from the current state $S$ which achieves goal $G$ but ignores the delete effects of each action. The length of this plan is used as a heuristic value.

The RPG is made of alternate fact and action layers.

• Fact layer $f(n)$ is used to determine which actions can appear in action layer $a(n+1)$. Preconditions satisfied in $f(n)$
• $f(n+1)=f(n)$ plus all the add effects of the actions in $a(n+1)$. (we ignore delete)
• Hence fact layers get bigger and bigger as more actions become applicable.

For each state $S$ reached during forward search, the length of the relaxed plan $P^{\prime }$ which achieves the goals $G$ starting from $S$ is computed. This is an estimate of the goal distance.

The relaxed solution plan $P^{\prime }=<O_0,O_1,\dots ,O_{m-1}>$, where each $O_i$ is the set of actions selected in parallel at time step $i$, and $m$ is the number of the first fact layer containing all goals. Hence the heuristic is the estimation of the sequential solution length, $h(s):=\sum |O_i|$.

Exploring RPG Heuristic

Building a Relaxed Planning Graph works as follows:

Note: actions in $A_2$ do not include actions from $A_1$.

To get a solution, we work backwards through the RPG.

• At each fact layer $f(n)$, we have goals to achieve $g(n)$.
• We start with $g(n)$ containing the problem goals, for each fact in $g(n)$:
  • If it was in $f(n-1)$, add it to $g(n-1)$
  • Otherwise, choose an action from $a(n)$ and add its preconditions to $g(n-1)$
• Stop when at $g(0)$