Limited Discrepancy Beam Search

David Furcy, Sven KoenigIJCAI 2005 · OpenReview

Introduction

Searching for a path from a start state to a goal is a cornerstone of artificial intelligence. While algorithms like A are optimal, they often exceed memory limits on complex problems. Beam search* addresses this by maintaining a fixed number of promising states (the beam width, $B$) at each level. However, beam search is "incomplete"—if the heuristic incorrectly prunes the path to the goal, the search fails. This often forces a choice between very small beam widths (leading to long, inefficient paths) or large widths that exhaust memory.

This paper introduces BULB (Beam search Using Limited discrepancy Backtracking), a memory-bounded algorithm that combines the efficiency of beam search with the completeness of backtracking. By leveraging "limited discrepancy" to guide backtracking, BULB avoids the over-pruning pitfalls of standard beam search and finds significantly shorter paths.

The BULB Algorithm

BULB integrates two core concepts: standard beam search and Limited Discrepancy Search (LDS). LDS is based on the insight that heuristics are typically most inaccurate at the beginning of a search. Instead of chronological backtracking (returning to the most recent decision), LDS backtracks by intentionally deviating from the heuristic's top choice—a "discrepancy"—starting from the top of the search tree.

Comparison of search strategies: (a) Breadth-first search explores all states per layer; (b) Beam search prunes states outside the beam; (c) Depth-first beam search (BULB) uses backtracking to explore different 'slices' of the state space.

In BULB, successors at each level are divided into "slices" of size $B$. The algorithm initially follows the best slice at every level, mimicking a standard beam search. If it hits a dead end or reaches memory limits, it backtracks using LDS principles to explore a different slice at a higher level. This "slicing" mechanism turns greedy pruning into a systematic exploration strategy. To ensure efficiency, BULB employs cycle detection via a hash table and maintains a strict memory bound of $O(Bd)$, where $d$ is the search depth.

Key Results

The authors evaluated BULB on challenging combinatorial puzzles, including the 48-Puzzle, 4-Peg Towers of Hanoi (22 disks), and the Rubik’s Cube.

  • Reliability and Path Quality: On the 48-Puzzle, standard beam search with a width of 10,000 only solved 80% of instances. In contrast, BULB solved 100% of instances and produced paths up to 25 times shorter (e.g., 440 steps vs. 11,737 steps).
  • Memory Efficiency: BULB successfully solved the 22-disk Towers of Hanoi problem, where standard beam search failed entirely due to misleading heuristics.
  • Anytime Performance: As an anytime algorithm, BULB can continue running after finding an initial solution, using additional discrepancies to further refine and shorten the path.
Performance comparison between standard beam search and BULB. (a) BULB consistently finds shorter paths (lower solution cost) as beam width $B$ increases. (b) BULB maintains manageable memory usage (stored nodes) while achieving these improvements.

Conclusion

BULB effectively bridges the gap between greedy, memory-efficient search and complete, optimal search. By prioritizing backtracking at the top of the search tree where heuristic errors are most likely, it provides a robust framework for solving large-scale search problems under tight memory constraints. Future work may explore dynamic beam widths and alternative discrepancy prioritization strategies to further enhance search efficiency.

Summary updated

BibTeX
@inproceedings{furcy2005limited,
  author = {David Furcy and Sven Koenig},
  title = {{Limited Discrepancy Beam Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=aBmdNpu7Pr6},
}
Figure