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.
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:
- Breadth-First Search with Lookahead (BRFSL): A version where goal testing occurs at the leaves of the lookahead.
- 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.
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