# Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions

arXiv: https://arxiv.org/abs/1703.03868 · HTML: https://mlsanity.com/paper/1703.03868/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2017.

## Built on by (most cited first, 4 of 4)

- [S^*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding](https://mlsanity.com/paper/2103.08155/) (2021)
- [Structure-Augmented Reasoning Generation](https://mlsanity.com/paper/2506.08364/) (2025)
- [On Parallel External-Memory Bidirectional Search](https://mlsanity.com/paper/2412.21104/) (2024)
- [Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search](https://mlsanity.com/paper/2606.07047/) (2026)

## Abstract (arXiv)

It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a consistent heuristic. Such states are called "surely expanded" (s.e.). A recent study characterized s.e. pairs of states for bidirectional search with consistent heuristics: if a pair of states is s.e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s.e. pairs, and present a new admissible front-to-end bidirectional heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.