===== 9. Pattern databases =====

Recall that a pattern database is an abstraction heuristic defined for an FDR task $\Pi=\langle V,A,s_0,g\rangle$ induced by a projection $\pi_P$ for a subset of variables $P\subseteq V$. The projection $\pi_P$ maps a state $s$ (i.e., a function on the variables $V$) to its restriction on $P$. 
One can also generalize $\pi_P$ to act on a partial state $s$ by
\[\pi_P(s)(v)=\begin{cases}
s(v) & \text{if }s(v)\text{ is defined and }v\in P,\\
\text{undefined} & \text{otherwise.} \\
\end{cases}
\]

The transition system corresponding to the projection $\pi_P$ has a nice representation as it can be specified as an FDR task $\Pi_P=\langle P,A_P,\pi_P(s_0),\pi_P(g)\rangle$ where the actions are defined as follows:
\[A_P = \{\pi_P(a)=\langle \pi_P(\mathsf{pre}_a),\pi_P(\mathsf{eff}_a)\rangle\mid a=\langle\mathsf{pre}_a,\mathsf{eff}_a\rangle\in A\}\]
Thus, $\pi_P(a)$ is simply created from $a$ by removing all variables not belonging to $P$ from the precondition and effect.

Consider the example from the tutorial [[courses:pui:tutorials:tutorial03|Propositional representation STRIPS, FDR]].

{{ :courses:pui:tutorials:blocks.png?400 |}}

Its FDR representation $\Pi=\langle V,A,s_0,g\rangle$ where $V=\{v_A,v_B,v_C,c_A,c_B,c_C\}$ with the domains

^ variable ^ domain ^
| $v_A$ | $\{on(A,B),on(A,C),on(A,T)\}$ |
| $v_B$ | $\{on(B,A),on(B,C),on(B,T)\}$ |
| $v_C$ | $\{on(C,A),on(C,B),on(C,T)\}$ |
| $c_A$ | $\{0,1\}$ |
| $c_B$ | $\{0,1\}$ |
| $c_C$ | $\{0,1\}$ |

The initial state $s_0$ is 
\[s_0=\{(v_A,on(A,T)),(v_B,on(B,T)),(v_C,on(C,A)),(c_A,0),(c_B,1),(c_C,1)\}.\] 
The goal is the partial function
\[g=\{(v_A,on(A,B)),(v_B,on(B,C)),(v_C,on(C,T))\}.\]

Finally, for each pair of different blocks $X,Y\in\{A,B,C\}$, we have actions $stack(X,Y)$ and $unstack(X,Y)$. The preconditions and effects are defined as follows:

^ action ^ precondition ^ effect ^
| stack(X,Y) | $\{(v_X,on(X,T)),(c_X,1),(c_Y,1)\}$ | $\{(v_X,on(X,Y)),(c_Y,0)\}$ |
| unstack(X,Y) | $\{(v_X,on(X,Y)),(c_X,1)\}$ | $\{(v_X,on(X,T)),(c_Y,1)\}$ |

We will assume that all the actions have the cost $1$.

**Exercise 1:** Draw the LTS induced by the projection $\pi_P$ for $P=\{v_B\}$ and compute the heuristic $h_P$ for $s_0$ and 
the state $s$ defined by 

^ $v_A$ ^ $v_B$ ^ $v_C$ ^ $c_A$ ^ $c_B$ ^ $c_C$ ^
| $on(A,T)$ | $on(B,A)$ | $on(C,B)$ | $0$ | $0$ | $1$ |

++++ Solution|
By restricting everything to $v_B$, we get
\[s_0=\{(v_B,on(B,T))\}\qquad g=\{(v_B,on(B,C))\}\]

For the actions stack(X,Y) and unstack(X,Y) we must distinguish whether $X=B$ or not.
^ action ^ precondition ^ effect ^
| stack(B,Y) | $\{(v_B,on(B,T))\}$ | $\{(v_B,on(B,Y))\}$ |
| unstack(B,Y) | $\{(v_B,on(B,Y))\}$ | $\{(v_B,on(B,T))\}$ |
| stack(X,Y), $X\neq B$ | $\emptyset$ | $\emptyset$ |
| unstack(X,Y), $X\neq B$ | $\emptyset$ | $\emptyset$ |

Thus, the actions stack(X,Y) and unstack(X,Y) for $X\neq B$ do nothing and correspond to self-loops on states in the corresponding LTS. The LTS looks as follows (the self-loops are omitted):

{{ :courses:pui:tutorials:pib.png?600 |}}

The initial state is $\{on(B,T)\}$ and there is only a single goal state $\{on(B,C)\}$. 

For the heuristic values, we have $h_P(s_0)=h^*(\pi_P(s_0))=h^*(\{(v_A,on(B,T))\})=1$ and $h_P(s)=h^*(\pi_P(s))=h^*(\{(v_B,on(B,A)\})=2$, where $h^*$ is the perfect heuristic for the above shown LTS.
++++

**Exercise 2:** Draw the LTS induced by the projection $\pi_P$ for $P=\{v_A,c_A\}$ and compute the heuristic $h_P$ for $s_0$ and 
the state $s$ defined by 

^ $v_A$ ^ $v_B$ ^ $v_C$ ^ $c_A$ ^ $c_B$ ^ $c_C$ ^
| $on(A,C)$ | $on(B,A)$ | $on(C,T)$ | $0$ | $1$ | $0$ |

++++ Solution|
By restricting everything to $\{v_A,c_A\}$, we get
\[s_0=\{(v_A,on(A,T)),(c_A,0)\}\qquad g=\{(v_A,on(A,B))\}\]

For the actions stack(X,Y) and unstack(X,Y) we must distinguish several cases: $X=A$, $Y=A$, and $X,Y\neq A$.
^ action ^ precondition ^ effect ^
| stack(A,Y) | $\{(v_A,on(A,T)),(c_A,1)\}$ | $\{(v_A,on(A,Y))\}$ |
| unstack(A,Y) | $\{(v_A,on(A,Y))),(c_A,1)\}$ | $\{(v_A,on(A,T))\}$ |
| stack(X,A), $X\neq A$  | $\{(c_A,1)\}$ | $\{(c_A,0)\}$ |
| unstack(X,A), $X\neq A$ | $\emptyset$ | $\{(c_A,1)\}$ |
| stack(X,Y), $X,Y\neq A$ | $\emptyset$ | $\emptyset$ |
| unstack(X,Y), $X,Y\neq A$ | $\emptyset$ | $\emptyset$ |

Thus, the actions stack(X,Y) and unstack(X,Y) for $X,Y\neq A$ do nothing and correspond to self-loops on states in the corresponding LTS. The LTS looks as follows (the self-loops are omitted):

{{ :courses:pui:tutorials:piac.png?600 |}}

The states in the abstract LTS are, for simplicity, represented as pairs of values, e.g., $\{(v_A,on(A,T)),(c_A,1)\}$ is denoted $on(A,T),1$.
The arrows denoted stack(X,A) (resp. unstack(X,A)) represents two transitions for $X\in\{B,C\}$. The initial state (the orange one) is $on(A,T),0$.
There are two goal states $on(A,B),0$ and $on(A,B),1$.

For the heuristic values, we have $h_P(s_0)=h^*(\pi_P(s_0))=h^*(\{(v_A,on(A,T)),(c_A,0)\})=2$ and $h_P(s)=h^*(\pi_P(s))=h^*(\{(v_A,on(A,C)),(c_A,0)\})=3$, where $h^*$ is the perfect heuristic for the above shown LTS.

++++

**Exercise 3:** Consider an FDR task $\Pi=\langle V,A,s_0,g\rangle$ whose LTS models a binary counter from $0$ to $15$. It has four variables 
$V=\{v_0,v_1,v_2,v_3\}$ with domains $\mathsf{dom}(v_i)=\{0,1\}$. So, the states correspond to 4-bit binary numbers. E.g., 
$\{(v_0,0),(v_1,1),(v_2,0),(v_3,1)\}$ represents the number $1010$ (i.e., $v_i$ represents the $i$-th bit from the right). 
The actions $A=\{a_0,a_1,a_2,a_3,ch\}$ increment the binary number by one. We need several actions to do this. To make the exercise more interesting,
we add a cheating action $ch$, allowing us to move forward faster. We will denote a pair $(v,d)$ 
as $v=d$.

^ action ^ $\mathsf{pre}$ ^ $\mathsf{eff}$ ^ cost ^
| $a_0$ | $v_0=0$ | $v_0=1$ | $1$ |
| $a_1$ | $v_0=1$, $v_1=0$ | $v_0=0$, $v_1=1$ | $2$ |
| $a_2$ | $v_0=1$, $v_1=1$, $v_2=0$ | $v_0=0$, $v_1=0$, $v_2=1$ | $3$ |
| $a_3$ | $v_0=1$, $v_1=1$, $v_2=1$, $v_3=0$ | $v_0=0$, $v_1=0$, $v_2=0$, $v_3=1$ | $4$ |
| $ch$ | $v_0=0$, $v_1=0$ | $v_0=1$, $v_1=1$ | $2$ |

The initial state is $0000$, and the goal is specified by $v_3=1$, $v_1=1$. Thus, there are four goal states $G=\{1010, 1011, 1110, 1111\}$.
The optimal $s_0$-plan is the sequence $ch,a_2,ch,a_0,a_1$ of cost $14$.

Draw the LTS induced by the syntactic projection to $P=\{v_0,v_2,v_3\}$ and compute the heuristic for the initial state $s_0$.

++++ Solution|
We will denote the abstract states as $d_3d_2Xd_0$, e.g., $10X1$ denotes the state $v_3=1$, $v_2=0$, and $v_0=1$.
The actions in the syntactic projection are 

^ action ^ $\mathsf{pre}$ ^ $\mathsf{eff}$ ^ cost ^
| $\pi_P(a_0)$ | $v_0=0$ | $v_0=1$ | $1$ |
| $\pi_P(a_1)$ | $v_0=1$ | $v_0=0$ | $2$ |
| $\pi_P(a_2)$ | $v_0=1$, $v_2=0$ | $v_0=0$, $v_2=1$ | $3$ |
| $\pi_P(a_3)$ | $v_0=1$, $v_2=1$, $v_3=0$ | $v_0=0$, $v_2=0$, $v_3=1$ | $4$ |

Note that $\pi_P(ch)=\pi_P(a_0)$. Moreover, the cost of $a_0$ is smaller, so we keep only $\pi_P(a_0)$.

The LTS is shown below. The green states are the goal states and the yellow one is the initial. The actions are denoted for simplicity by their original names, e.g. $a_0$ instead of $\pi_P(a_0)$.

{{ :courses:pui:tutorials:counter.png?600 |}}

The heuristic for the initial state $s_0$ equals $9$ as the optimal $\pi_P(s_0)$-plan is $a_0,a_2,a_0,a_3$.
++++