This tutorial focuses on the computation of the heuristics $h^{max}$ and $h^{add}$ based on delete relaxation.
As these heuristics first compute the delete relaxation of a STRIPS task $\Pi$, we will consider here only delete-free STRIPS tasks $\Pi$, i.e., $\Pi=\Pi^+$ and $h^*=h^+$. Thus, all the actions have empty delete effects.
Exercise 1: Consider the following STRIPS task $\Pi=\langle F,A,s_0,g\rangle$ where
action | pre | add | cost |
$o_1$ | $\emptyset$ | $\{b,c\}$ | $4$ |
$o_2$ | $\{a\}$ | $\{c\}$ | $2$ |
$o_3$ | $\{a,c\}$ | $\{d\}$ | $3$ |
$o_4$ | $\{c,d\}$ | $\{e\}$ | $1$ |
Compute the perfect heuristic $h^*$ for the initial state, i.e., $h^*(s_0)$.
Solution
The optimal $s_0$-plan is $\pi=o_1,o_2,o_3,o_4$ generating the following sequence of states:
$s_0=\{a\} \stackrel{o_1}{\longrightarrow} \{a,b,c\} \stackrel{o_3}{\longrightarrow} \{a,b,c,d\} \stackrel{o_4}{\longrightarrow} \{a,b,c,d,e\}$
Thus $h^*(s_0)=\mathsf{cost}(o_1) + \mathsf{cost}(o_3) + \mathsf{cost}(o_4) = 8$.
Exercise 2:
For the STRIPS task from the previous exercise, compute the $h^{max}$ heuristic for the initial state $s_0$, i.e., $h^{max}(s_0)$.
Solution
We will iteratively apply the operator $\Gamma_{max}$ to solve the exercise.
iteration | $a$ | $b$ | $c$ | $d$ | $e$ |
$0$ | $0$ | $4$ | $4$ | $\infty$ | $\infty$ |
$1$ | $0$ | $4$ | $2$ | $7$ | $\infty$ |
$2$ | $0$ | $4$ | $2$ | $5$ | $8$ |
$3$ | $0$ | $4$ | $2$ | $5$ | $6$ |
0th row: We get the initial values from the initial state and actions with empty preconditions. That's why $a$ has value $0$ and $b,c$ has value $4$ as it can be produced by $o_1$. The remaining facts are assigned to $\infty$.
ith row: To compute the values in the ith row, we need to iterate through every action $a$, compute the maximum $m$ of its preconditions $\mathsf{pre}_a$ in the (i-1)th row, and add the action cost $\mathsf{cost}(a)$ to $m$. This gives us a new possible value $v_a$ for each action's add-effect $q\in\mathsf{add}_a$. Finally, the new value for $q$ in the ith row is the minimum of all $v_a$'s and the value $q$ has in the (i-1)th row. In this process, we can obviously skip every action if any of its preconditions have the value $\infty$ in the (i-1)th row.
For example, consider the 1st row. The only actions without infinite preconditions in the 0-th row are $o_1,o_2,o_3$. $o_1$ does not generate any lower values for $b,c$. The maximum of the preconditions of $o_2$ is $0$. Thus $c$ can get the value $2=0+\mathsf{cost}(o_2)<4$. Finally, the maximum of the preconditions of $o_3$ is $4$. Hence $d$ gets $7=4+\mathsf{cost}(o_3)<\infty$.
Note that in the 2nd row, the value of $d$ is improved because the cost of the preconditions of $o_3$ was improved in the 1st row. Similarly, the value of $e$ gets better in the final row. Thus, 2nd row is not the fixed point of $\Gamma_{max}$.
Finally, we have $h^{max}(s_0)=\max\{4, 6\}=6$.
Exercise 3: For the STRIPS task from Exercise 1, compute $h^{add}(s_0)$.
Solution
Unlike the $h^{max}$, we must sum the values of the preconditions instead of taking their maximum.
iteration | $a$ | $b$ | $c$ | $d$ | $e$ |
$0$ | $0$ | $4$ | $4$ | $\infty$ | $\infty$ |
$1$ | $0$ | $4$ | $2$ | $7$ | $\infty$ |
$2$ | $0$ | $4$ | $2$ | $5$ | $10$ |
$3$ | $0$ | $4$ | $2$ | $5$ | $8$ |
Thus $h^{add}(s_0)=4+8=12$.
Exercise 4: Consider the following STRIPS task $\Pi=\langle F,A,s_0,g\rangle$ where
$F=\{a,b,c,d,e\}$,
$s_0 = \{a\}$,
$g = \{d,e\}$,
$A = \{o_1,o_2,o_3,o_4,o_5\}$ defined in the table below:
action | pre | add | cost |
$o_1$ | $\emptyset$ | $\{b\}$ | $2$ |
$o_2$ | $\{a\}$ | $\{b,c\}$ | $4$ |
$o_3$ | $\{a,b,c\}$ | $\{d,e\}$ | $3$ |
$o_4$ | $\{b,c\}$ | $\{e\}$ | $2$ |
$o_5$ | $\{e\}$ | $\{b,c\}$ | $2$ |
Compute $h^*(s_0)$, $h^{max}(s_0)$, and $h^{add}(s_0)$.
Solution
The optimal $s_0$-plan is $\pi=o_2,o_3$ generating the following sequence of states:
$s_0=\{a\} \stackrel{o_2}{\longrightarrow} \{a,b,c\} \stackrel{o_3}{\longrightarrow} \{a,b,c,d,e\}$
Thus $h^*(s_0)=\mathsf{cost}(o_2) + \mathsf{cost}(o_3) = 7$.
For $h^{max}$ we have the following computation:
iteration | $a$ | $b$ | $c$ | $d$ | $e$ |
$0$ | $0$ | $2$ | $\infty$ | $\infty$ | $\infty$ |
$1$ | $0$ | $2$ | $4$ | $\infty$ | $\infty$ |
$2$ | $0$ | $2$ | $4$ | $7$ | $6$ |
We have $h^{max}(s_0)=\max\{7, 6\}=7$.
For $h^{add}$ we have the following computation:
iteration | $a$ | $b$ | $c$ | $d$ | $e$ |
$0$ | $0$ | $2$ | $\infty$ | $\infty$ | $\infty$ |
$1$ | $0$ | $2$ | $4$ | $\infty$ | $\infty$ |
$2$ | $0$ | $2$ | $4$ | $9$ | $8$ |
Thus $h^{add}(s_0)=9+8=17$.