D-Node Retargeting in Bidirectional Heuristic Search

George Politowski, Ira PohlAAAI 1984

Introduction

Bidirectional search is a classic concept in artificial intelligence pathfinding. Theoretically, searching from both the start and the goal simultaneously should be significantly more efficient than a unidirectional search, as the search frontiers grow exponentially. However, in practice, bidirectional heuristic search often performs poorly, sometimes even worse than simple unidirectional A. This 1984 paper from the AAAI proceedings identifies the root cause of this inefficiency and proposes a novel solution: D-Node Retargeting*.

The "Miss in the Middle" Problem

The primary issue with traditional bidirectional search lies in how the search is "aimed." In a standard implementation, the forward search is guided by a heuristic toward the goal node (the root of the backward tree), while the backward search is guided toward the start node.

As the search progresses, the actual frontiers of these two trees move away from their respective roots. Because the trees are aimed at static points behind the opposing frontier, they often "miss" each other in the middle. Instead of colliding to form a path, they essentially perform two independent, inefficient unidirectional searches that pass each other by.

Conceptual visualization of search frontiers and the difficulty of meeting in the middle.

D-Node Retargeting: Aiming at the Frontier

The authors introduce "d-node retargeting" to force the search trees to actually meet. Instead of aiming at a static root, the algorithm periodically selects a representative "d-node" (direction node) from the frontier of the opposite tree to act as the new target.

Key Mechanisms

  1. D-Node Selection: The d-node is chosen as the node in the current search frontier with the highest $g$ value (the node furthest from its own root). This "scout" is statistically the most likely to be closest to the opposing frontier.
  2. Periodic Updates: To maintain computational efficiency, the target is not updated every step. The algorithm advances $n$ moves (empirically set to 75) before re-evaluating and selecting a new d-node.
  3. Heuristic Re-aiming: Once a new d-node is selected, the heuristic values for nodes on the opposite front are updated to aim toward this new, moving target.

This approach avoids the "computational ruin" of previous methods that tried to compare every node on one frontier to every node on the other. D-node retargeting requires only one comparison per node generated.

Experimental Evaluation

The algorithm was tested using the 15-puzzle benchmark across 50 problems of varying difficulty. The researchers evaluated performance using four different heuristic functions ($h=1$ to $h=4$) and three different weightings ($w = 0.5, 0.75, 1.0$) in the evaluation function $f = (1-w)g + wh$.

Key Findings

The results demonstrated that d-node retargeting is a robust and highly efficient method. It consistently outperformed both unidirectional search and previous bidirectional algorithms like Pohl’s method and de Champeaux’s BHFFA.

Table 1: Performance metrics for the D-node algorithm across various heuristics and weights.

As shown in the experimental data, the algorithm's success rate (S) and efficiency (nodes expanded M, nodes generated N) vary significantly with the choice of heuristic and weight. Notably, the d-node method was typically 10 to 20 times faster in CPU time than BHFFA and expanded roughly half as many nodes as Pohl’s algorithm.

Conclusion

D-node retargeting addresses a fundamental flaw in bidirectional heuristic search by replacing static targets with dynamic ones based on the opposing search frontier. While the authors focused on search efficiency over absolute admissibility (shortest path guarantees), the method's dramatic speedup and reduced node expansion make it a significant contribution to pathfinding literature.

Summary updated

BibTeX
@inproceedings{politowski1984d,
  author = {George Politowski and Ira Pohl},
  title = {{D-Node Retargeting in Bidirectional Heuristic Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure