AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 5

Partial-Expansion A* with Selective Node Generation

Authors

Ariel Felner,Meir Goldenberg,Guni Sharon,Roni Stern,Tal Beja,Nathan Sturtevant,Robert Holte,Jonathan Schaeffer

Ben-Gurion University,Ben-Gurion University,Ben-Gurion University,Ben-Gurion University,Ben-Gurion University,University of Denver,University of Alberta,University of Alberta


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 5

Volume

Issue:

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Track:

Extended Abstracts of Papers Presented Elsewhere

Downloads:

Download PDF

Abstract:

A* is often described as being 'optimal,' in that it expands the minimum number of unique nodes. But, A* may generate many extra nodes which are never expanded. This is a performance loss, especially when the branching factor is large. Partial Expansion A* (PEA*) addresses this problem when expanding a node, n, by generating all the children of n but only storing children with the same f-cost as n. We introduce an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* only generates the children with the same f-cost as the parent. State-of-the-art results were obtained for a number of domains. Drawbacks of EPEA* are also discussed. A full version of this paper appears in the proceedings of AAAI-2012

DOI:

10.1609/socs.v3i1.18227


SOCS

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search