Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

Alex Fukunaga

cs.AISep 20, 2026

Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

Authors: Alex Fukunaga

Organizations: The University of Tokyo

Abstract

In the A* search algorithm, the tie-breaking strategies for nodes with the same $f$ -value determines which states A* expands on the final $f$ -layer. For nine standard tie-breaking strategies, we show that under a consistent heuristic, every pair has positive-cost instances favoring each strategy over the other by an arbitrarily large additive expansion gap. A parameterized unit-cost grid example also gives unbounded expansion-count ratios between low- $h$ with FIFO and LIFO. In unit-cost search with $h > 0$ at non-goals, exact heuristic values near the goal lead to complementary extremal results: low- $h$ minimizes the number of remaining expansions from a common configuration within the perfect region, while high- $h$ maximizes the total number of expansions when every final-plateau state with $h=1$ is a goal predecessor. Finally, with the evaluation function $f_α = g + αh$ , when $h>0$ at non-goals, every heuristic weight $0 \leq α<1$ eliminates tie-breaking sensitivity, and all tie-breaking strategies expand the same set of states.

Figures & tables

Panel of Figure 1 — Figure 1: The star construction. Every state has $f^{*}=C^{*}$ . After expanding $s$ , the $M+1$ states in $U$ are tied non-goals in $\mathrm{OPEN}$ . Among the states in $U$ , only $p$ has a successor, namely the goal $G$ . The expansion count is $2$ plus the number of dead ends selected before $p$ .

Panel of Figure 2 — Figure 2: The grid family, shown for $m=3$ . White cells form the unique optimal solution path, lightly shaded cells form the cul-de-sac, and dark cells are blocked. The successor order is Up, Right, Down, Left in both panels. In panel (a), $[h,\mathrm{FIFO}]$ enters the solution corridor first and expands $10$ states, whereas $[h,\mathrm{LIFO}]$ enters the cul-de-sac first and expands $27$ . Transposition reverses their roles in panel (b). The selected goal is not counted as an expansion.

Panel of Figure 3 — Figure 3: Perfect Manhattan-distance values near the goal. In panel (a), every state in the shaded radius- $3$ neighborhood has a path that decreases $h$ by one at each step. In panel (b), an obstacle forces a detour from $v$ : the heuristic is perfect at $h=1$ , but not at $h=2$ .

Panel of Figure 4 — Figure 4: Heuristic savings without tie-breaking sensitivity below unit weight, and distinct expansion counts at unit weight. Edge labels are costs; state labels give $h$ ; shaded leaves are dead ends. All rows use goal preference, and selecting $G$ is not counted as an expansion.

Tree Search

Tree Search explores branching sequences of actions or decisions to find high-quality solutions under limits on time, memory, or computation.

See all 57 papers

Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search
Jun 5, 2026Alvin Zou, Muhammad Suhail Saleem, Maxim LikhachevTree Search
Carnegie Mellon University
Smoothed Analysis of Inconsistent A*
Sep 20, 2026Zhiyang Chen, Hailong YaoGraph-Based Planning
Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction
Jul 25, 2026Taiquan SuiGraph-Based Planning
Department of Computer Science and Engineering, Chalmers University of Technology, Gothenburg, Sweden

Jun 5, 2026J/K move · Enter open · S save

Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search

Alvin Zou, Muhammad Suhail Saleem, Maxim Likhachev

Carnegie Mellon University

Tree Search

Open paper AskPDF arXiv

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.

Abstract

Tree Search

Explore similar work

Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search

Smoothed Analysis of Inconsistent A*

Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction