===== 6. LM-Cut heuristic ====

**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=\{c,d,e\}$,
  * $A=\{o_1,o_2,o_3,o_4\}$

^ action ^ pre ^ add ^ cost ^
| $o_1$ | $\{a\}$ | $\{b,c\}$ | $3$ |
| $o_2$ | $\{a\}$ | $\{d\}$ | $5$ |
| $o_3$ | $\{b\}$ | $\{c,d\}$ | $1$ |
| $o_4$ | $\{a,b\}$ | $\{e\}$ | $4$ |

In the following exercises, we will compute LM-Cut at $s_0$. As the first step, construct the STRIPS task $\Pi_{s_0}$ extended by new facts $\bot,\top$ so that $\{\bot\}$ will be the new initial state and $\{\top\}$ the new goal state.

++++ Solution|
The STRIPS task $\Pi_{s_0}=\langle F\cup\{\bot,\top\}, A\cup\{a_\bot,a_\top\}, \{\bot\}, \{\top\}\rangle$. The action $a_\bot$ handles the new initial state. Its preconditions $\mathsf{pre}_{a_\bot}=\{\bot\}$ and its add effects $\mathsf{add}_{a_\bot}=s_0=\{a\}$. 
The action $a_\top$ handles the new goal. Its preconditions $\mathsf{pre}_{a_\top}=g=\{c,d,e\}$ and its add effects $\mathsf{add}_{a_\top}=\{\top\}$. 
The new actions have zero cost, i.e., $\mathsf{cost}(a_\bot)=\mathsf{cost}(a_\top)=0$.

^ action ^ pre ^ add ^ cost ^
| $a_\bot$ | $\{\bot\}$ | $\{a\}$ | $0$ |
| $a_\top$ | $\{c,d,e\}$ | $\{\top\}$ | $0$ |

++++

**Exercise 2:**
Compute the fixed point of $\Gamma_{max}$ for the new initial state $\{\bot\}$ and construct the justification graph for the precondition choice function that selects for an action $a$ its most expensive fact $p\in\mathsf{pre}_a$ based on the fixed point.

++++ Solution|

^ $\bot$ ^ $a$ ^ $b$ ^ $c$ ^ $d$ ^ $e$ ^ $\top$ ^
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $5$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $4$ | $7$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $4$ | $7$ | $7$ |

Thus $h^{max}(\{\bot\})=7$.

The choice function $\mathsf{chf}\colon A\to F$ selecting the most expensive precondition is defined as follows:

^ action ^ $o_1$ ^ $o_2$ ^ $o_3$ ^ $o_4$ ^ $a_\bot$ ^ $a_\top$ ^
| $\mathsf{chf}$ | $a$ | $a$ | $b$ | $b$ | $\bot$ | $e$ |

The justification graph is shown below:

{{ :courses:pui:tutorials:justification1.png?500 |}}
++++

**Exercise 3:** Find the $\bot$-$\top$-cut in the justification graph, its action landmark, its contribution to the LM-Cut heuristic, and the remaining cost function after subtracting the saturated cost for the landmark.

++++ Solution|
First, we must find the facts from which $\top$ is reachable with zero cost. These are $V_\top=\{e,\top\}$. Next, we look for all the facts reachable 
from $\bot$ without passing through $V_\top$. These are $U_\bot=\{\bot,a,b,c,d\}$. $U_\bot$ is a $\bot$-$\top$-cut and its corresponding action landmark is $\{o_4\}$. The contribution to the heuristic is $\mathsf{cost}(o_4)=4$. The remaining cost function is

^ action ^ $o_1$ ^ $o_2$ ^ $o_3$ ^ $o_4$ ^ $a_\bot$ ^ $a_\top$ ^
| $\mathsf{cost}$ | $3$ | $5$ | $1$ | $0$ | $0$ | $0$ |

++++

**Exercise 4:** Do the next iteration of LM-Cut computation.

++++ Solution|
We must recompute the fixed point of $\Gamma_{max}$ for the remaining cost function and construct the new justification graph for the new precondition choice function.

The new fixed point is:

^ $\bot$ ^ $a$ ^ $b$ ^ $c$ ^ $d$ ^ $e$ ^ $\top$ ^
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $5$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $4$ | $3$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $4$ | $3$ | $4$ |

Thus $h^{max}(\{\bot\})=4$. The new precondition choice function is:

^ action ^ $o_1$ ^ $o_2$ ^ $o_3$ ^ $o_4$ ^ $a_\bot$ ^ $a_\top$ ^
| $\mathsf{chf}$ | $a$ | $a$ | $b$ | $b$ | $\bot$ | $d$ |

The new justification graph is:

{{ :courses:pui:tutorials:justification2.png?500 |}}

Next, we must find the facts from which $\top$ is reachable with zero cost. These are $V_\top=\{d,\top\}$. Next, we look for all the facts reachable 
from $\bot$ without passing through $V_\top$. These are $U_\bot=\{\bot,a,b,c,e\}$. $U_\bot$ is a $\bot$-$\top$-cut and its corresponding action landmark is $\{o_2,o_3\}$. The contribution to the heuristic is $\mathsf{cost}(o_3)=1$. The remaining cost function is

^ action ^ $o_1$ ^ $o_2$ ^ $o_3$ ^ $o_4$ ^ $a_\bot$ ^ $a_\top$ ^
| $\mathsf{cost}$ | $3$ | $4$ | $0$ | $0$ | $0$ | $0$ |

++++

**Exercise 5:** Do the final iteration of the LM-Cut heuristic and compute its final value.

++++ Solution|
We must again recompute the fixed point of $\Gamma_{max}$ for the remaining cost function and construct the new justification graph for the new precondition choice function.

The new fixed point is:

^ $\bot$ ^ $a$ ^ $b$ ^ $c$ ^ $d$ ^ $e$ ^ $\top$ ^
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $4$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $3$ | $3$ | $\infty$ |
| $0$ | $0$ | $3$ | $3$ | $3$ | $3$ | $3$ |

Thus $h^{max}(\{\bot\})=3$. 
Now, the preconditions of $a_\top$ have all the same cost so that the choice function can choose any of them. We will select $d$ as I can reuse the picture of the justification graph. The new precondition choice function is:

^ action ^ $o_1$ ^ $o_2$ ^ $o_3$ ^ $o_4$ ^ $a_\bot$ ^ $a_\top$ ^
| $\mathsf{chf}$ | $a$ | $a$ | $b$ | $b$ | $\bot$ | $d$ |

Thus the justification graph is again:

{{ :courses:pui:tutorials:justification2.png?500 |}}

Next, we must find the facts from which $\top$ is reachable with zero cost. These are $V_\top=\{b,d,\top\}$. Next, we look for all the facts reachable 
from $\bot$ without passing through $V_\top$. These are $U_\bot=\{\bot,a,c\}$. $U_\bot$ is a $\bot$-$\top$-cut and its corresponding action landmark is $\{o_1,o_2\}$. The contribution to the heuristic is $\mathsf{cost}(o_1)=3$. The remaining cost function is

^ action ^ $o_1$ ^ $o_2$ ^ $o_3$ ^ $o_4$ ^ $a_\bot$ ^ $a_\top$ ^
| $\mathsf{cost}$ | $0$ | $1$ | $0$ | $0$ | $0$ | $0$ |

Now the fixed point for the remaining cost function is:
^ $\bot$ ^ $a$ ^ $b$ ^ $c$ ^ $d$ ^ $e$ ^ $\top$ ^
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $0$ | $0$ | $1$ | $\infty$ | $\infty$ |
| $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $\infty$ |
| $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ |

Thus $h^{max}(\{\bot\})=0$, and the computation of LM-Cut stops. The final heuristic value is the sum of all the contributions, i.e., 
$4+1+3=8$.

++++