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