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.
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.
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