Abstract
Beam search executes a state-space search, but may abandon nonpromising search avenues in order to reduce complexity. Although it has existed for more than two decades and has been applied to many real-world problems, beam search still suffers from the drawback of possible termination with no solution or a solution of unsatisfactory quality. In this paper, we first propose a domain-independent heuristic for node pruning, and a method to reduce the possibility that beam search will fail. We then develop a complete beam search algorithm. The new algorithm can not only find an optimal solution, but can also reach better solutions sooner than its underlying search method. We apply complete beam search to the maximum boolean satisfiability and the symmetric and asymmetric Traveling Salesman Problems. Our experimental results show that the domain-independent pruning heuristic is effective and the new algorithm significantly improves the performance of its underlying search algorithm.
Introduction
In heuristic search, a fundamental trade-off exists between computational speed and solution reliability. Standard beam search is a popular strategy that limits memory and computation by "pruning" search paths that appear unpromising. However, this efficiency comes at a cost: the algorithm is incomplete. If pruning rules are too aggressive, the path to an optimal (or even valid) solution may be discarded. Furthermore, most implementations rely on domain-specific pruning rules, requiring significant expert tuning.
This paper introduces Complete Anytime Beam Search (CBS), which addresses these limitations by making beam search both complete—guaranteed to find an optimal solution—and "anytime"—capable of returning increasingly better solutions as more time is allocated.
The CBS Algorithm
The CBS algorithm incorporates three primary innovations to overcome the traditional drawbacks of beam search.
1. Domain-Independent Pruning
Rather than relying on problem-specific logic, CBS uses a cost-based threshold. A child node $n'$ is pruned if its cost $c(n')$ exceeds its parent's cost $c(n)$ by more than a parameter $\delta$ (i.e., $c(n') > c(n) + \delta$). The initial $\delta$ is determined through online sampling, where an initial probe of the search space estimates the typical cost increases between nodes.
2. The Modification Rule
To prevent "artificial" dead ends—where all children of a node are slated for pruning—CBS enforces a rule to keep at least one child (the one with the minimum cost). This is particularly vital in search spaces with low branching factors, such as boolean satisfiability.
3. Iterative Weakening
This is the core mechanism of CBS. The algorithm starts with a restrictive pruning threshold (small $\delta$). If the search finishes without finding an optimal solution or if time remains, $\delta$ is increased ("weakened"), and the search restarts. Eventually, $\delta$ becomes large enough that no nodes are pruned, effectively transforming CBS into an exhaustive search like Depth-First Search (DFS).
Experimental Evaluation
The performance of CBS was evaluated against standard DFS across three NP-complete combinatorial optimization problems: Maximum 3-Satisfiability (Max 3-Sat), the Symmetric Traveling Salesman Problem (STSP), and the Asymmetric Traveling Salesman Problem (ATSP).
Key Results
In all tested domains, CBS demonstrated superior "anytime" performance, finding high-quality solutions significantly faster than DFS.
- Maximum 3-Sat: On difficult instances with 30 variables and 450 clauses, CBS with the modification rule significantly outperformed DFS.
- Traveling Salesman Problems: For both 100-city symmetric and 200-city asymmetric instances, CBS reached near-optimal solutions much sooner than DFS. Because the algorithm eventually relaxes all pruning, it is guaranteed to find the optimal solution given enough time.
Conclusion
Complete Anytime Beam Search (CBS) successfully bridges the gap between fast, greedy heuristics and exhaustive search. By utilizing iterative weakening and a domain-independent pruning heuristic, it provides a robust framework for solving complex optimization problems. While future work may explore optimal weakening schedules, the current results confirm that CBS significantly improves upon the anytime performance of traditional search methods while maintaining completeness.
Summary updated