Combining perimeter search and pattern database abstractions Academic Article uri icon

abstract

  • A pattern database abstraction (PDB) is a heuristic function in a form of a lookup table. A PDB stores the cost of optimal solutions for instances of abstract problems (subproblems). These costs are used as admissible heuristics for the original problem. Perimeter search (PS) is a form of bidirectional search. First, a breadth-first search is performed backwards from the goal state. Then, a forward search is executed towards the nodes of the perimeter. In this paper we study the effect of combining these two techniques. We describe two methods for doing this. The simplified method uses a regular PDB (towards a single goal state) but uses the perimeter to correct heuristics of nodes outside the perimeter. The second, more advanced method is to build a PDB that stores the cost of reaching any node of the perimeter from a given pattern. Although one might see great potential for speedup …

publication date

  • July 18, 2007