courses:pui:tutorials:tutorial04 [CourseWare Wiki]

4. Delete relaxation heuristics

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

$F=\{a,b,c,d,e\}$,
$s_0 = \{a\}$,
$g = \{b,e\}$,
$A = \{o_1,o_2,o_3,o_4\}$ defined in the table below:

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

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$.