Search
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
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)$.
We will iteratively apply the operator $\Gamma_{max}$ to solve the exercise.
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)$.
Unlike the $h^{max}$, we must sum the values of the preconditions instead of taking their maximum.
Thus $h^{add}(s_0)=4+8=12$.
Exercise 4: Consider the following STRIPS task $\Pi=\langle F,A,s_0,g\rangle$ where
Compute $h^*(s_0)$, $h^{max}(s_0)$, and $h^{add}(s_0)$.
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:
We have $h^{max}(s_0)=\max\{7, 6\}=7$.
For $h^{add}$ we have the following computation:
Thus $h^{add}(s_0)=9+8=17$.