On Creating Complementary Pattern Databases

A pattern database (PDB) for a planning task is a heuristic function in the form of a lookup table that contains optimal solution costs of a simplified version of the task. In this paper we introduce a method that sequentially creates multiple PDBs which are later combined into a single heuristic function. At a given iteration, our method uses estimates of the A* running time to create a PDB that complements the strengths of the PDBs created in previous iterations. We evaluate our algorithm using explicit and symbolic PDBs. Our results show that the heuristics produced by our approach are able to outperform existing schemes, and that our method is able to create PDBs that complement the strengths of other existing heuristics such as a symbolic perimeter heuristic.

Authors

• Santiago Franco
• Álvaro Torralba
• Levi H. S. Lelis Department of Computing Science, Alberta Machine Intelligence Institute (Amii), University of Alberta, Canada
• Mike Barley

Keywords

• Combinatorial & Heuristic Search: Combinatorial search/optimisation
• Combinatorial & Heuristic Search: Heuristic Search
• Combinatorial & Heuristic Search: Meta-Reasoning and Meta-heuristics
• Planning and Scheduling: Planning Algorithms