Symmetry in Pattern Databases

Question

I am trying to understand the use of symmetry in pattern databases (Heuristics, single agent search). This is too specialized of a topic to find common videos or explanations in general. I read the paper Pattern Databases by Joseph C. Culberson and Jonathan Schaeffer (University of Alberta) in Computational Intelligence, Volume 14, Number 3, 1998.

In the paper, they explain the different kinds of symmetries we can use on the 15-Sliding Tile Puzzle such as Horizontal, Vertical and Mirror. But what I do not understand is how exactly are we going to use those symmetrical configurations of a puzzle to find a good lower bound on the estimated cost of a state from the goal.

I would really appreciate if anybody can explain the process of using symmetry in pattern databases or can point toward a good explanation.

Answer 1

From your question I assume you understand how symmetries are computed. As an exercise, make sure to understand the example given in Figure 4 which refers to the easiest of all symmetries, the Mirror (also known as Diagonal) denoted as $D$. In the following I will refer to this symmetry only unless otherwise noted.

Next, hope you also understand that symmetries create isomorphic puzzles so that the number of moves necessary to optimally solve the reflected state is precisely the same number of moves (but different) necessary to optimally solve the original state ---see Figure 3 in the paper for a good example of a path reflection which results from applying $D$.

Hence, when computing the heuristic estimate of any state $p$, compute its symmetrical state $p'$ (in time linear in the size of the puzzle), and look up the Pattern Database for both states $p$ and $p'$. Since Pattern Databases are indeed homomorphisms let $\rho$ denote such mapping ---i.e., what tiles are mapped to themselves and what tiles are replaced by the don't care symbol. Thus, you can safely take the maximum of both values returned from the PDB:

$h(p)=\max\{V(\rho(p)), V(\rho(p'))\}$

where $V(n)$ denotes the value stored in the PDB for the abstracted state $n$ which consists of tiles and don't care symbols. The two values within brackets are indeed those mentioned at the beginning of Section 4.3.

Note the importance of the blank tile: The other symmetries H, V and D' do not preserve its location and therefore Section 4.2 proposes to use some corrections (3, 3, and 6 respectively) to both the lower and upper bounds.

Of all these symmetries, the most widely used are $D$ and $D'$. Other works (among many others) exploiting them are given below:

Richard E. Korf, Ariel Felner. Disjoint Pattern Database Heuristics. Artificial Intelligence, 134, pp. 9--22, 2002

Ariel Felner, Richard Korf, S. Hannan. Additive Pattern Database Heuristics. Journal of Artificial Intelligence Research, 22, pp. 279--318, 2004.

Uzi Zahavi, Ariel Felner, Robert C. Holte, Jonathan Schaeffer, Duality in Permutation State Spaces and the Dual Search Algorithm, Artificial Intelligence, 172 (4--5), pp. 514--540, 2008

To finish, let me reproduce here a paragraph from the last paper:

Because all valid, alternative PDB lookups provide lower bounds on the distance from state $S$ to $G$, their maximum can be taken as the value for $h(S)$. Of course, there is a tradeoff for doing this ---each PDB lookup increases the time it takes to compute $h(S)$. Because additional lookups provide diminishing returns in terms of the reduction in the number of nodes generated, it is not always best to use all possible PDB lookups.

Hope this helps,

Answer 2

From the article you mentioned: "states near to the goal can be precalculated", the obvious consequence is that you can go further if the branching factor (ir in this case search space) is lower.
So symmetrical reduction is not tool to do estimation but reduction for the search space and the end game (states near to goal) to make computations less computationaly expensive.

Another reduction described is to store partial solutions (sometimes called roadmap)(good states that makes the goal easier achievable) and reduces the space covered $1038-fold$.

The heuristic from A* and given roadmap has to estimate the best move from available data, so it is lower bound possible for this approach.