A*+IDA*: A Simple Hybrid Search Algorithm

Zhaoxing Bu, Richard E. KorfIJCAI 2019 · DOI

TL;DR

This paper introduces A+IDA, a novel hybrid search algorithm that combines the strengths of A and IDA to significantly speed up optimal pathfinding in complex state spaces like the 24-Puzzle. By intelligently leveraging memory, A+IDA achieves up to a 5x speedup over traditional IDA* and outperforms previous state-of-the-art methods.

What Problem Does This Paper Address?

Finding optimal solutions in large, complex state spaces is a fundamental challenge in artificial intelligence and computer science. Algorithms like A are optimal but memory-intensive, while IDA is memory-efficient but can be slow due to redundant computations (duplicate nodes). While many algorithms have attempted to bridge this gap, none have demonstrated significant speedups over IDA* on notoriously difficult problems like the 24-Puzzle. This paper tackles the problem of finding optimal solutions more efficiently by developing a simple yet highly effective hybrid approach that makes better use of available memory.

Methods

The core innovation is A+IDA, a hybrid algorithm that operates in two phases:

  1. A* Phase: The algorithm first runs A search, a best-first search algorithm, until its memory is nearly exhausted. During this phase, A explores promising paths and stores generated nodes. Crucially, A* naturally prunes duplicate nodes.
  2. IDA* Phase: Once A has filled available memory, the algorithm switches to IDA. Instead of starting from the root node, IDA begins its search from the "frontier nodes" – the nodes that were on A's open list when memory ran out. These IDA iterations are performed without duplicate checking, as A has already handled this. Additionally, the frontier nodes are ordered by their heuristic (h) values, which helps find solutions earlier in the final IDA* iteration.

The authors also explore variations:

  • Dual Search Integration: Combining A+IDA with an improved version of "dual search" (a technique for permutation problems) further boosts performance.
  • Disk-based A+IDA: For extremely hard problems, they investigate using disk storage for the A* phase to handle even larger state spaces.

Datasets

The primary dataset used for evaluation is the 24-Puzzle, a well-known benchmark for search algorithms. The authors use a standard set of 50 test cases, including hard instances. They also test on:

  • Rubik's Cube: To evaluate the algorithm's generality.
  • 27-Puzzle (4x7) and 29-Puzzle (5x6): Larger sliding-tile puzzles to push the boundaries of optimal search. They generated random instances for these puzzles.

Key Insights and Ideas

  • The Power of Simple Hybridization: The most striking insight is that a straightforward combination of A and IDA can yield substantial performance gains, challenging the notion that only complex algorithms can outperform IDA*.
  • Memory as a Performance Lever: The paper demonstrates that intelligently using memory (via A) to prune duplicates and establish a strong starting point for IDA is more effective than simply adding more memory to pure IDA* or other complex memory-limited algorithms.
  • Frontier Node Ordering is Key: Ordering the frontier nodes in the IDA* phase by their heuristic values significantly accelerates finding the optimal solution in the final iteration, a finding that has been known but not widely adopted.
  • Why A+IDA Fails on Rubik's Cube: The analysis reveals that for problems with fewer duplicate nodes and less effective heuristic ordering (like Rubik's Cube), the overhead of the A phase and the limited benefit of node ordering can negate the advantages, making it no faster than pure IDA.

Key Results

  • 24-Puzzle Speedup: A+IDA achieved up to a 5x speedup over an efficient IDA* implementation on the 24-Puzzle.
  • Outperforming State-of-the-Art: When combined with an optimized dual search, A+IDA achieved a 6.7x speedup over efficient IDA*.
  • Larger Puzzles: The algorithm successfully found optimal solutions for subsets of random 27-Puzzle and 29-Puzzle instances, marking a significant achievement for these larger problems.
  • Disk-based Performance: The disk-based version showed speedups on extremely hard 24-Puzzle instances, indicating its utility for problems exceeding RAM capacity.
  • Rubik's Cube: A+IDA was not faster than IDA* on Rubik's Cube, with only a 1% slowdown observed.

Limitations and Future Work

  • Memory Dependency: The performance of A+IDA is directly tied to the available memory. While the disk-based version extends its applicability, it's still slower than RAM-based versions on less extreme problems.
  • Problem Specificity: The effectiveness of A+IDA is problem-dependent. It excels on problems with many duplicate nodes and good heuristic ordering (like the 24-Puzzle) but offers less benefit on problems like Rubik's Cube.
  • Future Work: The authors suggest exploring A+IDA on other complex search problems and investigating its potential for finding approximate solutions quickly. They also note that verifying optimality for the hardest 27 and 29-Puzzle instances could take months to years, highlighting the ongoing challenge of solving extremely large state spaces.

Summary updated

BibTeX
@inproceedings{bu2019ida,
  author = {Zhaoxing Bu and Richard E. Korf},
  title = {{A*+IDA*: A Simple Hybrid Search Algorithm}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/168},
}
Figure