Partial-Expansion A* with Selective Node Generation Conference Paper uri icon

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* 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. n is re-inserted into the OPEN list, but with the f-cost of the next best child. This paper introduces an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* generates only the children with the same f-cost as the parent. EPEA* is generalized to its iterative-deepening variant, EPE-IDA*. For some domains, these algorithms yield substantial performance improvements. State-of-the-art results were obtained for the pancake puzzle and for some multi-agent pathfinding instances. Drawbacks of EPEA* are also discussed.

published proceedings

  • Proceedings of the AAAI Conference on Artificial Intelligence

author list (cited authors)

  • Felner, A., Goldenberg, M., Sharon, G., Stern, R., Beja, T., Sturtevant, N., Schaeffer, J., & Holte, R.

citation count

  • 6

complete list of authors

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

publication date

  • November 2012