Exercise 1: Find an LTS $\Theta=\langle S,A,T,G\rangle$ and a heuristic $h\colon S\to\mathbb{R}_0^+\cup\{\infty\}$ which is admissible but not consistent. Make the LTS $\Theta$ so that GBFS fails to find an optimal $s_0$-plan for an initial state $s_0$.
Solution
The simplest example of an LTS and an admissible and non-consistent heuristic is simply an LTS built on a chain $a\to b\to c$ where $c$ is the only goal state. Suppose that the transitions cost $1$. Then $h(a)=2$, $h(b)=0$, $h(c)=0$ is an admissible heuristic that is not consistent because $h(a)-h(b)=2-0=2>1$. However, this simple LTS and the heuristic cannot puzzle GBFS, as only a single path goes from $a$ to $c$.
Consider the following LTS $\Theta=\langle S,A,T,G\rangle$ where $S=\{a,b,c,d\}$, $A=\{\alpha,\beta,\gamma,\delta\}$, $G=\{d\}$, and the transitions $T$ are shown in the digraph below:
The costs of the actions are defined:
action | $\alpha$ | $\beta$ | $\gamma$ | $\delta$ |
cost | 1 | 1 | 3 | 2 |
The heuristic $h$ is defined:
state | $a$ | $b$ | $c$ | $d$ |
$h$ | 3 | 3 | 0 | 0 |
It is easy to check that $h$ is admissible. To see that it is not consistent, consider the transition $\langle b,\beta,c\rangle\in T$. We have $h(b)-h(c)=3-0=3> \mathsf{cost}(\beta)$.
Exercise 2: Let $\Theta$ be your above LTS and $h$ the admissible non-consistent heuristic. Choose an initial state and consider the algorithms GBFS and A$^*$. Show how the data structures that keep the state of their computation change in every iteration.
Solution
As an initial state, we choose $a\in S$. GBFS employs two data structures to keep its state of the computation: the priority queue $Open$ for states to be expanded, a set $Closed$ for already expanded states, and $Parent$ storing for each expanded state its predecessor and action.
The elements of the priority queue are pairs of the form $(p,s)$ where $p$ is the priority and $s$ is a state.
Iteration | $Open$ | $Closed$ | $Parent$ |
0 | $\{(3,a)\}$ | $\emptyset$ | $\emptyset$ |
1 | $\{(0,c),(3,b)\}$ | $\{a\}$ | $Parent(b)=(a,\alpha)$, $Parent(c)=(a,\gamma)$ |
2 | $\{(0,d),(3,b)\}$ | $\{a,c\}$ | $Parent(b)=(a,\alpha)$, $Parent(c)=(a,\gamma)$, $Parent(d)=(c,\delta)$ |
In the final iteration, the goal state $d$ is removed from $Open$, and the algorithm terminates.
Thus the plan returned by GBFS is $\pi=\gamma,\delta$ and $\mathsf{cost}(\pi)=3+2=5$, i.e., non-optimal plan.
A$^*$ replaces $Closed$ with gScores.
Iteration | $Open$ | $gScores$ | $Parent$ |
0 | $\{(3,a)\}$ | $g(a)=0$, $g(b)=\infty$, $g(c)=\infty$, $g(d)=\infty$ | $\emptyset$ |
1 | $\{(3,c),(4,b)\}$ | $g(a)=0$, $g(b)=1$, $g(c)=3$, $g(d)=\infty$ | $Parent(b)=(a,\alpha)$, $Parent(c)=(a,\gamma)$ |
2 | $\{(4,b),(5,d)\}$ | $g(a)=0$, $g(b)=1$, $g(c)=3$, $g(d)=5$ | $Parent(b)=(a,\alpha)$, $Parent(c)=(a,\gamma)$, $Parent(d)=(c,\delta)$ |
3 | $\{(2,c),(5,d)\}$ | $g(a)=0$, $g(b)=1$, $g(c)=2$, $g(d)=5$ | $Parent(b)=(a,\alpha)$, $Parent(c)=(b,\beta)$, $Parent(d)=(c,\delta)$ |
4 | $\{(4,d)\}$ | $g(a)=0$, $g(b)=1$, $g(c)=2$, $g(d)=4$ | $Parent(b)=(a,\alpha)$, $Parent(c)=(b,\beta)$, $Parent(d)=(c,\delta)$ |
Note that the 2nd iteration expands the state $b$ and must reopen $c$ again as the path through $b$ is cheaper than the direct path from $a$.
In the 3rd iteration, the algorithm expands $c$, finds a cheaper path to $d$, and updates the priority of $d$ in $Open$.
In the final iteration, the goal state $d$ is removed from $Open$, and the algorithm terminates.
Thus the plan returned by A$^*$ is $\pi^*=\alpha,\beta,\delta$ and $\mathsf{cost}(\pi)=1+1+2=4$, i.e., the optimal plan.