Enhanced Partial Expansion A

Meir Goldenberg, Ariel Felner, Roni Stern, Guni Sharon, Nathan R. Sturtevant, Robert C. Holte, Jonathan Schaeffer

TL;DR

This paper introduces Enhanced Partial Expansion A (EPEA), a novel search algorithm that significantly improves upon traditional A by intelligently avoiding the generation of "surplus" nodes. By leveraging domain-specific knowledge through an Operator Selection Function (OSF), EPEA achieves substantial reductions in both computation time and memory usage, making it highly effective for complex problems with large branching factors.

What Problem Does This Paper Address?

When solving complex problems, especially those with a high branching factor (meaning each step can lead to many possible next steps), traditional search algorithms like A can become overwhelmed. A generates a vast number of nodes, many of which are "surplus" – their estimated cost is higher than the optimal solution. These surplus nodes consume significant memory and processing time without contributing to finding the optimal solution. While a previous variant, Partial Expansion A (PEA), addressed the memory issue by not adding surplus nodes to the "OPEN" list, it incurred a significant time overhead due to re-generating nodes. This paper tackles the challenge of reducing both the time and memory costs associated with surplus nodes in search algorithms.

Methods

The core innovation is the Operator Selection Function (OSF). Unlike A and PEA, which generate all children of a node, EPEA uses an OSF to intelligently select only* the children that are "currently needed" (i.e., those with an estimated cost equal to the parent's current best estimate). The OSF is composed of two parts:

  1. Knowledge Component: Domain- and heuristic-specific knowledge, often represented in tables.
  2. Algorithmic Component: An algorithm that uses this knowledge to determine which operators lead to currently needed children and to update the parent node's stored value.

This allows EPEA to avoid generating surplus nodes altogether, rather than just avoiding storing them. The paper also extends these ideas to IDA (creating EPEIDA*) and explores different types of OSFs, including those based on pattern databases.

Datasets

The paper evaluates EPEA* and its variants on several standard benchmark domains:

  • 15-puzzle: Using the Manhattan distance heuristic.
  • Pancake Puzzle: Using the GAP heuristic.
  • Rubik's Cube: Using the Corner PDB heuristic.
  • Multi-Agent Pathfinding (MAPF): Using the Sum of Individual Costs (SIC) heuristic and additive PDBs.

No new benchmarks were introduced; existing, well-established problem domains were used for evaluation.

Key Insights and Ideas

  • The Power of Domain Knowledge: The OSF is the linchpin of EPEA*. It demonstrates that by encoding specific knowledge about the problem and heuristic, search can be made drastically more efficient.
  • Beyond Memory: Tackling Time: While PEA focused on memory, EPEA directly addresses the time overhead by avoiding unnecessary node generation, a crucial step for large-scale problems.
  • Surplus Nodes are Costly: The paper strongly emphasizes that surplus nodes are not just a memory burden but a significant performance bottleneck in terms of computation time.
  • OSF Flexibility: The paper categorizes OSFs into "full-checking" (checks all operators) and "direct-computation" (directly computes needed operators), showing that the choice depends on the domain and heuristic.
  • EPEA vs. PEA Trade-off: EPEA avoids the re-expansion overhead of PEA by not generating unneeded nodes, leading to better performance in many cases.

Key Results

  • Significant Speedups: EPEA and EPEIDA consistently outperformed their counterparts (A, IDA, PEA) across various domains. For example, on the 15-puzzle, EPEIDA generated 1.97x fewer nodes and was 1.25x faster than IDA. For the Pancake Puzzle, EPEIDA generated 68x fewer nodes and was 54x faster than IDA*.
  • Memory Savings: EPEA achieves the same memory savings as the most memory-efficient variant of PEA (with C=0).
  • MAPF Performance: In Multi-Agent Pathfinding, EPEA generated orders of magnitude fewer nodes and was significantly faster than A and PEA. EPEA with additive PDBs was the clear winner for hard instances.
  • OSF Effectiveness: The choice of OSF (full-checking vs. direct-computation) impacts performance, with direct-computation generally offering better speedups when applicable.

Limitations and Future Work

  • OSF Construction: The primary limitation is the need for a domain- and heuristic-specific OSF. Constructing an effective OSF can be challenging.
  • Inconsistent Heuristics: The paper touches upon the use of EPEA with inconsistent heuristics, noting a trade-off between EPEA's efficiency and the potential benefits of heuristic value propagation techniques (like BPMX). A deeper study of this trade-off is suggested.
  • Polynomial Domains: The paper notes that EPEA might not always be faster than A in polynomial domains, and in some cases, it was observed to be slightly slower.
  • Future Work: The authors suggest exploring EPEA for domain-independent planning heuristics, investigating merge-and-shrink abstractions, landmarks, and using symbolic representations like BDDs for OSF construction. They also propose studying EPEA for non-optimal searches and further investigating the trade-off with value propagation techniques.

Summary updated

Abstract

When solving instances of problem domains that feature a large branching factor, A* may generate a large number of nodes whose cost is greater than the cost of the optimal solution. We designate such nodes as surplus. Generating surplus nodes and adding them to the OPEN list may dominate both time and memory of the search. A recently introduced variant of A* called Partial Expansion A* (PEA*) deals with the memory aspect of this problem. When expanding a node n, PEA* generates all of its children and puts into OPEN only the children with f = f (n). n is re-inserted in the OPEN list with the f -cost of the best discarded child. This guarantees that surplus nodes are not inserted into OPEN. In this paper, we present a novel variant of A* called Enhanced Partial Expansion A* (EPEA*) that advances the idea of PEA* to address the time aspect. Given a priori domain- and heuristic- specific knowledge, EPEA* generates only the nodes with f = f(n). Although EPEA* is not always applicable or practical, we study several variants of EPEA*, which make it applicable to a large number of domains and heuristics. In particular, the ideas of EPEA* are applicable to IDA* and to the domains where pattern databases are traditionally used. Experimental studies show significant improvements in run-time and memory performance for several standard benchmark applications. We provide several theoretical studies to facilitate an understanding of the new algorithm.
BibTeX
@article{goldenberg2014enhanced,
  author = {Meir Goldenberg and Ariel Felner and Roni Stern and Guni Sharon and Nathan R. Sturtevant and Robert C. Holte and Jonathan Schaeffer},
  title = {{Enhanced Partial Expansion A}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  doi = {10.1613/jair.4171},
}
Figure