Using Lookaheads with Optimal Best-First Search

Roni Stern, Tamar Kulberis, Ariel Felner, Robert HolteAAAI 2010 · DOI

Abstract: Best-First Search (BFS) algorithms like A are optimal but suffer from high memory consumption, while Depth-First Search (DFS) is memory-efficient but often slow and suboptimal. This paper presents a hybrid framework that integrates DFS lookaheads into a BFS backbone. By exploring a fixed depth $k$ from the frontier, the proposed algorithms—Breadth-First Search with Lookahead (BRFSL) and A with Lookahead (AL*)—achieve significant memory reductions and speedups across various combinatorial benchmarks.

Introduction

The "Memory Wall" is a well-known bottleneck in heuristic search. Optimal algorithms like A must store all generated nodes in an "Open List" to ensure they find the shortest path and handle transpositions. In large state spaces, memory is often exhausted long before a solution is found. Conversely, Depth-First Search (DFS) variants like IDA use minimal memory but can be inefficient in domains with many cycles or transpositions. This research proposes a middle ground: a continuum between BFS and DFS that leverages the strengths of both.

The Lookahead Framework

The core idea is to perform a limited DFS lookahead of depth $k$ from each node on the BFS frontier. Instead of immediately adding every child to the priority queue, the algorithm explores the local neighborhood using DFS. This leverages the low overhead of DFS—which avoids complex heap management and state copying—to explore deeper without a proportional increase in memory usage.

The lookahead process in a search tree. (a) Expansion of root node A with a depth-2 lookahead. (b, c) Subsequent expansions of frontier nodes B and C. Legend indicates expanded, generated, and goal-tested nodes.

As shown in the figure above, this approach allows the algorithm to "skip" storing several levels of the search tree in the Open List. The memory complexity effectively drops from $O(b^d)$ to $O(b^{d-k})$, where $b$ is the branching factor and $d$ is the solution depth.

Algorithms: BRFSL and AL*

The authors introduce two main variants:

  1. Breadth-First Search with Lookahead (BRFSL): A version where goal testing occurs at the leaves of the lookahead.
  2. A with Lookahead (AL): A more sophisticated version where lookaheads are bounded by a cost function ($f$-value).

AL* incorporates several key optimizations. One is "Trivial Lookahead," where a child node with the same heuristic value as its parent is expanded immediately, bypassing expensive priority queue operations. Another is the integration of Bidirectional Pathmax (BPMX), which propagates heuristic values throughout the lookahead tree to improve pruning.

Lookahead in AL* illustrating cost-based exploration. The numbers represent f-values. Lookaheads allow the search to identify nodes with lower or equal costs deeper in the tree without increasing the Open List size.

Experimental Evaluation

The algorithms were tested on two classic benchmarks: the 15-Puzzle and the TopSpin Puzzle.

  • 15-Puzzle: AL(5) achieved a 4x speedup and a 20x reduction in memory compared to standard A. Crucially, it solved 98 out of 100 instances within a 2GB RAM limit, whereas standard A* could only solve 74.
  • TopSpin: In this cyclic domain, AL significantly outperformed IDA. The BFS backbone of AL* handles transpositions effectively, while the DFS lookaheads provide the necessary speed and memory savings.

Conclusion

By bridging the gap between BFS and DFS, lookahead-based searches offer a practical solution to the memory constraints of optimal pathfinding. While the optimal lookahead depth $k$ remains domain-dependent, the framework provides a robust way to scale search algorithms to larger problems. Future work includes developing dynamic methods to adjust $k$ automatically based on the search space characteristics.

Summary updated

BibTeX
@inproceedings{stern2010using,
  author = {Roni Stern and Tamar Kulberis and Ariel Felner and Robert Holte},
  title = {{Using Lookaheads with Optimal Best-First Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7559},
}
Figure