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