3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ If p is the original state and p' is the reflected state, then the number of moves to solve p for goal g is the same as the number of moves to solve p' for goal g' (goal in the reflected state),right? $\endgroup$ – a_123 Apr 23 '16 at 16:57
  • $\begingroup$ Indeed! That's why when using $D$, you can safely look up your Pattern Database because $D\circ I\circ D=I$ where $I$ is the identity permutation, i.e., the usual goal permutation: $\{0, 1, 2, ...\}$. However, for the other symmetries, this is not true and thus the corrections proposed in the paper (and mentioned in the reply: 3, 3 and 6) have to be applied if you want to preserve admissibility. $\endgroup$ – Carlos Linares López Apr 25 '16 at 17:46
  • $\begingroup$ Note that in the specific case of the $N$-puzzle, "symmetric look ups" (and also "dual lookups" from the third paper mentioned in my response) are "complicated by the blank". See Ariel Felner, Uzi Zahavi, Jonathan Schaeffer and Robert C. Holte, Dual Lookups in Pattern Databases, IJCAI 2015, pp. 103--108 and, specifically, Section 6 where this is explained. Indeed, the authors propose here to compute different PDBs with different goal states just depending upon the location of the blank tile ---they additionally use symmetries to minimize the number of these PDBs. $\endgroup$ – Carlos Linares López Apr 25 '16 at 18:03
  • $\begingroup$ Please, let me know s_123 if you think that any of these two comments address your question. I could then edit my answer to make it more complete. Cheers, $\endgroup$ – Carlos Linares López Apr 25 '16 at 18:04
  • $\begingroup$ @CarlosLinaresLópez What is the point of having the number of moves to solve p' for goal g'? How are we going to use this? I can't imagine a concrete example where this symmetry would be used to shrink PDB size. $\endgroup$ – Bilow Mar 15 '18 at 22:52
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.