Doing the pattern databases extra credit task..

[Subbarao Kambhampati <rao@parichaalak.eas.asu.edu>]

three people asked me about how to do pattern databases extra credit
task. 

We discussed pattern databases only briefly on the 2nd class of week
3. 

The text discusses this idea in page 108-109. A slightly longer
description can be found in the 2nd page (from the bottom of first
column) in the reading list paper

 http://rakaposhi.eas.asu.edu/korf-search.pdf

In essence, you concentrate on getting a subset (typicaly a full
L-corner) of the tiles in correct position, ignoring the identity of
all tiles.

Suppose our goal is to get to state

1 2 3 
4 0 5
6 7 8

then we know that any solution that gets you from a state s to the
goal state will have to, as part of that path, get the corner 

    3
    5
6 7 8

correct. 

So, if we act as if 1, 2 and 4 are all indistinguishable (say they are 
all white tiles), and consider the number of moves needed to get from
a given state s (with white tiles, and 3,5,6,7,8 in some random
positions) into a state where 3,5,6,7,8 form the corner fringe, this
number will be a _lower bound_ on the actual cost of going from s to
goal state. 

The pattern database idea is to compute, generally a priori, these
distances for all states (i.e., all configurations of 3,5,6,7,8). When 
you need to estimate the heuristic value of a state, we look up the
pattern database table. 

The computation of this distance essentially involves sovling a
(simpler) version of the 8 puzzle problem. 

Although the best way to compute the pattern database heuristic is to
do a breadth first search back from the goal state, for your extra
credit task, you can just compute the distances on demand  (so you can 
initialize the pattern database table with nulls, and when you compute a distance for a 
state, put the value in for latter use). 


Hope this helps... If you need further help, come see me.

Rao