Papers for

path planning developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Tie-breaking choices strongly affect A star search node expansions

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

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.

Sun 20 SeptArtificial Intelligence
The gist
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.
Open → 2609.23293v1