Symbolic A* search with pattern databases and the merge-and-shrink abstraction

Stefan Edelkamp; Peter Kissmann; Álvaro Torralba

doi:10.3233/978-1-61499-098-7-306

Symbolic A^* search with pattern databases and the merge-and-shrink abstraction

Stefan Edelkamp, Peter Kissmann, Álvaro Torralba

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

16 Citations (Scopus)

Abstract

The efficiency of heuristic search planning crucially depends on the quality of the search heuristic, while succinct representations of state sets in decision diagrams can save large amounts of memory in the exploration. BDDA^* - a symbolic version of A^* search - combines the two approaches into one algorithm. This paper compares two of the leading heuristics for sequential-optimal planning: the merge-and-shrink and the pattern databases heuristic, both of which can be compiled into a vector of BDDs and be used in BDDA^*. The impact of optimizing the variable ordering is highlighted and experiments on benchmark domains are reported.

Original language	English
Title of host publication	ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration
Number of pages	6
Publisher	IOS Press
Publication date	2012
Pages	306-311
ISBN (Print)	9781614990970
DOIs	https://doi.org/10.3233/978-1-61499-098-7-306
Publication status	Published - 2012
Externally published	Yes
Event	20th European Conference on Artificial Intelligence, ECAI 2012 - Montpellier, France Duration: 27 Aug 2012 → 31 Aug 2012

Conference

Conference	20th European Conference on Artificial Intelligence, ECAI 2012
Country/Territory	France
City	Montpellier
Period	27/08/2012 → 31/08/2012

Series	Frontiers in Artificial Intelligence and Applications
Volume	242
ISSN	0922-6389

Bibliographical note

Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

Access to Document

10.3233/978-1-61499-098-7-306

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

Edelkamp, S., Kissmann, P., & Torralba, Á. (2012). Symbolic A^* search with pattern databases and the merge-and-shrink abstraction. In ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration (pp. 306-311). IOS Press. https://doi.org/10.3233/978-1-61499-098-7-306

Edelkamp, Stefan ; Kissmann, Peter ; Torralba, Álvaro. / Symbolic A^* search with pattern databases and the merge-and-shrink abstraction. ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. IOS Press, 2012. pp. 306-311 (Frontiers in Artificial Intelligence and Applications, Vol. 242).

@inproceedings{b6ba09dd88f24ef286f142416bb02a29,

title = "Symbolic A* search with pattern databases and the merge-and-shrink abstraction",

abstract = "The efficiency of heuristic search planning crucially depends on the quality of the search heuristic, while succinct representations of state sets in decision diagrams can save large amounts of memory in the exploration. BDDA* - a symbolic version of A* search - combines the two approaches into one algorithm. This paper compares two of the leading heuristics for sequential-optimal planning: the merge-and-shrink and the pattern databases heuristic, both of which can be compiled into a vector of BDDs and be used in BDDA*. The impact of optimizing the variable ordering is highlighted and experiments on benchmark domains are reported.",

author = "Stefan Edelkamp and Peter Kissmann and {\'A}lvaro Torralba",

year = "2012",

doi = "10.3233/978-1-61499-098-7-306",

language = "English",

isbn = "9781614990970",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press",

pages = "306--311",

booktitle = "ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration",

address = "Netherlands",

}

Edelkamp, S, Kissmann, P & Torralba, Á 2012, Symbolic A^* search with pattern databases and the merge-and-shrink abstraction. in ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. IOS Press, Frontiers in Artificial Intelligence and Applications, vol. 242, pp. 306-311, 20th European Conference on Artificial Intelligence, ECAI 2012, Montpellier, France, 27/08/2012. https://doi.org/10.3233/978-1-61499-098-7-306

Symbolic A^* search with pattern databases and the merge-and-shrink abstraction. / Edelkamp, Stefan; Kissmann, Peter; Torralba, Álvaro.
ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. IOS Press, 2012. p. 306-311 (Frontiers in Artificial Intelligence and Applications, Vol. 242).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - Symbolic A* search with pattern databases and the merge-and-shrink abstraction

AU - Edelkamp, Stefan

AU - Kissmann, Peter

AU - Torralba, Álvaro

PY - 2012

Y1 - 2012

N2 - The efficiency of heuristic search planning crucially depends on the quality of the search heuristic, while succinct representations of state sets in decision diagrams can save large amounts of memory in the exploration. BDDA* - a symbolic version of A* search - combines the two approaches into one algorithm. This paper compares two of the leading heuristics for sequential-optimal planning: the merge-and-shrink and the pattern databases heuristic, both of which can be compiled into a vector of BDDs and be used in BDDA*. The impact of optimizing the variable ordering is highlighted and experiments on benchmark domains are reported.

AB - The efficiency of heuristic search planning crucially depends on the quality of the search heuristic, while succinct representations of state sets in decision diagrams can save large amounts of memory in the exploration. BDDA* - a symbolic version of A* search - combines the two approaches into one algorithm. This paper compares two of the leading heuristics for sequential-optimal planning: the merge-and-shrink and the pattern databases heuristic, both of which can be compiled into a vector of BDDs and be used in BDDA*. The impact of optimizing the variable ordering is highlighted and experiments on benchmark domains are reported.

UR - http://www.scopus.com/inward/record.url?scp=84878775014&partnerID=8YFLogxK

U2 - 10.3233/978-1-61499-098-7-306

DO - 10.3233/978-1-61499-098-7-306

M3 - Article in proceeding

AN - SCOPUS:84878775014

SN - 9781614990970

T3 - Frontiers in Artificial Intelligence and Applications

SP - 306

EP - 311

BT - ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration

PB - IOS Press

T2 - 20th European Conference on Artificial Intelligence, ECAI 2012

Y2 - 27 August 2012 through 31 August 2012

ER -

Edelkamp S, Kissmann P, Torralba Á. Symbolic A^* search with pattern databases and the merge-and-shrink abstraction. In ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. IOS Press. 2012. p. 306-311. (Frontiers in Artificial Intelligence and Applications, Vol. 242). doi: 10.3233/978-1-61499-098-7-306