AAAI

Association for the Advancement of Artificial Intelligence

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

Optimal-Generation Variants of EPEA*

Authors

Meir Goldenberg,Ariel Felner,Nathan Sturtevant,Robert C. Holte,Jonathan Schaeffer

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


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 6

Volume

Issue:

Vol. 6 No. 1 (2013): Sixth Annual Symposium on Combinatorial Search

Track:

Full Papers

Downloads:

Download PDF

Abstract:

It is known that A* is optimal with respect to the expanded nodes (Dechter and Pearl 1985) (D&P). The exact meaning of this optimality varies depending on the class of algorithms and instances over which A* is claimed to be optimal. A* does not provide any optimality guarantees with respect to the generated nodes. However, such guarantees may be critical for optimally solving instances of domains with a large branching factor. In this paper, we introduce two new variants of the recently introduced Enhanced Partial Expansion A* algorithm (EPEA*) (Felner et al. 2012). We leverage the results of D&P to show that these variants possess optimality with respect to the generated nodes in much the same sense as A* possesses optimality with respect to the expanded nodes. The results in this paper are theoretical. A study of the practical performance of the new variants is beyond the scope of this paper.

DOI:

10.1609/socs.v4i1.18288


SOCS

Vol. 6 No. 1 (2013): Sixth Annual Symposium on Combinatorial Search