A - algorithm — heuristic, admissibility, consistency — important for GNC: Question bank

Throughout this page GNC means Guidance, Navigation & Control — the on-board planning stack of rovers, drones and spacecraft that must compute shortest routes quickly with limited compute.

Reminder of the pieces so nothing here is used before it is anchored:

start and goal are the two special nodes: where the search begins and where it must end. Later on this page we use the short symbols $S$ for start and $G$ for goal.
$g (n)$ = ==cost of the best known path from start to $n$ == (what you have already paid).
$h (n)$ = ==heuristic estimate of the remaining cost from $n$ to the goal== (your peek-guess).
$h^{*} (n)$ = the true cheapest remaining cost from $n$ to the goal (the thing $h$ is estimating).
$c (u, v)$ = ==the cost of the edge that goes from node $u$ to node $v$ . We assume, as everywhere in A*, that every edge cost is non-negative==, $c (u, v) \geq 0$ — you can never "gain" cost by moving.
$f (n) = g (n) + h (n)$ = estimated total trip cost through $n$ ; A* always expands the smallest- $f$ open node.
$C^{*}$ = the optimal (cheapest) total cost of getting from start to goal.
Admissible: $0 \leq h (n) \leq h^{*} (n)$ , never overestimates the true remaining cost.
Consistent: $h (u) \leq c (u, v) + h (v)$ for every edge, and $h (goal) = 0$ .

The picture below is the mental model behind almost every item on this page: the magenta arrow is $g$ (already paid), the violet dashed arrow is the peek-guess $h$ , and their sum is $f$ . Several answers below say "the good path looks expensive" or " $f$ never dips" — read those against this figure.

Figure — A - algorithm — heuristic, admissibility, consistency — important for GNC

True or false — justify

True or false: If

h

is admissible, the first goal A* pops off the queue is guaranteed optimal.

True. Some frontier node

n

sits on an optimal path, so

f (n) = g (n) + h (n) \leq g (n) + h^{*} (n) = C^{*}

(look at the figure:

g

plus the honest remaining cost is exactly the whole trip). Any suboptimal goal

G_{2}

(a second, worse goal node reached with

g (G_{2}) > C^{*}

) has

h (G_{2}) = 0

since it is a goal, so

f (G_{2}) = g (G_{2}) > C^{*} \geq f (n)

; A* pops the smaller-

f

node

n

first, so

G_{2}

can never be returned before an optimal goal.

True or false: Consistency implies admissibility.

True, and it is a one-way arrow. Along any path

n = v_{0} \to \dots \to v_{k} = goal

, sum

h (v_{i}) \leq c (v_{i}, v_{i + 1}) + h (v_{i + 1})

; the

h

terms telescope and the boundary value

h (v_{k}) = h (goal) = 0

drops out, leaving

h (n) \leq

path cost, hence

h (n) \leq h^{*} (n)

True or false: Admissibility implies consistency.

False. Admissibility only bounds each

h

against the total remaining cost; it does not forbid

f

from dipping between neighbours, so an admissible-but-inconsistent

h

can exist and may force re-expansions.

True or false: With a consistent heuristic, A* never needs to re-open a node already closed.

True. Consistency makes

f

non-decreasing along expansions (

f (v) \geq f (u)

), so a node's

g

is final the moment it is popped — no cheaper path can arrive later.

True or false: A* with

h (n) = 0

everywhere is a broken or useless algorithm.

False.

h = 0

is both admissible and consistent, so A* is still correct — it simply reduces to Dijkstra's Algorithm because

f = g

(in the figure the violet peek-arrow collapses to nothing).

True or false: Greedy best-first search (

f = h

) always returns the shortest path if

h

is admissible.

False. Greedy ignores

g

entirely, so it can commit to a route that looks close but is expensive; admissibility of

h

does not rescue it — see Greedy Best-First Search.

True or false: A larger admissible heuristic (closer to

h^{*}

) never expands more nodes than a smaller one.

True, and here is the WHY. If

h_{2} (n) \geq h_{1} (n)

everywhere (both admissible), then every node with

f_{2} = g + h_{2} > C^{*}

also had

f_{1} \leq f_{2}

, so the set A* expands (nodes with

f \leq C^{*}

) under

h_{2}

is a subset of the set under

h_{1}

— a bigger honest push toward the goal can only rule nodes out, never in.

True or false: Multiplying an admissible

h

by a weight

w > 1

keeps A* optimal but faster.

False. Weighted A* (

f = g + w \cdot h

) is generally inadmissible; it trades optimality for speed and only guarantees cost

\leq w \cdot C^{*}

— see Weighted A* and Bounded Suboptimality.

True or false: If every edge cost is the same constant, A* and Dijkstra always expand the same nodes.

False. Even with uniform edges, a non-trivial admissible

h

lets A* skip nodes pointing away from the goal; only

h = 0

makes them identical.

True or false: The consistency condition

h (u) \leq c (u, v) + h (v)

is just the Triangle Inequality applied to the heuristic.

True. Reading

h

as an estimated distance-to-goal, going

u \to v

then estimating from

v

can never be shorter than estimating straight from

u

Spot the error

"I set

h (A) = 5

when the true remaining cost is

1

to focus the search harder — this is fine because bigger heuristics are always better."

Error:

h = 5 > h^{*} = 1

overestimates, breaking admissibility. Concretely, with start

S

and goal

G

from the reminder box,

S \to A \to G

costs

1 + 1 = 2

but a direct edge

S \to G

costs

2.5

; the inflated

h (A)

makes the good path look expensive (

f = 1 + 5 = 6

) so A* pops the direct goal (

f = 2.5

) and returns

2.5

, missing the true optimum

2

"Consistency guarantees optimality, and admissibility guarantees no re-expansion."

Backwards. Admissibility guarantees optimality; consistency is the stronger property that additionally guarantees no closed node is re-opened.

"My heuristic satisfies

h (goal) = 0

and

h (u) \leq c (u, v) + h (v)

on every edge, but I still worry it might overestimate somewhere."

No worry needed. Those two conditions are consistency, and consistency provably implies admissibility, so

h

never overestimates.

"To prove A* optimal I only need to check the goal's heuristic is zero."

Insufficient. The optimality proof needs

h (n) \leq h^{*} (n)

for all nodes;

h (goal) = 0

is one required piece but does not by itself bound the other nodes.

"Since

f

is the estimated total cost, A* should expand the node with the largest

f

first to make fastest progress."

Error: A* expands the smallest

f

. Smallest

f

is the most promising cheapest-total candidate; largest

f

would be the least promising node.

"A negative heuristic like

h = - 3

is still admissible because it never overestimates."

Error: admissibility requires

0 \leq h (n)

. A negative

h

violates the lower bound and can distort

f

, and it is pointless since true remaining cost is never negative.

"Dijkstra is a special case of Greedy best-first search."

Error: Dijkstra is A* with

h = 0

, i.e.

f = g

. Greedy uses

f = h

and discards

g

; they sit at opposite ends, with A* in between.

Why questions

Why does using only

h

(greedy) lose optimality while

g + h

keeps it?

Ignoring

g

throws away the cost already paid (the magenta arrow in the figure), so A* can be lured into a route that starts cheap-looking but accumulates expensive edges; adding

g

balances "what I've paid" against "what I still owe".

Why does admissibility, and not consistency, appear in the optimality proof?

The optimality argument only needs one frontier node

n

on an optimal path to satisfy

f (n) \leq C^{*}

, which follows directly from

h (n) \leq h^{*} (n)

— that is precisely admissibility.

Why does consistency make

f

non-decreasing as we expand deeper?

For edge

u \to v

f (v) = g (u) + c (u, v) + h (v) \geq g (u) + h (u) = f (u)

because

c (u, v) + h (v) \geq h (u)

; the heuristic's smoothness cancels the growth in

g

f

can only stay level or rise.

Why is straight-line (Euclidean) distance a safe heuristic for a drone that can fly diagonally?

A straight line is the shortest possible path between two points, so it can never exceed the true flyable cost (

h \leq h^{*}

) — admissible — and it obeys the triangle inequality — consistent. See GNC Path Planning.

Why does GNC (Guidance, Navigation & Control) prefer A* over plain Dijkstra for on-board planning?

On-board compute is limited; an admissible

h

funnels the search into a narrow cone toward the goal, exploring far fewer nodes while still returning the genuinely shortest route.

Why is a Priority Queue / Min-Heap the natural data structure for A*?

A* must repeatedly extract the minimum- $f$ open node; a min-heap gives that extraction and the insertion of updated

f

values in logarithmic time, which is what makes the search efficient.

Why is Manhattan distance admissible on a 4-directional unit-cost grid?

Each move costs

1

and changes the coordinate sum by at most

1

, so the coordinate-difference count

∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣

can never exceed the true number of moves needed.

Edge cases

What does A* return if the goal is unreachable?

The open list empties without ever popping a goal, so A* reports failure — the heuristic cannot manufacture a path that does not exist.

What happens when two nodes have equal

f

A* may expand either first (tie-break is implementation-defined); correctness is unaffected, though a tie-break favouring larger

g

often expands fewer nodes.

h (n) = h^{*} (n)

(a perfect heuristic) admissible, and what does A* do with it?

Yes, equality satisfies

h \leq h^{*}

and is consistent. A* then walks straight down an optimal path expanding essentially only nodes on it — the ideal, though usually uncomputable.

What is

h (goal)

required to be, and why?

It must be

0

. There is no remaining cost at the goal, and the consistency/telescoping and optimality arguments both rely on this anchoring value being exactly zero.

If all edge costs are zero, is any

h \geq 0

still admissible?

Only

h = 0

is admissible, because

h^{*} (n) = 0

everywhere, so any positive

h

would overestimate — a degenerate but instructive boundary.

Does a graph with a zero-cost edge

c (u, v) = 0

still allow consistency?

Yes, consistency then demands

h (u) \leq h (v)

across that edge; it is a valid constraint, not a contradiction, as long as the heuristic does not drop across the free edge.

What does the consistency inequality reduce to on an edge where

h (u) = h (v)

It becomes

0 \leq c (u, v)

, i.e. it just requires the edge cost to be non-negative — trivially true (our standing assumption), showing consistency is automatic when the heuristic is flat.