Partial-Expansion A* with Selective Node Generation

Authors

  • Ariel Felner Ben-Gurion University
  • Meir Goldenberg Ben-Gurion University
  • Guni Sharon Ben-Gurion University
  • Roni Stern Ben-Gurion University
  • Tal Beja Ben-Gurion University
  • Nathan Sturtevant University of Denver
  • Robert Holte University of Alberta
  • Jonathan Schaeffer University of Alberta

DOI:

https://doi.org/10.1609/socs.v3i1.18227

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

SoCS 2012 Proceedings Cover

Downloads

Published

2021-08-20

How to Cite

Felner, A., Goldenberg, M., Sharon, G., Stern, R., Beja, T., Sturtevant, N., Holte, R., & Schaeffer, J. (2021). Partial-Expansion A* with Selective Node Generation. Proceedings of the International Symposium on Combinatorial Search, 3(1), 180-181. https://doi.org/10.1609/socs.v3i1.18227

Issue

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

Section

Extended Abstracts of Papers Presented Elsewhere