On Creating Complementary Pattern Databases
Abstract
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.
Cite
Text
Franco et al. "On Creating Complementary Pattern Databases." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/601Markdown
[Franco et al. "On Creating Complementary Pattern Databases." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/franco2017ijcai-creating/) doi:10.24963/IJCAI.2017/601BibTeX
@inproceedings{franco2017ijcai-creating,
title = {{On Creating Complementary Pattern Databases}},
author = {Franco, Santiago and Torralba, Álvaro and Lelis, Levi H. S. and Barley, Mike},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {4302-4309},
doi = {10.24963/IJCAI.2017/601},
url = {https://mlanthology.org/ijcai/2017/franco2017ijcai-creating/}
}