Search
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 Propositional representation STRIPS, FDR.
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
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:
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
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.
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):
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
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$.
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):
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$.
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$.
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
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)$.
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$.