Introduction
In state-space search, a fundamental trade-off exists between time and memory. Algorithms like A are time-efficient but suffer from exponential memory growth. Conversely, linear-space algorithms like Iterative Deepening A (IDA*) are memory-efficient but can be slow due to redundant node regenerations. Bidirectional search—searching simultaneously from the start and the goal—offers a theoretical speedup by halving the search depth. However, it traditionally requires significant memory to store search fronts and detect their intersection.
This paper introduces Memory-Bounded Bidirectional Search (MBBS), the first algorithm to successfully combine the efficiency of bidirectional search with strict memory constraints. By adapting memory-bounded unidirectional search to a two-sided framework, the authors demonstrate that bidirectional search is not only feasible under limited RAM but significantly faster than traditional one-way approaches.
Methods: WSMAG* and MBBS
The core of the proposed approach lies in two algorithmic developments:
WSMAG (Weighted Simplified Memory-Bounded A for Graphs)
WSMAG extends Russell’s SMA to handle directed acyclic graphs. SMA manages a fixed memory budget by pruning the "least promising" nodes when the limit is reached, while "backing up" their values to parents for potential future regeneration. WSMAG introduces a "blocking" technique to prevent infinite loops during node regeneration in graphs and incorporates a weight factor ($\epsilon$) to allow for $\epsilon$-admissible search, finding solutions within a guaranteed factor of the optimal cost.
MBBS (Memory-Bounded Bidirectional Search)
MBBS runs WSMAG* from both directions (start-to-goal and goal-to-start). It utilizes hashing to detect when the two search trees meet. To optimize performance, it includes "trimming" and "screening" techniques to prune nodes that cannot improve upon the current best solution, thereby conserving memory and computational time.
Empirical Evaluation
The authors evaluated MBBS using the standard 15-Puzzle benchmark, specifically the 100 instances published by Richard Korf. The performance was compared against several algorithms, including RBFS, WIDA, and HPA, under a fixed memory limit of 256,000 nodes.
Key Results
The empirical results highlighted the superiority of the bidirectional approach:
- Efficiency: MBBS generated significantly fewer nodes than unidirectional counterparts like WIDA* and RBFS across various solution qualities.
- Robustness: While classical bidirectional algorithms like HPA* often failed under strict memory limits, MBBS remained effective due to its inherent memory-bounding mechanisms.
- The Power of $\epsilon$: By allowing a small margin of error ($\epsilon > 0$), the computational cost dropped exponentially. For instance, at $\epsilon = 0.25$, MBBS found solutions only 4% worse than optimal but did so 80 times faster than an optimal search.
Discussion and Insights
The research challenges the long-held belief that the primary difficulty in bidirectional search is the "meeting" of the fronts. Instead, the authors argue that the real bottleneck is the "cleanup" phase—the computational effort required to prove solution optimality after the fronts have met.
Furthermore, the transition from tree search to graph search in a memory-bounded context is non-trivial. The "blocking" mechanism introduced in WSMAG* is essential for preventing infinite loops when nodes are deleted and subsequently rediscovered via better paths. While implementation complexity is high, the results suggest that for complex, real-world problems, the efficiency gains of memory-bounded bidirectional search are substantial.
Summary updated