Back to AI Research

AI Research

Front-to-Attractors: Modifying the Front-to-Front H... | AI Research

Key Takeaways

  • Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search Bidirectional heuristic search is a technique used to find the shortest p...
  • 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.
Paper AbstractExpand

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.

Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search
Bidirectional heuristic search is a technique used to find the shortest path between two points by running two simultaneous searches: one from the start toward the goal, and one from the goal toward the start. A key factor in the speed of these algorithms is the "heuristic," a guide that estimates the remaining distance to the target. While some heuristics look only at the final destination (Front-to-End), others look at the opposite search frontier (Front-to-Front) to provide more accurate guidance. This paper introduces a new class of heuristics called Front-to-Attractors (F2A), which provides the high-quality guidance of Front-to-Front methods while significantly reducing the heavy computational work required to calculate those estimates.

The Challenge of Pairwise Evaluations

In bidirectional search, Front-to-Front (F2F) heuristics are highly effective because they consider the progress of the opposite search frontier. However, they are computationally expensive. To calculate the heuristic for a single state, the algorithm must perform a "pairwise evaluation" against every single state currently in the opposite frontier. As the search progresses and the number of states in the frontier grows, the time required to compute these heuristics increases, often slowing down the overall planning process.

How Front-to-Attractors Works

The F2A approach solves this by using "attractors"—a small, dynamically maintained set of representative states that act as a surrogate for the entire opposite frontier. Instead of comparing a state against every single point in the opposite frontier, the algorithm only compares it against these few active attractors. Because these attractors are strategically chosen to represent the current best paths, they provide rich, accurate guidance similar to the full frontier, but at a fraction of the computational cost. The algorithm also includes specific logic to update these attractors during the search, ensuring they remain relevant as the search space evolves.

Key Results and Performance

The researchers tested F2A across several domains, including 2D grid pathfinding, the Sliding Tiles puzzle, and the Pancake puzzle. The results demonstrate that F2A successfully strikes a balance between search guidance and computational efficiency. Across the tested domains, F2A reduced the number of required pairwise heuristic evaluations by up to 11.2 times compared to traditional F2F methods. Furthermore, it achieved an average of 4.8 times fewer node expansions than Front-to-End (F2E) methods, proving that it maintains strong guidance while being much faster to compute.

Important Considerations

While F2A is designed to be efficient, the authors note that the quality of the heuristic depends on how well the attractors represent the frontier. In some scenarios, a naive implementation might cause the attractors to become less informative, effectively causing the heuristic to "degenerate" into a simpler Front-to-End calculation. To prevent this, the researchers introduced two specific optimizations—New Attractor (NA) and Associated States (AS)—which help keep the attractors close to the frontier and ensure the heuristic remains accurate throughout the search process.

Comments (0)

No comments yet

Be the first to share your thoughts!