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