On creating complementary pattern databases

Santiago Franco Aixela, Alvaro Torralba, Levi HS Lelis, Mike Barley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17)
EditorsCarles Sierra
Pages4302-4309
Number of pages8
ISBN (Electronic)9780999241103
DOIs
Publication statusPublished - Aug 2017
Event26th International Joint Conference on Artificial Intelligence - Melbourne Convention Centre, Melbourne, Australia
Duration: 19 Aug 201725 Aug 2017
Conference number: 26
https://ijcai-17.org/ (Link to Conference Website )

Conference

Conference26th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2017
CountryAustralia
CityMelbourne
Period19/08/1725/08/17
Internet address

Fingerprint

Table lookup
Planning
Costs

Cite this

Franco Aixela, S., Torralba, A., Lelis, L. HS., & Barley, M. (2017). On creating complementary pattern databases. In C. Sierra (Ed.), Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17) (pp. 4302-4309) https://doi.org/10.24963/ijcai.2017/601
Franco Aixela, Santiago ; Torralba, Alvaro ; Lelis, Levi HS ; Barley, Mike. / On creating complementary pattern databases. Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17). editor / Carles Sierra. 2017. pp. 4302-4309
@inproceedings{38f5a102ff4e4004aac0b8b1353ba7bc,
title = "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.",
author = "{Franco Aixela}, Santiago and Alvaro Torralba and Lelis, {Levi HS} and Mike Barley",
year = "2017",
month = "8",
doi = "10.24963/ijcai.2017/601",
language = "English",
pages = "4302--4309",
editor = "Carles Sierra",
booktitle = "Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17)",

}

Franco Aixela, S, Torralba, A, Lelis, LHS & Barley, M 2017, On creating complementary pattern databases. in C Sierra (ed.), Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17). pp. 4302-4309, 26th International Joint Conference on Artificial Intelligence, Melbourne, Australia, 19/08/17. https://doi.org/10.24963/ijcai.2017/601

On creating complementary pattern databases. / Franco Aixela, Santiago; Torralba, Alvaro; Lelis, Levi HS; Barley, Mike.

Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17). ed. / Carles Sierra. 2017. p. 4302-4309.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - On creating complementary pattern databases

AU - Franco Aixela, Santiago

AU - Torralba, Alvaro

AU - Lelis, Levi HS

AU - Barley, Mike

PY - 2017/8

Y1 - 2017/8

N2 - 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.

AB - 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.

U2 - 10.24963/ijcai.2017/601

DO - 10.24963/ijcai.2017/601

M3 - Conference contribution

SP - 4302

EP - 4309

BT - Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17)

A2 - Sierra, Carles

ER -

Franco Aixela S, Torralba A, Lelis LHS, Barley M. On creating complementary pattern databases. In Sierra C, editor, Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17). 2017. p. 4302-4309 https://doi.org/10.24963/ijcai.2017/601