courses:pui:tutorials:tutorial06 [CourseWare Wiki]

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:

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