Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search
This work improves the efficiency of bidirectional search algorithms for AI planning and heuristic search, offering a practical trade-off between heuristic quality and computational cost.
The authors introduce a new heuristic class, front-to-attractors (F2A), for bidirectional search that reduces computational overhead of front-to-front heuristics while preserving informativeness. F2A reduces pairwise evaluations by up to 11.2x compared to F2F and achieves 4.8x fewer node expansions than F2E on average.
Heuristics play a central role in the performance of bidirectional search algorithms, which commonly rely on two main classes. Front-to-end (F2E) heuristics estimate the distance from a state s to the target of the search (the goal for forward search or the start for backward search). In contrast, front-to-front (F2F) heuristics estimate the distance from s to the opposite search frontier using a pairwise function h(s, s'), where s' ranges over frontier states. Although F2F heuristics are typically more informative and therefore reduce the number of node expansions, their reliance on extensive pairwise evaluations incurs substantial computational overhead. To address this limitation, we introduce a new heuristic class, front-to-attractors (F2A), that preserves much of the informativeness of F2F while dramatically reducing its computational cost. Rather than evaluating distances to all states on the opposite frontier, F2A estimates the distance from s to a small, dynamically maintained set of attractors in the opposite search direction. These attractors serve as a surrogate for the full frontier, enabling rich heuristic guidance at a fraction of the computational expense while maintaining the optimality guarantees offered by F2F. We evaluate F2A across multiple domains and show that it reduces the number of pairwise evaluations by up to 11.2x compared to F2F, while achieving 4.8x fewer node expansions than F2E on average.