Does surely expanded mean part of the best route?

No. A low estimate can force exploration of a branch that does not supply the returned solution.

Is a node with f=C* always expanded?

No. Its treatment can depend on ties and when the goal is selected.

Can the solver normally identify the complete set beforehand?

Not directly from this definition, because the optimal solution cost C* is usually not yet known.

AI Glossary / Graphs and symbolic AI / Intermediate

Surely expanded nodes

Definition

Surely expanded nodes are search nodes that standard A* must expand before it can terminate with an optimal solution under the relevant search assumptions. In the usual consistent-heuristic analysis, they lie below the optimal-cost boundary: f(n)=g(n)+h(n) is strictly less than C*, the cost of an optimal solution. Nodes with f(n)=C* are on the boundary and may depend on tie-breaking.

What it means

A* ranks candidate nodes by an estimated total solution cost. The value g is the cost already incurred along the node's path, while h estimates the remaining cost. Their sum f determines the priority.

“Surely” is a mathematical classification, not a confidence percentage or an instruction to mark a node as certain in advance. C* is generally unknown while solving the problem. The classification often explains search effort after the optimal cost is known or within a theoretical analysis. It does not mean every such node belongs to an optimal solution path.

How it works

Consider ordinary A* on a finite search space with nonnegative action costs, a consistent admissible heuristic, and a goal test when a node is selected from the frontier. Assume standard correct handling of repeated states. Consistency makes f-values nondecreasing along paths, and admissibility prevents overestimating the remaining optimal cost.

Before A* selects an optimal goal of cost C*, every eligible frontier node with f<C* has higher priority than that goal. Reachable nodes below this boundary cannot be hidden behind ancestors with larger f under consistency, so the relevant nodes in this region are expanded first.

Nodes with f=C* may be selected before or after the goal according to the tie policy. Nodes with f>C* need not be expanded before ordinary A* stops optimally. Weighted A*, inconsistent heuristics, pruning, memory limits, and alternative termination rules require separate analysis rather than an automatic transfer of this description.

Three practical examples

Search teaching: separate the part of an A* trace forced by its cost ordering from the part affected by ties.
Heuristic comparison: examine how a more informative admissible heuristic moves nodes toward or beyond the optimal-cost contour, potentially reducing mandatory search work.
Planner benchmarking: report expansion counts with the heuristic, duplicate handling, and tie-breaking policy so apparently different results can be interpreted correctly.

Think of it this way

Think of a queue ordered by a lower-bound price estimate. Every item estimated below the final accepted price must be considered first under that queue rule; items exactly at the price can depend on the tie policy. The analogy is limited because search generates new nodes as it proceeds, and the guarantee relies on heuristic and graph assumptions.

Worked example

Use an original finite search graph. Start S has edges to A of cost 2, to B of cost 3, and to C of cost 4. Each of A, B, and C leads directly to goal G, with costs 6, 5, and 5 respectively. There are no other edges. The three complete route costs are 8, 8, and 9, so C*=8.

Choose h(S)=5, h(A)=3, h(B)=5, h(C)=5, and h(G)=0. These values are admissible. They are also consistent: for example, h(S)=5≤2+3 and h(A)=3≤6+0, with the other edge checks satisfied similarly.

After expanding S, A has f=2+3=5, B has f=3+5=8, and C has f=4+5=9. A must be expanded before any goal of cost 8. Expanding A generates G with g=8 and f=8.

The frontier now includes B and G tied at 8, plus C at 9. If the tie rule selects G, A* terminates without expanding B. If it selects B first, B is expanded before the same optimal goal is accepted. Thus B is on the boundary, not surely expanded under all tie policies. C is not expanded before termination in either trace.

S and A are the strictly-below-boundary nodes in this example. The result distinguishes generating B from expanding it: B was generated as soon as S was expanded, even in the trace where B never produces successors.

Illustrative case study

Fictional case: a planning team compares two implementations of the same A* demonstration and sees different expansion totals. Both return a route with the same optimal cost. The team discovers that most of the difference occurs among nodes tied at that cost.

It records tie-breaking and separates counts below, on, and above the final cost contour. Different totals alone do not establish incorrectness. This fictional case illustrates diagnostic reporting, not measured production performance or proof that all implementation differences are harmless.

Common misconceptions and mistakes

Do not replace the strict inequality f<C* with f≤C*: boundary nodes need separate treatment. A generated node is not necessarily expanded. A surely expanded node need not lie on the returned route, because optimistic estimates can lead A* into unproductive branches.

More informative heuristics can reduce expansions while costing more to compute, so fewer expansions do not automatically mean less elapsed time. Also distinguish nodes representing paths from states representing configurations; repeated-state handling affects how theoretical node counts map to implementation statistics.

Business use

The concept helps explain where an optimal planner spends unavoidable work under a particular heuristic and search policy. Use it when analyzing planner changes, especially when a new heuristic appears to save memory or expansions.

Document the assumptions before making performance claims. If the planner uses weighted estimates or stops when a goal is first generated, the ordinary A* contour argument may not apply. Measure total runtime, heuristic evaluation cost, memory, and solution quality together rather than turning one theoretical category into a complete business performance measure.

Check your understanding

C*=12 and a reachable eligible node has g=4 and h=7 under the stated consistent A* assumptions. Which region is it in?

Answer: f=11<12, so it is in the surely expanded region, not the tie boundary.

Related terms

Admissible heuristic
Evaluation function
Frontier
A* search
consistent heuristic
node expansion
tie-breaking
optimal solution cost

Learn next

Trace the worked graph twice using opposite tie policies. Then increase h(A) from 3 to its exact remaining cost of 6 and observe how A moves to the boundary. Keep heuristic consistency and the goal-selection rule explicit throughout the comparison.

Sources

Domshlak, Karpas, and Markovitch, Learning to Combine Admissible Heuristics Under Bounded Time, surely expanded sets and tie boundaries: https://karpase.net.technion.ac.il/files/2017/02/icaps2009ws.pdf The graph and fictional case are original. Scope: the standard consistent A* analysis stated above; the cited paper also identifies its own more restrictive modelling assumptions.

Previous: SUPS Next: Surrogate data testing