Abstract
Bidirectional Heuristic Search (Bi-HS) is a powerful technique for pathfinding, yet it often suffers from sub-optimal frontier expansion strategies and counter-intuitive performance anomalies where stronger heuristics lead to more node expansions. This paper introduces DVCBS (Dynamic Vertex Cover Bidirectional Search), an algorithm that minimizes expansions by solving a dynamic vertex cover problem on search frontiers. Additionally, the authors propose lb-propagation, a general technique that shares lower-bound information between frontiers to ensure search algorithms are "well-behaved" and "reasonable." Experimental results across multiple domains, including the Pancake Puzzle and Towers of Hanoi, demonstrate that these methods significantly reduce node expansions and eliminate performance anomalies.
Introduction
In pathfinding, searching simultaneously from both the start and the goal—Bidirectional Heuristic Search (Bi-HS)—is intuitively appealing. However, optimizing Bi-HS involves overcoming two significant hurdles: the Meeting Problem (deciding which frontier to expand) and the Hump-in-the-Middle Anomaly (where better heuristics paradoxically degrade performance). This research addresses these issues by leveraging the theoretical "Must-Expand Graph" ($G_{MX}$), which identifies the minimal set of node pairs necessary to guarantee an optimal solution.
Dynamic Vertex Cover Bidirectional Search (DVCBS)
The state-of-the-art NBS (Near-optimal Bidirectional Search) algorithm expands both nodes in a "must-expand pair" during each iteration. To improve upon this, the authors propose DVCBS. This algorithm models the search as a Minimum Vertex Cover (MVC) problem on a bipartite graph representing the search frontiers.
By maintaining a Dynamic $G_{MX}$ (DGMX) based on current lower bounds, DVCBS greedily expands nodes belonging to the minimum vertex cover. To manage computational overhead, the algorithm expands clusters of nodes with identical costs. This strategy allows DVCBS to more surgically select nodes for expansion compared to previous approaches. As shown in experimental evaluations, DVCBS consistently reduces the number of nodes expanded across various domains, often outperforming NBS by a significant margin.
lb-propagation: Enhancing Heuristics Dynamically
A core contribution of the paper is lb-propagation. This technique defines a lower bound ($lb$) for any node $u$ as the minimum cost of a path through $u$ connecting the two search frontiers. By propagating this $lb$ information from the opposite frontier, the algorithm can dynamically update a node's heuristic ($h$-value).
This method ensures that algorithms become:
- Well-behaved: Stronger heuristics always lead to better or equal performance.
- Reasonable: The search never expands nodes that are demonstrably more expensive than the optimal solution.
lb-propagation can be integrated into existing Bi-HS algorithms like MM or BHPA, effectively turning static heuristics into dynamic ones that "learn" from the progress of the opposing search frontier.
Experimental Results
The authors evaluated their methods on standard benchmarks, including the 14-Pancake Puzzle, 15 Puzzle, Towers of Hanoi (TOH4), and Grid-based pathfinding from Dragon Age: Origins.
Solving the Anomaly
The "hump-in-the-middle" anomaly was effectively eliminated. By forcing algorithms to respect the global lower bound via lb-propagation, the performance curves were smoothed. As shown in the 10-pancake experiments, the inclusion of $lb$ information ensures that stronger heuristics consistently result in fewer node expansions, removing the erratic spikes seen in standard Bi-HS implementations.
Performance Gains
DVCBS consistently outperformed NBS. In the 14-Pancake puzzle with a GAP-2 heuristic, DVCBS reduced expansions from ~137,000 to ~87,000. Similarly, lb-propagation provided massive speedups when applied to other algorithms. In some cases, node expansions were reduced by up to a factor of four, demonstrating the power of sharing lower-bound information across search frontiers.
Conclusion
By viewing bidirectional search through the lens of vertex cover and introducing dynamic heuristic updates via lb-propagation, this work provides a more principled and robust framework for Bi-HS. While DVCBS currently lacks the strict "2x optimal" theoretical bound of NBS, its empirical performance is superior. Future work may focus on reducing the computational overhead of calculating vertex covers and scaling these techniques to even more complex problem domains.
Summary updated