Searching Without a Heuristic: Efficient Use of Abstraction

Bradford John Larsen, Ethan Burns, Wheeler Ruml, Robert HolteAAAI 2010 · DOI

Introduction

The efficiency of the A search algorithm is fundamentally tied to the quality of its heuristic function ($h$). In many complex or constrained domains, such as a sliding tile puzzle with a "glued" tile, standard heuristics like Manhattan distance fail to provide accurate estimates. While Pattern Databases (PDBs) offer a solution by precomputing abstract costs, they are memory-intensive and inflexible to changes in the goal state. Hierarchical Heuristic Search (HHS) methods like HA and HIDA* attempt to compute these costs lazily, but they often suffer from massive redundancy, re-expanding the same abstract nodes repeatedly.

The Switchback Algorithm

The "Switchback" approach addresses these inefficiencies by organizing the abstraction hierarchy into alternating search directions. In a standard hierarchical search, a request for a heuristic value at the base level triggers a search at the next abstraction level. Switchback optimizes this by alternating the search direction at each level:

  • Base Level (Level 0): Searches forward from the start state toward the goal.
  • Abstraction Level 1: Searches backward from the abstracted goal toward the abstracted start.
  • Abstraction Level 2: Searches forward again.
The Switchback mechanism: alternating search directions across abstraction levels ensure each node is expanded at most once.

This alternating structure is the key to Switchback's efficiency. When the base level encounters a node $n$ and requires a heuristic estimate to the goal, it queries Level 1. Because Level 1 is searching backward from the goal, any node it has already expanded contains the optimal distance back to that goal. If the value is present in Level 1's closed list, it is returned immediately. If not, Level 1 resumes its search until the value is found. This coordination ensures that every node at any level of the hierarchy is expanded at most once, effectively building a "lazy" Pattern Database focused only on relevant states.

Experimental Evaluation

The researchers benchmarked Switchback against HA, HIDA, and standard A* across four challenging combinatorial domains:

  1. Macro 15-Puzzle: Allows moving multiple tiles in a single step.
  2. Glued 15-Puzzle: A standard puzzle with one fixed tile, rendering traditional heuristics ineffective.
  3. 14-Pancake Puzzle: A high-branching factor permutation puzzle.
  4. Standard 15-Puzzle: A baseline for performance in well-understood domains.

Key Results

Switchback demonstrated significant performance gains over previous hierarchical algorithms. In the Glued 15-Puzzle, Switchback was nearly four times faster than HIDA*. The algorithm's structural efficiency is most evident in its node expansion counts and cache hit rates.

Performance comparison across four domains. Switchback consistently achieves lower CPU times and higher cache hit rates than previous hierarchical methods.

As shown in the experimental data, Switchback achieved a 100% cache hit rate at the base level for several domains. This indicates that once an abstract region is explored, its heuristic values are perfectly preserved and reused, eliminating the re-expansion problem that plagued HA. While A with hand-tuned heuristics remains faster for simple domains like the standard 15-puzzle, Switchback is the superior choice for "messy" domains where effective heuristics are not readily available.

Limitations and Future Work

Despite its advantages, Switchback requires the ability to compute state "predecessors" for backward searching, which may be difficult in domains with irreversible actions. Additionally, while more memory-efficient than full PDBs, it still stores all generated nodes, which could be a constraint in massive state spaces. Future research may explore dynamic search direction selection to optimize cache reuse when goal states change.

Summary updated

BibTeX
@inproceedings{larsen2010searching,
  author = {Bradford John Larsen and Ethan Burns and Wheeler Ruml and Robert Holte},
  title = {{Searching Without a Heuristic: Efficient Use of Abstraction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7563},
}
Figure