Hierarchical A*: Searching Abstraction Hierarchies Efficiently

AAAI 1996

TL;DR

This paper introduces Hierarchical A, a novel search algorithm that significantly improves the efficiency of A search by leveraging abstraction hierarchies. By combining a new class of "homomorphism abstractions" with intelligent caching techniques, Hierarchical A* effectively overcomes limitations of previous abstraction methods, leading to substantial reductions in search effort and breaking a long-standing theoretical barrier.

What Problem Does This Paper Address?

The core problem this paper tackles is the computational cost of search algorithms like A when applied to complex problems. A uses heuristics to guide its search, estimating the distance from the current state to the goal. A common way to generate these heuristics is through abstraction: creating a simpler, "abstract" state space where search is faster. The results from the abstract search are then used to inform the search in the original, more complex space.

However, two major obstacles have hindered the practical application of this approach:

  1. Valtorta's Barrier: A theorem states that for a common type of abstraction ("embedding abstractions"), A* using an abstracted heuristic will expand at least as many states as a blind search in the original space. This means no speedup is guaranteed.
  2. Computational Overhead: Generating the heuristic often requires repeatedly performing a full search in the abstract space for each state expansion in the original space, which can be computationally expensive and negate any benefits gained from the heuristic.

This paper aims to overcome these limitations by introducing a new abstraction technique and more efficient search strategies.

Methods

The paper proposes Hierarchical A, an algorithmic approach that customizes the A algorithm for searching abstraction hierarchies. The key innovations are:

  • Homomorphism Abstractions: Instead of "embedding" abstractions (which essentially add edges to the original graph), the paper focuses on "homomorphism" abstractions. These group multiple states from the original space into a single abstract state. This many-to-one mapping is crucial because it allows a single abstract state expansion to represent the expansion of many original states, potentially breaking Valtorta's barrier.
  • Caching Techniques: To address the computational overhead of repeated abstract searches, Hierarchical A* employs several caching strategies:
  • h*-caching: Stores the exact distance-to-goal computed for abstract states. When a search at an abstract level completes, the computed heuristic values for states on the solution path are cached.
  • Optimal-path caching: Extends h*-caching by storing the entire optimal path found in the abstract space. This allows for direct termination when the goal is reached, avoiding further expansion of states on that path.
  • P-g caching: Leverages the fact that if the length of the shortest path to the goal (P) is known, then P - g(S) (where g(S) is the cost to reach state S) is an admissible heuristic. This technique caches this "P-g" value for states that were opened but not closed.

These caching mechanisms aim to avoid recomputing heuristic values and reduce the number of abstract searches needed.

Datasets

The paper evaluates its methods on 8 different search spaces. These include:

  • Blocks-5
  • 5-puzzle
  • Fool's Disk
  • Hanoi-7
  • KL2000
  • MC 60-40-7 (Missionaries and Cannibals)
  • Permute-6
  • Words

For each search space, 200 test problems were generated by randomly selecting 100 pairs of states and creating two problems for each pair (start to goal, and goal to start). The authors emphasize that the same 200 problems were used across all experiments for detailed comparison. No new benchmarks were introduced; existing search spaces were used.

Key Insights and Ideas

  • Homomorphisms are Key to Breaking Barriers: The paper strongly suggests that "homomorphism abstractions" are essential for overcoming Valtorta's barrier, unlike "embedding abstractions." By collapsing multiple states into one, they offer a more significant potential for heuristic quality and search speedup.
  • Caching is Crucial for Practicality: While homomorphism abstractions offer theoretical advantages, their practical benefit is heavily dependent on efficient caching. Without it, the cost of computing heuristics can outweigh the gains. The paper demonstrates that combining multiple caching strategies is vital.
  • Granularity Matters: The "granularity" of the abstraction (controlled by an "abstraction radius") significantly impacts performance. There's a sweet spot: too fine-grained, and the heuristic might not be informative enough; too coarse, and the heuristic becomes too weak. Finding the right balance is critical.
  • Surprising Effectiveness of Coarse Abstractions: The authors note it's surprising that even very coarse abstractions (with only one non-trivial abstract level) can lead to significant reductions in nodes expanded, especially when combined with algorithmic enhancements.

Key Results

  • Breaking Valtorta's Barrier: Hierarchical A* (specifically version V3, incorporating optimal-path and P-g caching) successfully breaks Valtorta's barrier in 5 out of 8 test spaces. When combined with varying abstraction granularity, it breaks the barrier in all test spaces.
  • Significant Reduction in Nodes Expanded:
    • Naive Hierarchical A (without advanced caching) actually increased* nodes expanded compared to blind search.
  • h*-caching (V1) roughly halved the number of nodes expanded.
  • Optimal-path caching (V2) doubled the savings of h*-caching.
  • V3 (with both optimal-path and P-g caching) showed the best performance, breaking the barrier in multiple spaces.
  • CPU Time Improvements: While nodes expanded are a theoretical measure, CPU time is also reported. The paper notes that V3's reduction in nodes expanded often balances the overhead of hierarchical search, leading to significant CPU time improvements (e.g., a factor of 10 for the 8-puzzle).
  • Granularity Impact: Table 3 shows that for V3, the best abstraction radius varied across search spaces. Increasing the radius initially reduced nodes expanded but then increased them, highlighting the trade-off.

Limitations and Future Work

  • Abstraction Technique: The paper acknowledges that the "max-degree" abstraction technique used is not suitable for all types of search spaces (e.g., those with non-uniform operator costs). The development of abstraction techniques specifically suited for Hierarchical A* is identified as an important area for future research.
  • Implementation Details: The authors mention that their current implementation is "rather clumsy in many of its low-level details," suggesting that further optimization of the implementation could yield even better CPU time results.
  • User-Supplied Abstractions: While the current work focused on evaluating Hierarchical A* with automatically generated abstractions, future work could explore its performance with user-supplied abstractions, which might be more tailored to specific problems.
  • Theoretical vs. Practical Gains: While the paper demonstrates breaking Valtorta's barrier, the reduction in nodes expanded was sometimes modest. The authors suggest that the limitations were more due to the abstraction technique than excessive algorithmic overhead.

Summary updated

BibTeX
@inproceedings{1996hierarchical,
  title = {{Hierarchical A*: Searching Abstraction Hierarchies Efficiently}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure