Tie-breaking choices strongly affect A star search node expansions
Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau
Artificial Intelligence
Summary
When computers try to find the best path using A* search, they often have to decide between several equally good options. This paper shows that the way the algorithm breaks ties between these options can hugely change how many states it examines, sometimes making one method much better than another. The authors prove this is true for several common tie-breaking methods under certain conditions. They also find situations where a special formula in the search removes the need to break ties at all.
What this means in practice
- •For path planning developers: Choose tie-breaking methods in A* implementations to significantly reduce redundant state expansions in navigation systems.
- •For game ai programmers: Optimize A* tie-breaking choices in game pathfinding to balance computation and responsiveness based on heuristic properties.
A theory result. No direct application yet.
Authors
Alex Fukunaga
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.