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

# Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau
Source: [https://arxiv.org/html/2609.23293](https://arxiv.org/html/2609.23293)
###### Abstract

In the A\* search algorithm, the tie\-breaking strategies for nodes with the sameff\-value determines which states A\* expands on the finalff\-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\-hhwith FIFO and LIFO\. In unit\-cost search withh\>0h\>0at non\-goals, exact heuristic values near the goal lead to complementary extremal results: low\-hhminimizes the number of remaining expansions from a common configuration within the perfect region, while high\-hhmaximizes the total number of expansions when every final\-plateau state withh=1h=1is a goal predecessor\. Finally, with the evaluation functionfα=g\+α​hf\_\{\\alpha\}=g\+\\alpha h, whenh\>0h\>0at non\-goals, every heuristic weight0≤α<10\\leq\\alpha<1eliminates tie\-breaking sensitivity, and all tie\-breaking strategies expand the same set of states\.

## 1Introduction

The A∗search algorithm for finding an optimal\-cost path from a start state to a goal state in a graph orders states according to the evaluation functionf=g\+hf=g\+h, whereggis the cost of the current path from the initial state andhhestimates the remaining cost to a goal\([Hart et al\., 1968](https://arxiv.org/html/2609.23293#bib.bib9)\)\. Since multiple states inOPEN\\mathrm\{OPEN\}may have the same minimumff\-value, a complete algorithm specification requires a sequence of*tie\-breaking*criteria\. A common choice prefers smallerhhand resolves any remaining ties by insertion order \(FIFO, LIFO\) or by uniform random selection\. On an equal\-fftie, preferring smallerhhis equivalent to preferring largergg\.

For optimal search, previous work has investigated the performance of tie\-breaking strategies for A∗\. While A∗must expand all nodes withf<C∗f<C^\{\*\}, whereC∗C^\{\*\}is the cost of an optimal solution, the number of nodes expanded in the final plateau \(nodes withf=C∗f=C^\{\*\}\) is affected by the tie\-breaking strategy\.[Asai and Fukunaga \(2016\)](https://arxiv.org/html/2609.23293#bib.bib1);[Asai and Fukunaga \(2017b\)](https://arxiv.org/html/2609.23293#bib.bib3)experimentally evaluated the performance of FIFO, LIFO, random, high\-gg, and low\-ggtie\-breaking policies and proposed plateau\-depth\-based rules \.[Corrêa et al\. \(2018\)](https://arxiv.org/html/2609.23293#bib.bib6)proposed tie\-breaking based on cost adaptation\.

Despite the long history of A∗and the wide acknowledgment that tie\-breaking affects search efficiency, to our knowledge, formal analysis of tie\-breaking has received relatively little attention\.[Corrêa et al\. \(2018\)](https://arxiv.org/html/2609.23293#bib.bib6)showed that optimal tie\-breaking strategies can expand fewer nodes than some common tie\-breaking strategies\. However, pairwise relationships among the most commonly used tie\-breaking strategies which are based ongg\-values and order of entry intoOPEN\\mathrm\{OPEN\}have not been systematically analyzed\.

We analyze expansion counts under standard tie\-breaking strategies based onhh\-values and insertion order intoOPEN\\mathrm\{OPEN\}\. We make three contributions\.

The first contribution is a pairwise incomparability result\. For nine standard strategies formed from FIFO, LIFO, uniform random selection, and low\-hhor high\-hhcriteria, a single parameterized construction with a consistent heuristic and positive edge costs yields arbitrarily large expansion gaps in both directions\. The deterministic comparisons hold for expanded sets as well as counts; comparisons involving randomization use exact expectations\. In other words, none of these nine standard tie\-breaking rules dominate the others in general\. Unbounded gaps among standard tie\-breaking rules can be found even in familiar domains, as a parameterized example on four\-neighbor unit\-cost grids with Manhattan distance and a fixed successor order gives unbounded additive gaps and expansion\-count ratios between\[h,FIFO\]\[h,\\mathrm\{FIFO\}\]and\[h,LIFO\]\[h,\\mathrm\{LIFO\}\]\. Transposing the grid reverses which strategy expands fewer states\.

The second contribution identifies extremal strategies under a local accuracy condition on the heuristic\. In unit\-cost search withh\>0h\>0at non\-goals, suppose thathhis perfect on final\-plateau states withh≤kh\\leq k\. From a common search configuration whose minimum eligiblehh\-value ism≤km\\leq k, every low\-hhstrategy performs exactlymmfurther expansions, and is minimal, i\.e\., no continuation performs fewer expansions\. The guarantee concerns the*remaining*expansions; when the condition holds at entry to the final plateau, the continuation guarantee yields global expansion optimality\. Furthermore, under the weaker condition that every final\-plateau state withh=1h=1is a goal predecessor, every high\-hhstrategy attains the maximum*total*expansion count, independently of its final tie\-breaker\.

Finally, we elucidate how the tie\-breaking\-dependent search on the final plateauf=C∗f=C^\{\*\}arises, by considering search using the weighted evaluation functionfα=g\+α​hf\_\{\\alpha\}=g\+\\alpha h\. Whenh\>0h\>0at non\-goals, every underweighted heuristic search with weight0≤α<10\\leq\\alpha<1expands the same set of states, regardless of tie\-breaking, The common expanded set for0<α<10<\\alpha<1contains the states expanded by ordinary A∗and is contained in the uniform\-cost expanded set, so the disappearance of tie\-breaking sensitivity comes from making formerly optional final\-layer states compulsory\. Thus, there is a sharp boundary at the standard A∗weightα=1\\alpha=1, which restores a final layer on which tie\-breaking can affect the expanded set; indeed, as shown by the first contribution, the resulting expansion gap can be arbitrarily large\.

## 2Preliminaries and Previous Expansion Bounds

We begin by describing the graph\-search model, tie\-breaking, and comparison criteria, then recalling the classical expansion bounds used in the subsequent analysis\.

### 2\.1Search model

A search instance isI=\(V,A,c,s,𝒢,h\)I=\(V,A,c,s,\\mathcal\{G\},h\), where\(V,A\)\(V,A\)is a finite directed graph,c:A→ℝ≥0c:A\\to\\mathbb\{R\}\_\{\\geq 0\}assigns transition costs,s∉𝒢s\\notin\\mathcal\{G\}is the initial state, and𝒢\\mathcal\{G\}is the set of goals\. The heuristich:V→ℝh:V\\to\\mathbb\{R\}is state\-based\. Letg∗​\(v\)g^\{\*\}\(v\)be the least cost of a path fromsstovv, and leth∗​\(v\)h^\{\*\}\(v\)be the least cost fromvvto a goal; either is\+∞\+\\inftyif no such path exists\. We assume that the instance is solvable and writeC∗=h∗​\(s\)<\+∞C^\{\*\}=h^\{\*\}\(s\)<\+\\infty\.

A heuristichhis*perfect*ifh​\(v\)=h∗​\(v\)h\(v\)=h^\{\*\}\(v\)for every statevv\. More generally,hhis*perfect on a setW⊆VW\\subseteq V*ifh​\(v\)=h∗​\(v\)h\(v\)=h^\{\*\}\(v\)for everyv∈Wv\\in W\.

Unless stated otherwise,hhis consistent,

h⁡\(u\)≤c⁡\(u,v\)\+h⁡\(v\)\(\(u,v\)∈A\),h\(u\)\\leq c\(u,v\)\+h\(v\)\\qquad\(\(u,v\)\\in A\),andh⁡\(G\)=0h\(G\)=0for every goalGG\. These conditions imply admissibility,h⁡\(v\)≤h∗​\(v\)h\(v\)\\leq h^\{\*\}\(v\)\. Positivity at non\-goals is assumed only where stated\. Successors are generated in a fixed order, which is part of the instance and is identical in every comparison on that instance\.

A∗maintainsOPEN\\mathrm\{OPEN\}andCLOSED\\mathrm\{CLOSED\}, with at most one currentOPEN\\mathrm\{OPEN\}entry per state\. An entry stores its best knowngg\-value, parent, first\-insertion timestamp, and goal status\. Expanding a non\-goal state removes it fromOPEN\\mathrm\{OPEN\}, adds it toCLOSED\\mathrm\{CLOSED\}, and generates all its successors\. A newly encountered state is goal\-tested and inserted\. A strictly smaller tentativeggupdates an existing entry and its parent, but*preserves its first\-insertion timestamp*; equal\- and higher\-cost duplicates are discarded\. Consistency ensures that an expanded state hasg=g∗g=g^\{\*\}and is never reopened\. Stale priority\-queue records, if retained by an implementation, are ignored and do not count as expansions\.

The goal test is evaluated at generation, including for the initial state\. Search terminates only when a goal is selected fromOPEN\\mathrm\{OPEN\}\. At a selection point, define

OPENmin=arg​minv∈OPEN⁡\{g⁡\(v\)\+h⁡\(v\)\}\.\\mathrm\{OPEN\}\_\{\\min\}=\\operatorname\*\{arg\\,min\}\_\{v\\in\\mathrm\{OPEN\}\}\\\{g\(v\)\+h\(v\)\\\}\.IfOPENmin\\mathrm\{OPEN\}\_\{\\min\}contains a goal, a goal is selected immediately; otherwise a tie\-breaker selects a non\-goal inOPENmin\\mathrm\{OPEN\}\_\{\\min\}for expansion\. We call the states ofOPENmin\\mathrm\{OPEN\}\_\{\\min\}*eligible*at that selection point\. Selecting a goal is not counted as an expansion\. A generated goal with largerffremains inOPEN\\mathrm\{OPEN\}and does not cause termination\.

This goal\-preference convention is standard in analyses of A∗tie\-breaking\([Dechter and Pearl, 1985](https://arxiv.org/html/2609.23293#bib.bib7);[Corrêa et al\., 2018](https://arxiv.org/html/2609.23293#bib.bib6)\)\. Adding it to a minimum\-ffsearch cannot increase its expansion count: under otherwise identical choices, the two runs share a prefix, after which the goal\-preferring run may terminate while the other continues\.

Our comparisons hold the graph, heuristic, successor order, duplicate handling, and goal\-preference rule fixed\. The importance of specifying all levels of tie\-breaking is also emphasized by[Barley et al\. \(2025\)](https://arxiv.org/html/2609.23293#bib.bib4), who show that incomplete descriptions can lead to irreproducible and misleading comparisons in optimal bidirectional heuristic search\. Here, these conventions isolate the expansion effects of the tie\-breaking rules being compared\.

### 2\.2Tie\-breaking and comparisons

Tie\-breaking criteria are applied lexicographically afterffand goal preference\. We omit these two common criteria when naming a strategy\. Thus\[h,FIFO\]\[h,\\mathrm\{FIFO\}\]denotes low\-hhfollowed by FIFO, and\[−h,LIFO\]\[\-h,\\mathrm\{LIFO\}\]denotes high\-hhfollowed by LIFO\. The full ordering for\[h,FIFO\]\[h,\\mathrm\{FIFO\}\]is\[f,goal preference,h,FIFO\]\[f,\\text\{goal preference\},h,\\mathrm\{FIFO\}\]\. FIFO and LIFO select the earliest and latest first\-insertion timestamps, respectively\. RANDOM samples uniformly from the states left tied by all preceding criteria, independently at each selection\. The terms*low\-hh*and*high\-hh*name criteria, whereas\[h,τ\]\[h,\\tau\]and\[−h,τ\]\[\-h,\\tau\]name strategies with a specified final tie\-breakerτ\\tau\.

At equalff, minimizinghhis equivalent to maximizinggg, and maximizinghhis equivalent to minimizinggg\. The distinction between smaller\-ggand larger\-ggtie\-breaking also appears in incremental search:[Likhachev and Koenig \(2005\)](https://arxiv.org/html/2609.23293#bib.bib15)generalize Lifelong Planning A∗to support larger\-ggtie\-breaking, among other extensions\. Our comparisons concern ordinary, non\-incremental A∗\.

LetEτ​\(I,ρ\)E\_\{\\tau\}\(I;\\rho\)be the set of non\-goal states expanded by strategyτ\\tau, and letXτ​\(I,ρ\)X\_\{\\tau\}\(I;\\rho\)be its expansion count, for random outcomeρ\\rho\. Since there are no re\-expansions,Xτ=\|Eτ\|X\_\{\\tau\}=\|E\_\{\\tau\}\|\. We omitρ\\rhofor deterministic runs\. For deterministic strategies,*set dominance*on an instance class meansEτ1​\(I\)⊆Eτ2​\(I\)E\_\{\\tau\_\{1\}\}\(I\)\\subseteq E\_\{\\tau\_\{2\}\}\(I\)on every instance, with a strict inclusion on at least one\.*Expansion\-count dominance*replaces inclusion byXτ1​\(I\)≤Xτ2​\(I\)X\_\{\\tau\_\{1\}\}\(I\)\\leq X\_\{\\tau\_\{2\}\}\(I\); for randomized strategies, we compare expectations\. We establish*pairwise incomparability*by giving instances with strict count inequalities in both directions\. This also rules out set dominance in either direction for deterministic strategies; the converse implication need not hold\. An additive gap is unbounded when it exceeds every prescribed integer on some instance\. Expectations are over a strategy’s random choices on a fixed instance, not over a distribution of instances\.

### 2\.3Compulsory expansions and the final plateau

Definef∗​\(v\)=g∗​\(v\)\+h⁡\(v\)f^\{\*\}\(v\)=g^\{\*\}\(v\)\+h\(v\), where the superscript refers to the optimal cost from the initial state, not to use of a perfect heuristic\. For reachable non\-goal states, let

S<=\{v∉𝒢:f∗​\(v\)<C∗\},S==\{v∉𝒢:f∗\(v\)=C∗\},S≤=S<∪S=\.\\begin\{split\}S\_\{<\}&=\\\{v\\notin\\mathcal\{G\}:f^\{\*\}\(v\)<C^\{\*\}\\\},\\\\ S\_\{=\}&=\\\{v\\notin\\mathcal\{G\}:f^\{\*\}\(v\)=C^\{\*\}\\\},\\qquad S\_\{\\leq\}=S\_\{<\}\\cup S\_\{=\}\.\\end\{split\}The states inS<S\_\{<\}are*surely expanded*\. We callS=S\_\{=\}the non\-goal finalff\-layer and use*final plateau*for search atf=C∗f=C^\{\*\}, including any eligible optimal goals\. We restate the classical expansion bounds in this notation\([Dechter and Pearl, 1985](https://arxiv.org/html/2609.23293#bib.bib7)\)\.

###### Lemma 1\(A∗expansion bounds; after[Dechter and Pearl \(1985\)](https://arxiv.org/html/2609.23293#bib.bib7)\)\.

Every run of the modeled A∗algorithm satisfies

S<⊆Eτ​\(I,ρ\)⊆S≤\.S\_\{<\}\\subseteq E\_\{\\tau\}\(I;\\rho\)\\subseteq S\_\{\\leq\}\.All states inS<S\_\{<\}are expanded before any state inS=S\_\{=\}\.

###### Proof\.

Consistency gives the optimal\-ggproperty at expansion and nondecreasing selectedff\-values\. Before termination, a frontier state on an optimal solution path is inOPEN\\mathrm\{OPEN\}withf≤C∗f\\leq C^\{\*\}, so no state withf∗\>C∗f^\{\*\}\>C^\{\*\}is expanded\. Forv∈S<v\\in S\_\{<\},f∗f^\{\*\}is nondecreasing along a shortest path tovv\. Each state on that path hasf∗<C∗f^\{\*\}<C^\{\*\}and must be generated with its optimalggand expanded before a goal, whoseff\-value is at leastC∗C^\{\*\}\. The same reasoning forces these states before any expansion atf=C∗f=C^\{\*\}\. ∎

The distinction between compulsory and final\-layer expansions matters when interpreting comparisons of search effort: comparingS<S\_\{<\}alone does not determine total expansion counts\. In particular,[Holte \(2010\)](https://arxiv.org/html/2609.23293#bib.bib13)shows that a more accurate heuristic need not reduce the total number of A∗expansions\. Our pairwise comparisons hold the heuristic fixed and vary only the specified tie\-breaking criteria\.

An instance is*nonpathological*with respect tohhif it has an optimal solution path withh​\(v\)<h∗​\(v\)h\(v\)<h^\{\*\}\(v\)at every non\-goal state on the path\([Dechter and Pearl, 1985](https://arxiv.org/html/2609.23293#bib.bib7)\)\. Otherwise it is*pathological*\. LetΠ∗\\Pi^\{\*\}be the simple optimal paths whose only goal is their last state, and define

ℓ∗​\(I\)=minπ∈Π∗⁡\|\(π∖𝒢\)∩S=\|\.\\ell^\{\*\}\(I\)=\\min\_\{\\pi\\in\\Pi^\{\*\}\}\|\(\\pi\\setminus\\mathcal\{G\}\)\\cap S\_\{=\}\|\.
The following proposition states the classical minimum\-expansion characterization in the model used in this paper\. All runs considered here return an optimal\-cost solution; expansion optimality instead concerns search effort, measured by the number of non\-goal states expanded\. We call a run*expansion\-minimal*onIIif no other run of the modeled A∗algorithm expands fewer non\-goal states on the same instance\.

###### Proposition 1\(Minimum\-expansion characterization; after[Dechter and Pearl \(1985\)](https://arxiv.org/html/2609.23293#bib.bib7)\)\.

Every run satisfies

Xτ​\(I,ρ\)≥\|S<\|\+ℓ∗​\(I\),X\_\{\\tau\}\(I;\\rho\)\\geq\|S\_\{<\}\|\+\\ell^\{\*\}\(I\),and an instance\-dependent deterministic tie\-breaker attains equality\. Hence

\|S<\|\+ℓ∗​\(I\)\|S\_\{<\}\|\+\\ell^\{\*\}\(I\)is the minimum expansion count achievable by the modeled A∗algorithm onII\.

Moreover, the following are equivalent: the instance is nonpathological;ℓ∗​\(I\)=0\\ell^\{\*\}\(I\)=0; some run expands exactlyS<S\_\{<\}; every run expands exactlyS<S\_\{<\}\.

###### Proof\.

The parent\-pointer chain of the selected optimal goal is an optimal path, and each of its non\-goal states was expanded\. Lemma[1](https://arxiv.org/html/2609.23293#Thmlemma1)also forces all ofS<S\_\{<\}, giving the lower bound\. Choose a path attainingℓ∗\\ell^\{\*\}\. Consistency makes its states inS=S\_\{=\}a final segment\. AfterS<S\_\{<\}has been expanded, an instance\-dependent tie\-breaker can select the states of this segment in path order, then select the generated goal\. It expands exactly\|S<\|\+ℓ∗\|S\_\{<\}\|\+\\ell^\{\*\}states\.

On an optimal path,f∗​\(v\)<C∗f^\{\*\}\(v\)<C^\{\*\}is equivalent toh​\(v\)<h∗​\(v\)h\(v\)<h^\{\*\}\(v\), so nonpathology is equivalent toℓ∗=0\\ell^\{\*\}=0\. In that case, an optimal goal is generated fromS<S\_\{<\}and is selected before any non\-goal inS=S\_\{=\}\. Every run therefore expands exactlyS<S\_\{<\}\. Conversely, the parent\-pointer path of any run expanding onlyS<S\_\{<\}hasℓ∗=0\\ell^\{\*\}=0\. ∎

The minimum is over all tie\-breaking rules allowed by our A∗model\. Such a rule may use instance\-specific information, including information about states that have not yet been generated, and may differ from the standard strategies studied next\. The existence of an expansion\-minimal rule therefore does not establish a dominance relation between any two fixed strategies\.

## 3Pairwise Incomparability

This section establishes unbounded worst\-case separation in the number of expansions among the standard tie\-breaking rules\.

### 3\.1A final\-plateau construction

We start with a simple construction with unbounded branching factor\. The following construction lets us choose insertion order and heuristic values independently, while keeping all competing states tied on the primaryff\-value\. This lets us control FIFO/LIFO preferences and low\-hh/high\-hhpreferences separately, while RANDOM samples uniformly from the states left tied\.

###### Lemma 2\(Star construction\)\.

LetM≥1M\\geq 1be an integer,C\>0C\>0, and values0<h⁡\(u\)<C0<h\(u\)<CforU=\{p,b1,…,bM\}U=\\\{p,b\_\{1\},\\ldots,b\_\{M\}\\\}\. Construct a tree with initial statess, unique goalGG, edgess→us\\to ufor allu∈Uu\\in U, and one further edgep→Gp\\to G\. Set

h\(s\)=C,h\(G\)=0,c\(s,u\)=C−h\(u\),c\(p,G\)=h\(p\)\.\\begin\{gathered\}h\(s\)=C,\\qquad h\(G\)=0,\\\\ c\(s,u\)=C\-h\(u\),\\qquad c\(p,G\)=h\(p\)\.\\end\{gathered\}GenerateUUin any prescribed order\. All edge costs are positive;hhis admissible, consistent, zero at the goal, and positive at non\-goals\. Every state satisfiesf∗=C∗=Cf^\{\*\}=C^\{\*\}=C\. If a strategy expandskkof thebib\_\{i\}beforepp, thenXτ=2\+kX\_\{\\tau\}=2\+k\.

###### Proof\.

Each consistency inequality holds with equality\. The unique solution paths,p,Gs,p,Ghas costCC, andhhis perfect on it\. Eachbib\_\{i\}is a dead end withh∗​\(bi\)=\+∞h^\{\*\}\(b\_\{i\}\)=\+\\infty\. After expandingss, all members ofUUare known non\-goals inOPENmin\\mathrm\{OPEN\}\_\{\\min\}, withf=Cf=C\. Only expandingppgenerates a goal\. Goal preference then terminates search immediately, afterss, thekkdead ends, andpp\. ∎

ssppb1b\_\{1\}⋮\\vdotsbMb\_\{M\}GGC−h⁡\(p\)C\-h\(p\)C−h⁡\(b1\)C\-h\(b\_\{1\}\)h⁡\(p\)h\(p\)After expandingss,all states inUUareknown non\-goals atf=Cf=C\.GGis generated onlywhenppis expanded\.Figure 1:The star construction\. Every state hasf∗=C∗f^\{\*\}=C^\{\*\}\. After expandingss, theM\+1M\+1states inUUare tied non\-goals inOPEN\\mathrm\{OPEN\}\. Among the states inUU, onlypphas a successor, namely the goalGG\. The expansion count is22plus the number of dead ends selected beforepp\.Consider the nine strategies

𝒫=\{FIFO,LIFO,RANDOM,\[h,FIFO\],\[h,LIFO\],\[h,RANDOM\],\[−h,FIFO\],\[−h,LIFO\],\[−h,RANDOM\]\}\.\\begin\{split\}\\mathcal\{P\}=\\\{&\\mathrm\{FIFO\},\\mathrm\{LIFO\},\\mathrm\{RANDOM\},\[h,\\mathrm\{FIFO\}\],\[h,\\mathrm\{LIFO\}\],\[h,\\mathrm\{RANDOM\}\],\\\\ &\[\-h,\\mathrm\{FIFO\}\],\[\-h,\\mathrm\{LIFO\}\],\[\-h,\\mathrm\{RANDOM\}\]\\\}\.\\end\{split\}
###### Theorem 1\(Pairwise incomparability\)\.

On the positive\-cost trees of Lemma[2](https://arxiv.org/html/2609.23293#Thmlemma2), for every integerM≥1M\\geq 1:

1. \(i\)Every pair of distinct deterministic strategies in𝒫\\mathcal\{P\}has an instance with expansion counts22andM\+2M\+2, and another with these counts reversed\.
2. \(ii\)Every pair of distinct strategies in𝒫\\mathcal\{P\}involving at least one randomized strategy has an instance favoring each strategy in expected expansions, with an expected gap of at leastM/2M/2in each direction\.

All comparisons are decided before an optimal goal is generated\.

###### Proof\.

By Lemma[2](https://arxiv.org/html/2609.23293#Thmlemma2), it suffices to control the number of dead ends expanded beforepp\. Insertion order and the valuesh⁡\(u\)h\(u\)can be chosen independently\. Group strategies by their heuristic criterion: none, low\-hh, or high\-hh\.

If both strategies have the same heuristic criterion, they differ in the final FIFO, LIFO, or RANDOM rule\. Give all members ofUUequalhh\. Makingppfirst or last in insertion order reverses the deterministic FIFO/LIFO counts\. Under RANDOM, the rank ofppamongM\+1M\+1states is uniform, so the expected number of preceding dead ends isM/2M/2\. This gives both expected inequalities against either deterministic rule\.

If one strategy is low\-hhand the other high\-hh, makeppthe unique minimum\-hhstate and all dead ends higher, or makeppthe unique maximum\-hhstate and all dead ends lower\. These choices give counts22andM\+2M\+2in opposite directions, regardless of the final rule\.

It remains to compare a strategy with no heuristic criterion against one with a low\-hhor high\-hhcriterion\. If the former is FIFO or LIFO, choosepp’s insertion position to make it last for that strategy and itshh\-value to make it uniquely preferred by the latter\. Reversing both choices reverses the counts\. If the former is RANDOM, its expected count is2\+M/22\+M/2independently of thehh\-values; makingppuniquely preferred or disfavored by the heuristic criterion gives the two expected gaps ofM/2M/2\.

In each deterministic comparison, the expanded sets are\{s,p\}\\\{s,p\\\}and\{s,p,b1,…,bM\}\\\{s,p,b\_\{1\},\\ldots,b\_\{M\}\\\}, in opposite orders on the two instances\. The randomized comparisons follow from the uniform rank ofppin the cases where randomization affects its position\. ∎

When all members ofUUhave equalhh, RANDOM assigns a uniform rank toppamong theM\+1M\+1tied states\. Hence

XRANDOM−2∼Unif⁡\{0,…,M\},𝔼⁡\[XRANDOM\]=2\+M2\.X\_\{\\mathrm\{RANDOM\}\}\-2\\sim\\operatorname\{Unif\}\\\{0,\\ldots,M\\\},\\qquad\\mathbb\{E\}\[X\_\{\\mathrm\{RANDOM\}\}\]=2\+\\frac\{M\}\{2\}\.Movingppfrom first to last in insertion order reverses the FIFO and LIFO counts but does not change the RANDOM distribution\.

#### Unbounded expansion gaps with bounded branching\.

While this star construction uses an unbounded branching factor only to generate allM\+1M\+1tied states in a single expansion, this is not essential to the separation\. The same tied frontier can be generated with maximum out\-degree two by replacingsswith a forced chain: each chain state generates one member ofUUand the next chain state, with the chain states assignedf<C∗f<C^\{\*\}and the members ofUUassignedf=C∗f=C^\{\*\}\. A∗therefore expands the entire chain before selecting any member ofUU\. At that point, the members ofUUhave the prescribed insertion order and heuristic values, and the remainder of the search is exactly the star construction\. The forced prefix adds the same number of expansions to every strategy, so all pairwise additive gaps in Theorem[1](https://arxiv.org/html/2609.23293#Thmtheorem1)remain unchanged\.

### 3\.2Unbounded gaps on unit\-cost grids

The star construction above gives a simple proof of pairwise incomparability on an abstract structure, and shows that in general, none of the standard tie\-breaking rules dominate the other\. We next show that a large tie\-breaking effect also occurs under a familiar setting\. Figure[2](https://arxiv.org/html/2609.23293#S3.F2)illustrates large expansion gaps between\[h,FIFO\]\[h,\\mathrm\{FIFO\}\]and\[h,LIFO\]\[h,\\mathrm\{LIFO\}\]on four\-neighbor grids with unit costs and Manhattan distance\. Successors are generated in the fixed order Up, Right, Down, Left in both panels\.

In panel \(a\), the start has two branches: an L\-shaped corridor leading to the goal, and a cul\-de\-sac connected to the corridor only through the start\. For an integerm≥1m\\geq 1, scale the illustrated layout so that each leg of the solution corridor hasm\+2m\+2edges and the cul\-de\-sac consists of an\(m\+1\)×\(m\+1\)\(m\+1\)\\times\(m\+1\)square plus its entrance cell\. The solution path containsCm=2​m\+4C\_\{m\}=2m\+4non\-goal states, including the start, and the cul\-de\-sac containsDm=\(m\+1\)2\+1D\_\{m\}=\(m\+1\)^\{2\}\+1states\. Every traversable cell is reachable from the start by a monotone path toward the goal, sog∗​\(v\)\+h⁡\(v\)=C∗=2​m\+4g^\{\*\}\(v\)\+h\(v\)=C^\{\*\}=2m\+4throughout the grid\.

Expanding the start generates the corridor entrance first and the cul\-de\-sac entrance second\. These states tie in bothffandhh, so\[h,FIFO\]\[h,\\mathrm\{FIFO\}\]enters the corridor, whereas\[h,LIFO\]\[h,\\mathrm\{LIFO\}\]enters the cul\-de\-sac\. Once either entrance is expanded, that branch continues to offer eligible states with smallerhhthan the postponed entrance to the other branch\. Consequently, the corridor\-first run follows the solution path to the goal, while the cul\-de\-sac\-first run exhausts the cul\-de\-sac before entering the solution corridor\. The expansion counts are thereforeCmC\_\{m\}andCm\+DmC\_\{m\}\+D\_\{m\}, respectively\.

Panel \(b\) transposes the grid while retaining the same successor order\. This exchanges the roles of the two entrances, so\[h,LIFO\]\[h,\\mathrm\{LIFO\}\]now expandsCmC\_\{m\}non\-goals and\[h,FIFO\]\[h,\\mathrm\{FIFO\}\]expandsCm\+DmC\_\{m\}\+D\_\{m\}\. Thus either strategy can incur an additive gapDm=Θ⁡\(m2\)D\_\{m\}=\\Theta\(m^\{2\}\)and an expansion\-count ratio\(Cm\+Dm\)/Cm=Θ⁡\(m\)\(C\_\{m\}\+D\_\{m\}\)/C\_\{m\}=\\Theta\(m\)\.

ssaabbGG\(a\) FIFO favoredsolution pathCmC\_\{m\}expansionscul\-de\-sacDmD\_\{m\}statesssaabbGG\(b\) LIFO favoredsolution path:CmC\_\{m\}expansionscul\-de\-sacDmD\_\{m\}statesFigure 2:The grid family, shown form=3m=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,FIFO\]\[h,\\mathrm\{FIFO\}\]enters the solution corridor first and expands1010states, whereas\[h,LIFO\]\[h,\\mathrm\{LIFO\}\]enters the cul\-de\-sac first and expands2727\. Transposition reverses their roles in panel \(b\)\. The selected goal is not counted as an expansion\.

## 4Minimum\- and Maximum\-Expansion Tie\-Breaking with Locally Perfect Heuristics

The preceding section shows that in general, standard tie\-breaking strategies are incomparable, and that large tie\-breaking effects persist even on restricted unit\-cost instances\. However, with sufficiently strong constraints, it is possible to find interesting cases where some tie\-breaking strategies dominate others\. We now consider one such constraint: assume that the heuristic is perfect on specified low\-hhlayers of the final plateau\. This condition rules out the mechanism used by the star construction, where dead ends can receive small heuristic values, and yields strong guarantees for broad classes of tie\-breaking strategies\.

The guarantees depend only on whetherhhis minimized or maximized within the final plateau\. They hold independently of how remaining ties are resolved\. Thus, for an arbitrary final tie\-breakerτ\\tau, every low\-hhstrategy\[h,τ\]\[h,\\tau\]minimizes the number of remaining expansions once the search reaches the relevant perfect region\. Likewise, for an arbitrary final tie\-breakerσ\\sigma, every high\-hhstrategy\[−h,σ\]\[\-h,\\sigma\]maximizes the total number of expansions under the weaker assumption thathhis perfect onB1B\_\{1\}\. These statements also hold for every outcome when the final tie\-breaker is randomized\. Hence the results characterize the low\-hhand high\-hhclasses as a whole, rather than particular choices such as FIFO, LIFO, or RANDOM within those classes\.

Throughout this section, all edges have cost one, andhhis consistent, zero at goals, and strictly positive at non\-goals\. These are additional assumptions and are not properties of arbitrary A∗instances\. Sinceg∗g^\{\*\}andC∗C^\{\*\}are integers, every state inS=S\_\{=\}has a positive integer heuristic value\. For integersj,k≥1j,k\\geq 1, define

Bj=\{v∈S=:h⁡\(v\)=j\},B≤k=⋃j=1kBj\.B\_\{j\}=\\\{v\\in S\_\{=\}:h\(v\)=j\\\},\\qquad B\_\{\\leq k\}=\\bigcup\_\{j=1\}^\{k\}B\_\{j\}\.Requiringhhto be perfect on the final plateauB≤kB\_\{\\leq k\}imposes no additional accuracy condition outside that set\. In particular,hhis perfect onB1B\_\{1\}exactly when every final\-plateau state withh=1h=1is a goal predecessor\.

A*search configuration*HHincludesOPEN\\mathrm\{OPEN\},CLOSED\\mathrm\{CLOSED\}, currentgg\-values, parent pointers, and insertion timestamps\. At a selection point with minimumf=C∗f=C^\{\*\}and no goal inOPENmin\\mathrm\{OPEN\}\_\{\\min\}, write

m⁡\(H\)=min⁡\{h⁡\(v\):v∈OPENmin​\(H\)\}\.m\(H\)=\\min\\\{h\(v\):v\\in\\mathrm\{OPEN\}\_\{\\min\}\(H\)\\\}\.Goals with largerffmay be present\. Comparisons of continuations fromHHhold the entire configuration fixed\.

### 4\.1Low\-hhminimizes remaining expansions

Ifv∈Bjv\\in B\_\{j\}andh​\(v\)=h∗​\(v\)h\(v\)=h^\{\*\}\(v\), consider a successorwwon a shortest path to a goal\. Admissibility and consistency implyh⁡\(w\)=j−1h\(w\)=j\-1\. Moreover,g∗​\(w\)=g∗​\(v\)\+1g^\{\*\}\(w\)=g^\{\*\}\(v\)\+1: a cheaper path towwfollowed by the remainingj−1j\-1steps would yield a solution cheaper thanC∗C^\{\*\}\. Thusw∈Bj−1w\\in B\_\{j\-1\}whenj\>1j\>1, andwwis a goal whenj=1j=1\.

###### Theorem 2\(Optimal continuation by low\-hh\)\.

Suppose thathhis perfect onB≤kB\_\{\\leq k\}\. LetHHbe a reachable configuration with minimumf=C∗f=C^\{\*\}, no goal inOPENmin\\mathrm\{OPEN\}\_\{\\min\}, andm=m⁡\(H\)≤km=m\(H\)\\leq k\. Every low\-hhcontinuation\[h,τ\]\[h,\\tau\]performs exactlymmfurther non\-goal expansions\. Every tie\-breaking continuation from the sameHHperforms at leastmm\. Both statements hold for every outcome of any random choices\.

###### Proof\.

By Lemma[1](https://arxiv.org/html/2609.23293#Thmlemma1), all states inS<S\_\{<\}have already been expanded\. Every current minimum\-ffentry consequently belongs toS=S\_\{=\}and has its optimalgg\-value\. Low\-hhselects a statev∈Bmv\\in B\_\{m\}\. For any selectedv∈Bjv\\in B\_\{j\}with a perfect heuristic value, the descent property gives a successorw∈Bj−1w\\in B\_\{j\-1\}, or a goal forj=1j=1\. Ifwwwere already inCLOSED\\mathrm\{CLOSED\}, following the same optimal continuation to its first unexpanded state would exhibit either an eligible goal or anOPEN\\mathrm\{OPEN\}state atf=C∗f=C^\{\*\}withh<jh<j\. Both contradict selection of a minimum\-hhnon\-goal with valuejj\. Thus expandingvvmakeswweligible with its optimalgg\. Consistency prevents a generated successor from havingh<j−1h<j\-1; previously eligible states haveh≥jh\\geq j\. Low\-hhtherefore selects heuristic valuesm,m−1,…,1m,m\-1,\\ldots,1and then the generated goal, for exactlymmexpansions\.

For the lower bound, take the parent\-pointer path of the optimal goal selected by any continuation fromHH\. Its first statewwunexpanded atHHis inOPEN\\mathrm\{OPEN\}with its optimalgg\. It lies inS=S\_\{=\}because all ofS<S\_\{<\}has been expanded and it is on an optimal solution path\. Henceh⁡\(w\)≥mh\(w\)\\geq m\. Every subsequent non\-goal on this parent\-pointer path must be expanded afterHH: parents are expanded before their children, equal\-cost duplicates do not change parents, and no state is reopened\. The unit\-cost suffix fromwwrequires at leasth∗​\(w\)≥h⁡\(w\)≥mh^\{\*\}\(w\)\\geq h\(w\)\\geq msuch expansions\. ∎

The theorem compares the number of expansions remaining from a fixed search configuration, and is about the optimality of a search suffix; total expansion counts also depend on the work performed before that configuration is reached\.

### 4\.2Low\-hhminimizes total expansions at plateau entry

Different tie\-breakers may reach the final plateau with different histories and insertion orders, but they have expanded the same compulsory setS<S\_\{<\}and expose the same relevant plateau states\. Therefore, low\-hh’s optimal continuation also minimizes the total expansion count, provided that plateau entry satisfies the local accuracy condition of Theorem[2](https://arxiv.org/html/2609.23293#Thmtheorem2)\.

LetH0H\_\{0\}be the first selection point with minimumf=C∗f=C^\{\*\}\. Every run has then expanded preciselyS<S\_\{<\}, although not necessarily in the same order\. Thus every run reachesH0H\_\{0\}after the same number\|S<\|\|S\_\{<\}\|of expansions\.

If an optimal goal is present, every run stops\. Otherwise the set of minimum\-ffstates is independent of the preceding tie\-breaking choices\. Indeed, it is

R=\(\{s\}∩S=\)∪\{v∈S=:∃u∈S<,\(u,v\)∈A,g∗\(u\)\+1=g∗\(v\)\}\.\\begin\{split\}R=\{\}&\(\\\{s\\\}\\cap S\_\{=\}\)\\\\ &\\cup\\\{v\\in S\_\{=\}:\\exists u\\in S\_\{<\},\(u,v\)\\in A,\\ g^\{\*\}\(u\)\+1=g^\{\*\}\(v\)\\\}\.\\end\{split\}
All transitions fromS<S\_\{<\}have been processed, and these are exactly the final\-plateau states generated with their optimalggbefore any final\-plateau expansion\. Therefore

m0=minv∈R⁡h⁡\(v\)m\_\{0\}=\\min\_\{v\\in R\}h\(v\)
is also independent of the preceding expansion order\. Insertion timestamps need not be the same\.

###### Corollary 1\(Global low\-hhoptimality at plateau entry\)\.

Suppose thatH0H\_\{0\}has no goal inOPENmin\\mathrm\{OPEN\}\_\{\\min\},m0≤km\_\{0\}\\leq k, andhhis perfect onB≤kB\_\{\\leq k\}\. For every final tie\-breakerσ\\sigmaand every random outcome,

minτ⁡Xτ=X\[h,σ\]=\|S<\|\+m0=\|S<\|\+ℓ∗​\(I\)\.\\min\_\{\\tau\}X\_\{\\tau\}=X\_\{\[h,\\sigma\]\}=\|S\_\{<\}\|\+m\_\{0\}=\|S\_\{<\}\|\+\\ell^\{\*\}\(I\)\.
Thus every low\-hhstrategy minimizes the total expansion count\.

###### Proof\.

Every run reaches plateau entry after exactly\|S<\|\|S\_\{<\}\|expansions, and every low\-hhrun then has the same valuem0m\_\{0\}\. Theorem[2](https://arxiv.org/html/2609.23293#Thmtheorem2)gives both the lower bound on the number of remaining expansions and its attainment by every low\-hhcontinuation\. Proposition[1](https://arxiv.org/html/2609.23293#Thmproposition1)identifiesm0=ℓ∗​\(I\)m\_\{0\}=\\ell^\{\*\}\(I\)\. ∎

### 4\.3High\-hhmaximizes total expansions

The next result needs perfect values only onB1B\_\{1\}, and characterizes the complete expanded set up to the identity of one goal predecessor\.

###### Theorem 3\(Exact high\-hhexpansion count\)\.

Suppose thathhis perfect onB1B\_\{1\}\. On a nonpathological instance, every strategy expands exactlyS<S\_\{<\}\. On a pathological instance, for every final tie\-breakerσ\\sigmaand every random outcome, there existsp∈B1p\\in B\_\{1\}such that

E\[−h,σ\]=S<∪\(S=∖B1\)∪\{p\}\.E\_\{\[\-h,\\sigma\]\}=S\_\{<\}\\cup\(S\_\{=\}\\setminus B\_\{1\}\)\\cup\\\{p\\\}\.\(1\)Consequently,

X\[−h,σ\]=\{\|S<\|,if the instance is nonpathological,\|S<\|\+\|S=∖B1\|\+1,otherwise\.X\_\{\[\-h,\\sigma\]\}=\\begin\{cases\}\|S\_\{<\}\|,&\\text\{if the instance is nonpathological\},\\\\ \|S\_\{<\}\|\+\|S\_\{=\}\\setminus B\_\{1\}\|\+1,&\\text\{otherwise\}\.\\end\{cases\}\(2\)Every high\-hhstrategy maximizes the total expansion count among all tie\-breakers\. For every strategyτ\\tau,

Eτ∖B1⊆E\[−h,σ\],\|Eτ∩B1\|=\|E\[−h,σ\]∩B1\|∈\{0,1\}\.E\_\{\\tau\}\\setminus B\_\{1\}\\subseteq E\_\{\[\-h,\\sigma\]\},\\qquad\|E\_\{\\tau\}\\cap B\_\{1\}\|=\|E\_\{\[\-h,\\sigma\]\}\\cap B\_\{1\}\|\\in\\\{0,1\\\}\.

###### Proof\.

The nonpathological case follows from Proposition[1](https://arxiv.org/html/2609.23293#Thmproposition1)\. Suppose the instance is pathological\. No optimal goal is generated fromS<S\_\{<\}, since an optimal solution path ending with a predecessor inS<S\_\{<\}would be nonpathological by consistency\. Any final\-plateau predecessor of an optimal goal hash≤1h\\leq 1by consistency and thereforeh=1h=1by positivity and integrality\. Every terminating run must thus expand a state inB1B\_\{1\}\. Conversely, the first expansion inB1B\_\{1\}generates an optimal goal becausehhis perfect there, and goal preference terminates search\. Every strategy expands exactly one member ofB1B\_\{1\}\.

Now consider anyv∈S=∖B1v\\in S\_\{=\}\\setminus B\_\{1\}, whether or not another strategy expands it\. Along a shortest path fromsstovv,f∗f^\{\*\}is nondecreasing and never exceedsC∗C^\{\*\}\. The path cannot pass through a goal beforevv, since unit costs andh⁡\(v\)\>0h\(v\)\>0would then implyf∗​\(v\)\>C∗f^\{\*\}\(v\)\>C^\{\*\}\. The path’s final segment inS=S\_\{=\}hashhdecreasing by one at every edge, with all its values at leasth⁡\(v\)≥2h\(v\)\\geq 2\. The first state of this segment isssor is generated with optimalggfromS<S\_\{<\}\. Before selecting any state inB1B\_\{1\}, high\-hhmust expand this state and, inductively, every following state throughvv: otherwise the first unexpanded state of the segment would remain eligible withh≥2h\\geq 2\. It cannot terminate before its firstB1B\_\{1\}expansion\. Hence it expands everyv∈S=∖B1v\\in S\_\{=\}\\setminus B\_\{1\}\.

Lemma[1](https://arxiv.org/html/2609.23293#Thmlemma1)excludes all other non\-goals except the single selected member ofB1B\_\{1\}, proving \([1](https://arxiv.org/html/2609.23293#S4.E1)\) and \([2](https://arxiv.org/html/2609.23293#S4.E2)\)\. Every competing run expands all ofS<S\_\{<\}, some subset ofS=∖B1S\_\{=\}\\setminus B\_\{1\}, and one member ofB1B\_\{1\}in the pathological case\. This gives count maximality and the asserted inclusions\. WhenB1B\_\{1\}has at most one member, its identity cannot differ between runs\. ∎

Thus the final FIFO, LIFO, or RANDOM criterion can affect*which*member ofB1B\_\{1\}high\-hhexpands, but not*how many*states it expands under these assumptions\.

Combining the global low\-hhresult with Theorem[3](https://arxiv.org/html/2609.23293#Thmtheorem3)gives the two ends of the expansion range\.

###### Corollary 2\(Global minimum and maximum expansion counts\)\.

Suppose thatH0H\_\{0\}has no goal inOPENmin\\mathrm\{OPEN\}\_\{\\min\},m0≤km\_\{0\}\\leq k, andhhis perfect onB≤kB\_\{\\leq k\}\. For arbitrary final tie\-breakersσ\\sigmaandσ′\\sigma^\{\\prime\}, every run satisfies

minτ⁡Xτ\\displaystyle\\min\_\{\\tau\}X\_\{\\tau\}=X\[h,σ\]=\|S<\|\+m0=\|S<\|\+ℓ∗​\(I\),\\displaystyle=X\_\{\[h,\\sigma\]\}=\|S\_\{<\}\|\+m\_\{0\}=\|S\_\{<\}\|\+\\ell^\{\*\}\(I\),\(3\)X\[h,σ\]\\displaystyle X\_\{\[h,\\sigma\]\}≤Xτ≤X\[−h,σ′\],\\displaystyle\\leq X\_\{\\tau\}\\leq X\_\{\[\-h,\\sigma^\{\\prime\}\]\},\(4\)maxτ⁡Xτ\\displaystyle\\max\_\{\\tau\}X\_\{\\tau\}=X\[−h,σ′\]=\|S<\|\+\|S=∖B1\|\+1\.\\displaystyle=X\_\{\[\-h,\\sigma^\{\\prime\}\]\}=\|S\_\{<\}\|\+\|S\_\{=\}\\setminus B\_\{1\}\|\+1\.\(5\)The extrema include all outcomes of randomized strategies\. The low\-hh/high\-hhgap is unbounded even for each fixedk≥1k\\geq 1\.

###### Proof\.

The minimum is Corollary[1](https://arxiv.org/html/2609.23293#Thmcorollary1)\. Sincek≥1k\\geq 1, the assumption thathhis perfect onB≤kB\_\{\\leq k\}implies thathhis also perfect onB1B\_\{1\}, so Theorem[3](https://arxiv.org/html/2609.23293#Thmtheorem3)gives the maximum\. The middle inequality follows from these two extrema\.

For an unbounded gap, letk≥1k\\geq 1and introduceNNstatesu1,…,uNu\_\{1\},\\ldots,u\_\{N\}with unit\-cost edges

s→x,s→ui,x→p,ui→p,p→G\.s\\to x,\\quad s\\to u\_\{i\},\\quad x\\to p,\\quad u\_\{i\}\\to p,\\quad p\\to G\.
Seth⁡\(s\)=h⁡\(x\)=h⁡\(p\)=1h\(s\)=h\(x\)=h\(p\)=1,h⁡\(ui\)=2h\(u\_\{i\}\)=2, andh⁡\(G\)=0h\(G\)=0\. The heuristic is consistent and positive at non\-goals, andC∗=3C^\{\*\}=3\. HereS<=\{s,x\}S\_\{<\}=\\\{s,x\\\},S==\{p,u1,…,uN\}S\_\{=\}=\\\{p,u\_\{1\},\\ldots,u\_\{N\}\\\}, andB1=\{p\}B\_\{1\}=\\\{p\\\}\. All final\-plateau values are perfect, so the hypothesis holds for the fixedkk, andm0=1≤km\_\{0\}=1\\leq k\. Every low\-hhstrategy expandsppimmediately afters,xs,x, whereas every high\-hhstrategy expands alluiu\_\{i\}beforepp\. Their counts are33andN\+3N\+3\. ∎

#### Scope of the guarantees\.

The high\-hhguarantee can fail without exact heuristic values onB1B\_\{1\}, as the unit\-cost version of the star construction shows, or when final\-plateau non\-goals withh=0h=0are allowed\. The unit\-cost assumption is also substantive: even withh=h∗h=h^\{\*\}, minimizing remaining cost need not minimize remaining expansions when edge costs vary\. For example, consider two paths fromssto a unique goal, each costing2​M2M, whereM≥2M\\geq 2\. One begins with an edge of costMMfollowed byMMunit\-cost edges; the other has two edges of costs11and2​M−12M\-1\. After expandingss, low\-hhfollows the first path and requiresMMfurther expansions, whereas high\-hhselects the goal predecessor on the second path and requires only one\.

### 4\.4Locally perfect heuristics on grids

The preceding results are stated in terms of heuristic values on the low\-hhlayers of the final plateau\. Four\-neighbor grid pathfinding with Manhattan\-distance heuristic provides a familiar setting in which these conditions have a simple geometric interpretation\. In particular, the assumption required for the high\-hhresult—thathhis perfect onB1B\_\{1\}—holds automatically for Manhattan distance\. The stronger conditions needed for the low\-hhresults depend on the local obstacle structure near the goal\.

With a single goalG=\(xG,yG\)G=\(x\_\{G\},y\_\{G\}\)and unit\-cost orthogonal moves, use

h⁡\(x,y\)=\|x−xG\|\+\|y−yG\|\.h\(x,y\)=\|x\-x\_\{G\}\|\+\|y\-y\_\{G\}\|\.Every move changes Manhattan distance by one, sohhis consistent; every path to the goal requires at leasthhmoves, so it is admissible\. Every traversable state withh=1h=1is adjacent to the goal\. In particular,hhis perfect onB1B\_\{1\}, irrespective of obstacles farther away\.

Every such instance is pathological: the last non\-goal on each optimal path hash=h∗=1h=h^\{\*\}=1\. Theorem[3](https://arxiv.org/html/2609.23293#Thmtheorem3)therefore implies that high\-hhexpands every non\-goal state withf∗≤C∗f^\{\*\}\\leq C^\{\*\}except all but one of the final\-plateau goal neighbors\. If the goal has at most one traversable neighbor, the high\-hhexpanded set contains that of every tie\-breaker\.

More generally, a final\-plateau cell withh≤kh\\leq khas a perfect value whenever it has a traversable monotone path to the goal\. An obstacle\-free Manhattan ball of radiuskkis a sufficient, but not necessary, condition for the heuristic being perfect onB≤kB\_\{\\leq k\}\. Figure[3](https://arxiv.org/html/2609.23293#S4.F3)illustrates the difference between perfect accuracy ath=1h=1and at larger values\. From any common configuration satisfyingm⁡\(H\)≤km\(H\)\\leq k, Theorem[2](https://arxiv.org/html/2609.23293#Thmtheorem2)gives minimum*remaining*expansions\. When this condition holds atH0H\_\{0\}, the guarantee yields global expansion optimality\.

vvGG\(a\) Perfect forh≤3h\\leq 3everyh≤3h\\leq 3cell has a monotone pathvvGG■\\blacksquare\(b\) Perfect ath=1h=1, not ath=2h=2h⁡\(v\)=2h\(v\)=2buth∗​\(v\)=4h^\{\*\}\(v\)=4Figure 3:Perfect Manhattan\-distance values near the goal\. In panel \(a\), every state in the shaded radius\-33neighborhood has a path that decreaseshhby one at each step\. In panel \(b\), an obstacle forces a detour fromvv: the heuristic is perfect ath=1h=1, but not ath=2h=2\.

## 5Heuristic Scaling and Tie\-Breaking Sensitivity

The preceding results concern ordinary A∗, withf=g\+hf=g\+h\. We now connect heuristic scaling and weighted A∗with the nonpathology criterion of[Dechter and Pearl \(1985\)](https://arxiv.org/html/2609.23293#bib.bib7)to identify a sharp boundary in tie\-breaking sensitivity\. With a consistent heuristic that is positive at non\-goals, underweighting the heuristic makes the expanded set independent of tie\-breaking, whereas at unit weight the expansion gaps can be arbitrarily large\.

Consider weighted A∗using the evaluation function

fα=g\+α​h,0≤α≤1,f\_\{\\alpha\}=g\+\\alpha h,\\qquad 0\\leq\\alpha\\leq 1,and retain the search conventions of Section[2](https://arxiv.org/html/2609.23293#S2), withfαf\_\{\\alpha\}as the primary key\. In particular, a goal is selected whenever one is tied for minimumfαf\_\{\\alpha\}, and selecting a goal is not counted as an expansion\. LetEα,τ​\(I,ρ\)E\_\{\\alpha,\\tau\}\(I;\\rho\)denote the non\-goal expanded set, and define

S<\(α\)=\{v∉𝒢:g∗​\(v\)\+α​h​\(v\)<C∗\}\.S\_\{<\}^\{\(\\alpha\)\}=\\\{v\\notin\\mathcal\{G\}:g^\{\*\}\(v\)\+\\alpha h\(v\)<C^\{\*\}\\\}\.The endpointsα=0\\alpha=0andα=1\\alpha=1are uniform\-cost search\([Dijkstra, 1959](https://arxiv.org/html/2609.23293#bib.bib8)\)and ordinary A∗, respectively\.

### 5\.1Independence below unit weight

###### Corollary 3\(Expanded\-set independence under reduced heuristic weight\)\.

Suppose that the original heuristichhis consistent, zero at goals, and strictly positive at every non\-goal\. For every fixed0≤α<10\\leq\\alpha<1, every tie\-breakerτ\\tau, and every random outcomeρ\\rho,

Eα,τ​\(I,ρ\)=S<\(α\)\.E\_\{\\alpha,\\tau\}\(I;\\rho\)=S\_\{<\}^\{\(\\alpha\)\}\.\(6\)Thus both the expanded set and the expansion count are independent of tie\-breaking\.

###### Proof\.

Writeq=α​hq=\\alpha h\. Consistency ofhhand nonnegative edge costs give

q⁡\(u\)≤α​c​\(u,v\)\+q⁡\(v\)≤c⁡\(u,v\)\+q⁡\(v\)\(\(u,v\)∈A\),q\(u\)\\leq\\alpha c\(u,v\)\+q\(v\)\\leq c\(u,v\)\+q\(v\)\\qquad\(\(u,v\)\\in A\),soqqis consistent and zero at goals\. At every non\-goal on an optimal solution path, positivity and admissibility give

q⁡\(v\)=α​h​\(v\)<h⁡\(v\)≤h∗​\(v\)\.q\(v\)=\\alpha h\(v\)<h\(v\)\\leq h^\{\*\}\(v\)\.The instance is therefore nonpathological with respect toqq, and Proposition[1](https://arxiv.org/html/2609.23293#Thmproposition1)yields \([6](https://arxiv.org/html/2609.23293#S5.E6)\)\. ∎

The star construction of Lemma[2](https://arxiv.org/html/2609.23293#Thmlemma2)shows that the boundary atα=1\\alpha=1is sharp in the worst case\. Every non\-goal in that construction satisfies

g∗​\(v\)\+α​h​\(v\)=C−\(1−α\)​h​\(v\)<C=C∗\(0≤α<1\),g^\{\*\}\(v\)\+\\alpha h\(v\)=C\-\(1\-\\alpha\)h\(v\)<C=C^\{\*\}\\qquad\(0\\leq\\alpha<1\),so every strategy expands allM\+2M\+2non\-goals below unit weight\. On the separating instances of Theorem[1](https://arxiv.org/html/2609.23293#Thmtheorem1), the compared deterministic strategies have counts22andM\+2M\+2atα=1\\alpha=1\. Thus an arbitrarily small reduction in weight can eliminate an arbitrarily large tie\-breaking gap\. Tie\-breaking independence at each fixedα<1\\alpha<1does not imply that the common expanded set is independent ofα\\alpha; it may shrink asα\\alphaincreases\.

### 5\.2Expanded\-set comparison

The independence result also gives a comparison with ordinary A∗and uniform\-cost search\.

###### Corollary 4\(Expanded\-set inclusion under reduced heuristic weight\)\.

Under the assumptions of Corollary[3](https://arxiv.org/html/2609.23293#Thmcorollary3), writeEαE\_\{\\alpha\}for the common expanded set at weight0≤α<10\\leq\\alpha<1\. For every ordinary A∗tie\-breakerτ\\tau, every random outcomeρ\\rho, and every0≤α<10\\leq\\alpha<1,

E1,τ​\(I,ρ\)⊆S≤⊆Eα⊆E0=\{v∉𝒢:g∗​\(v\)<C∗\}\.E\_\{1,\\tau\}\(I;\\rho\)\\subseteq S\_\{\\leq\}\\subseteq E\_\{\\alpha\}\\subseteq E\_\{0\}=\\\{v\\notin\\mathcal\{G\}:g^\{\*\}\(v\)<C^\{\*\}\\\}\.\(7\)Moreover,

0≤α<β<1⟹Eβ⊆Eα\.0\\leq\\alpha<\\beta<1\\quad\\Longrightarrow\\quad E\_\{\\beta\}\\subseteq E\_\{\\alpha\}\.\(8\)

###### Proof\.

Lemma[1](https://arxiv.org/html/2609.23293#Thmlemma1)givesE1,τ​\(I,ρ\)⊆S≤E\_\{1,\\tau\}\(I;\\rho\)\\subseteq S\_\{\\leq\}\. For everyv∈S≤v\\in S\_\{\\leq\}, positivity implies

g∗​\(v\)\+α​h​\(v\)=g∗​\(v\)\+h⁡\(v\)−\(1−α\)​h​\(v\)<C∗,g^\{\*\}\(v\)\+\\alpha h\(v\)=g^\{\*\}\(v\)\+h\(v\)\-\(1\-\\alpha\)h\(v\)<C^\{\*\},sov∈Eαv\\in E\_\{\\alpha\}by Corollary[3](https://arxiv.org/html/2609.23293#Thmcorollary3)\. For0≤α<β<10\\leq\\alpha<\\beta<1, positivity also gives

g∗​\(v\)\+β​h​\(v\)<C∗⟹g∗​\(v\)\+α​h​\(v\)<C∗\.g^\{\*\}\(v\)\+\\beta h\(v\)<C^\{\*\}\\quad\\Longrightarrow\\quad g^\{\*\}\(v\)\+\\alpha h\(v\)<C^\{\*\}\.This proves \([8](https://arxiv.org/html/2609.23293#S5.E8)\), and henceEα⊆E0E\_\{\\alpha\}\\subseteq E\_\{0\}; the formula forE0E\_\{0\}follows by settingα=0\\alpha=0in \([6](https://arxiv.org/html/2609.23293#S5.E6)\)\. ∎

Reducing the weight makes every non\-goal in the ordinary final layer compulsory\. It therefore removes tie\-breaking sensitivity without saving expansions relative to ordinary A∗, but can retain savings over uniform\-cost search\.

#### Example\.

Figure[4](https://arxiv.org/html/2609.23293#S5.F4)illustrates both effects on a six\-state tree\. The only goal isGG, andb1,b2,xb\_\{1\},b\_\{2\},xare dead ends\. The heuristic is consistent, zero atGG, and positive at every non\-goal\. The optimal path iss,p,Gs,p,G, withC∗=3C^\{\*\}=3; fix the successor order atssto bep,b1,b2,xp,b\_\{1\},b\_\{2\},x\.

ssh=3h=3pph=1h=1b1b\_\{1\}h=1h=1b2b\_\{2\}h=2h=2xxh=4h=4GGh=0h=02222112211C∗=3C^\{\*\}=3Successor order atss:p,b1,b2,xp,b\_\{1\},b\_\{2\},x

Figure 4:Heuristic savings without tie\-breaking sensitivity below unit weight, and distinct expansion counts at unit weight\. Edge labels are costs; state labels givehh; shaded leaves are dead ends\. All rows use goal preference, and selectingGGis not counted as an expansion\.After expandingss, the priorities are

fα​\(p\)=fα​\(b1\)=2\+α,fα​\(b2\)=1\+2​α,fα​\(x\)=2\+4​α\.f\_\{\\alpha\}\(p\)=f\_\{\\alpha\}\(b\_\{1\}\)=2\+\\alpha,\\qquad f\_\{\\alpha\}\(b\_\{2\}\)=1\+2\\alpha,\\qquad f\_\{\\alpha\}\(x\)=2\+4\\alpha\.Forα<1\\alpha<1, the first three states must be expanded, whereasxxis expanded exactly whenα<1/4\\alpha<1/4\. Atα=1/4\\alpha=1/4, goal preference excludesxx\. Importantly,ppandb1b\_\{1\}remain tied: atα=1/2\\alpha=1/2, selectingppfirst generatesGGwithfα=3f\_\{\\alpha\}=3, butb1b\_\{1\}must still be expanded becausefα​\(b1\)=5/2<3f\_\{\\alpha\}\(b\_\{1\}\)=5/2<3\. Expanded\-set independence does not require the absence of ties\.

Atα=1\\alpha=1, the statesp,b1,b2p,b\_\{1\},b\_\{2\}instead all havef=3f=3, whereasf⁡\(x\)=6f\(x\)=6\. FIFO selectspp; high\-hhfollowed by FIFO selectsb2,pb\_\{2\},p; and LIFO selectsb2,b1,pb\_\{2\},b\_\{1\},p\. The goal is selected immediately afterpp, giving the three counts in Figure[4](https://arxiv.org/html/2609.23293#S5.F4)\.

## 6Related Work

#### Plateau search\.

[Benton et al\. \(2010\)](https://arxiv.org/html/2609.23293#bib.bib5)identifygg\-value plateaus as a difficulty for temporal planning when search steps do not increase the objective value\. Plateaus also arise in satisficing search under different evaluation functions\.[Wilt and Ruml \(2014\)](https://arxiv.org/html/2609.23293#bib.bib19)study heuristic plateaus and local minima in greedy best\-first search, while[Asai and Fukunaga \(2017a\)](https://arxiv.org/html/2609.23293#bib.bib2)study exploration among and within equal\-hhplateaus\. Thesehh\-plateaus are distinct from the finalf=C∗f=C^\{\*\}plateaus considered here\.

[Asai and Fukunaga \(2016\)](https://arxiv.org/html/2609.23293#bib.bib1)analyze A∗tie\-breaking, emphasizing the large plateaus induced by zero\-cost actions, and develop plateau\-depth strategies\.[Asai and Fukunaga \(2017b\)](https://arxiv.org/html/2609.23293#bib.bib3)further interpret A∗as a sequence of satisficing searches within equal\-ffplateaus and introduce additional distance\-to\-go guidance within those plateaus\. Our results complement this work with unbounded pairwise separations under consistent heuristics and strictly positive costs, including a separation between low\-hhFIFO and LIFO on unit\-cost Manhattan grids\.

#### Optimal expansion versus fixed\-policy comparisons\.

[Corrêa et al\. \(2018\)](https://arxiv.org/html/2609.23293#bib.bib6)show that common A∗tie\-breakers need not achieve optimal expansion\. For consistenthh, their optimal\-expansion rule orders states by\[g\+h,g\+hϵ∗\]\[g\+h,g\+h^\{\*\}\_\{\\epsilon\}\], wherehϵ∗h^\{\*\}\_\{\\epsilon\}is the exact remaining cost after adding a sufficiently small positive constantϵ\\epsilonto each transition cost\. They also evaluate practical cost\-adaptation variants\. Our pairwise result addresses a different question: whether one of the nine specified standard strategies uniformly requires no more expansions than another\. Our unit\-cost results additionally identify local conditions under which entire low\-hhor high\-hhclasses attain extremal expansion counts without computing an additional heuristic\.

#### Tie\-breaking in greedy best\-first search\.

[Heusner et al\. \(2017\)](https://arxiv.org/html/2609.23293#bib.bib11)introduce high\-water mark benches to characterize search behavior in greedy best\-first search, including states that cannot be expanded under any tie\-breaker and conditions for compulsory expansion\.[Heusner et al\. \(2018\)](https://arxiv.org/html/2609.23293#bib.bib12)study best\- and worst\-case expansion counts over tie\-breaking choices for a fixed state space and heuristic, and compare FIFO, LIFO, and random tie\-breaking\. These analyses share our emphasis on expanded sets and tie\-dependent expansion counts, but concern greedy best\-first search rather than cost\-optimal A∗on its finalff\-layer\.

#### Heuristic accuracy\.

[Helmert and Röger \(2008\)](https://arxiv.org/html/2609.23293#bib.bib10)show that A∗can require exponentially many expansions in planning domains even with heuristics whose error is bounded by a small additive constant\. Their lower bounds count states strictly below the finalff\-layer, so favorable final\-plateau tie\-breaking cannot eliminate this effort\. In contrast, our conditions require exact heuristics values on specified final\-plateau layers\. In unit\-cost search, exact remaining cost is also shortest remaining path length\. This supports the optimal low\-hhcontinuation in Theorem[2](https://arxiv.org/html/2609.23293#Thmtheorem2), but does not bound the effort needed to reach the common configuration\. Theorem[3](https://arxiv.org/html/2609.23293#Thmtheorem3)requires that the heuristic be perfect only onB1B\_\{1\}and characterizes maximum total expansion counts instead\.

#### Heuristic weighting\.

[Pohl \(1970\)](https://arxiv.org/html/2609.23293#bib.bib16)studies the relationship between search effort, heuristic accuracy, and heuristic weighting\. Our result in Section[5](https://arxiv.org/html/2609.23293#S5)is an application of the nonpathology criterion of[Dechter and Pearl \(1985\)](https://arxiv.org/html/2609.23293#bib.bib7), restated in Proposition[1](https://arxiv.org/html/2609.23293#Thmproposition1)\. Under the stated consistency, positivity, and goal\-preference assumptions, every fixed weight0≤α<10\\leq\\alpha<1makes the expanded set independent of tie\-breaking, whereas unbounded pairwise gaps are possible atα=1\\alpha=1\. This independence is obtained by making ordinary final\-layer states compulsory, not by reducing expansions relative to ordinary A∗\.

#### Expansion\-order differences beyond tie\-breaking\.

This paper studies differences in expansion order caused by explicit tie\-breaking among nodes with equalff\-value\. Similar ordering differences can also arise from other aspects of best\-first search\.[Suzuki and Fukunaga \(2026\)](https://arxiv.org/html/2609.23293#bib.bib18)compares eager and lazy duplicate detection in A∗and give examples in which duplicate handling changes the order of expansions and produces large differences in expansion count\([Suzuki and Fukunaga, 2026](https://arxiv.org/html/2609.23293#bib.bib18)\)\. Likewise, in parallel best\-first search with a sharedOPEN\\mathrm\{OPEN\}, concurrent execution can produce an expansion order different from that of the corresponding sequential search\([Kuroiwa and Fukunaga, 2020](https://arxiv.org/html/2609.23293#bib.bib14);[Shimoda and Fukunaga, 2025](https://arxiv.org/html/2609.23293#bib.bib17)\)\. These mechanisms are not tie\-breakers in our model, but they illustrate the broader point that changes in expansion order can have large effects on search effort, and in both settings, the divergence constructions are structurally similar to those in Figures[1](https://arxiv.org/html/2609.23293#S3.F1)and[2](https://arxiv.org/html/2609.23293#S3.F2)\.

## 7Discussion and Conclusions

This paper investigated expansion counts under standard tie\-breaking rules for A∗\. We showed that on positive\-cost final\-plateau trees, none of these nine standard tie\-breaking rules dominate the others in general, with unbounded additive gaps in deterministic or expected expansions\. The grid example shows that unbounded additive gaps and expansion\-count ratios between\[h,FIFO\]\[h,\\mathrm\{FIFO\}\]and\[h,LIFO\]\[h,\\mathrm\{LIFO\}\]also arise on the familiar four\-neighbor unit\-cost grids with Manhattan distance, with instances favoring each strategy\.

On the other hand, in unit\-cost search withh\>0h\>0at non\-goals, assuming accuracy on the low\-hhpart of the final plateau can yield extremal strategies\. Exact heuristic values onB≤kB\_\{\\leq k\}make every low\-hhstrategy \(regardless of final tie\-breaker\) optimal for the remaining search from a common configuration whose minimum eligiblehh\-value is at mostkk\. When this condition holds at plateau entry, the same guarantee yields global expansion optimality\. Exact heuristic values onB1B\_\{1\}make every high\-hhstrategy expansion\-maximal, independently of the final tie\-breaker\.

Finally, we showed that reducing the heuristic weight below one eliminates tie\-breaking sensitivity under the stated assumptions, by makes all ordinary final\-layer states compulsory\.

These results contribute to a theoretical understanding of A∗search on the final plateau\. One direction for future work is to identify additional structural conditions that imply bounded or unbounded expansion gaps between tie\-breaking strategies\. Another is to identify broader conditions under which particular classes of tie\-breakers attain minimum or maximum expansion counts\. Finally, while we considered heuristic weights below one, it would be useful to study tie\-breaking among states with equal weighted evaluation values in weighted A∗with heuristic weight greater than one\.

## References

- Asai and Fukunaga \(2016\)M\. Asai and A\. Fukunaga\.Tiebreaking strategies for A\* search: how to explore the final frontier\.In*Proceedings of AAAI*, pages 673–679, 2016\.
- Asai and Fukunaga \(2017a\)M\. Asai and A\. Fukunaga\.Exploration among and within plateaus in greedy best\-first search\.In*Proceedings of ICAPS*, pages 11–19, 2017a\.doi:10\.1609/icaps\.v27i1\.13800\.
- Asai and Fukunaga \(2017b\)M\. Asai and A\. Fukunaga\.Tie\-breaking strategies for cost\-optimal best first search\.*Journal of Artificial Intelligence Research*, 58:67–121, 2017b\.
- Barley et al\. \(2025\)M\. Barley, N\. de Kriek, S\. Franco, A\. Garcia\-Olaya, T\. Hartill, C\. Triggs, H\. Zwart, V\. Alcázar, and P\. Riddle\.A problem with the current methodology for comparing search algorithms and a proposed solution\.In*Proceedings of SoCS*, pages 29–37, 2025\.doi:10\.1609/socs\.v18i1\.35973\.
- Benton et al\. \(2010\)J\. Benton, K\. Talamadupula, P\. Eyerich, R\. Mattmüller, and S\. Kambhampati\.GG\-value plateaus: A challenge for planning\.In*Proceedings of ICAPS*, pages 259–262, 2010\.doi:10\.1609/icaps\.v20i1\.13396\.
- Corrêa et al\. \(2018\)A\. B\. Corrêa, A\. G\. Pereira, and M\. Ritt\.Analyzing tie\-breaking strategies for the A\* algorithm\.In*Proceedings of IJCAI*, pages 4715–4721, 2018\.doi:10\.24963/ijcai\.2018/655\.
- Dechter and Pearl \(1985\)R\. Dechter and J\. Pearl\.Generalized best\-first search strategies and the optimality of A\*\.*Journal of the ACM*, 32\(3\):505–536, 1985\.doi:10\.1145/3828\.3830\.
- Dijkstra \(1959\)E\. W\. Dijkstra\.A note on two problems in connexion with graphs\.*Numerische Mathematik*, 1:269–271, 1959\.doi:10\.1007/BF01386390\.
- Hart et al\. \(1968\)P\. E\. Hart, N\. J\. Nilsson, and B\. Raphael\.A formal basis for the heuristic determination of minimum cost paths\.*IEEE Transactions on Systems Science and Cybernetics*, 4\(2\):100–107, 1968\.
- Helmert and Röger \(2008\)M\. Helmert and G\. Röger\.How good is almost perfect?In*Proceedings of the Twenty\-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13\-17, 2008*, pages 944–949, 2008\.
- Heusner et al\. \(2017\)M\. Heusner, T\. Keller, and M\. Helmert\.Understanding the search behaviour of greedy best\-first search\.In*Proceedings of SoCS*, pages 47–55, 2017\.
- Heusner et al\. \(2018\)M\. Heusner, T\. Keller, and M\. Helmert\.Best\-case and worst\-case behavior of greedy best\-first search\.In*Proceedings of IJCAI*, pages 1463–1470, 2018\.doi:10\.24963/ijcai\.2018/203\.
- Holte \(2010\)R\. C\. Holte\.Common misconceptions concerning heuristic search\.In*Proceedings of the Third Annual Symposium on Combinatorial Search \(SoCS 2010\)*, pages 46–51, 2010\.doi:10\.1609/socs\.v1i1\.18160\.
- Kuroiwa and Fukunaga \(2020\)R\. Kuroiwa and A\. Fukunaga\.Analyzing and avoiding pathological behavior in parallel best\-first search\.In*Proceedings of ICAPS*, pages 175–183, 2020\.
- Likhachev and Koenig \(2005\)M\. Likhachev and S\. Koenig\.A generalized framework for lifelong planning A\* search\.In*Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling \(ICAPS\)*, pages 99–108, 2005\.
- Pohl \(1970\)I\. Pohl\.Heuristic search viewed as path finding in a graph\.*Artificial Intelligence*, 1:193–204, 1970\.
- Shimoda and Fukunaga \(2025\)T\. Shimoda and A\. Fukunaga\.Parallel greedy best\-first search with a bound on expansions relative to sequential search\.In*Proceedings of AAAI*, pages 26668–26677, 2025\.doi:10\.1609/aaai\.v39i25\.34869\.
- Suzuki and Fukunaga \(2026\)Y\. Suzuki and A\. Fukunaga\.Eager vs\. Lazy Duplicate Detection in A\*, 2026\.Proceedings of ICAPS Workshop on Heuristics and Search for Domain\-Independent Planning \(HSDIP\)\.
- Wilt and Ruml \(2014\)C\. M\. Wilt and W\. Ruml\.Speedy versus greedy search\.In*Proceedings of the Seventh Annual Symposium on Combinatorial Search, SOCS 2014, Prague, Czech Republic, 15\-17 August 2014*, pages 184–192, 2014\.