Optimal-Generation Variants of EPEA
- Meir Goldenberg
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Nathan R. Sturtevant
- Robert Holte, Department of Computing Science, University of Alberta
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
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.
Citation
M. Goldenberg, A. Felner, N. Sturtevant, R. Holte, J. Schaeffer. "Optimal-Generation Variants of EPEA". Symposium on Combinatorial Search, (ed: Malte Helmert, Gabriele Röger), pp 89-97, July 2013.| Keywords: | heuristic search, optimality, generated nodes |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Goldenberg+al:SoCS13,
author = {Meir Goldenberg and Ariel Felner and Nathan R. Sturtevant and
Robert Holte and Jonathan Schaeffer},
title = {Optimal-Generation Variants of EPEA},
Editor = {Malte Helmert, Gabriele Röger},
Pages = {89-97},
booktitle = {Symposium on Combinatorial Search},
year = 2013,
}Last Updated: July 09, 2020Submitted by Sabina P
