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

• Dijkstra's Algorithm pops smallest $g$, i.e. key $=g(n)$. It ignores the goal entirely.
• Greedy Best-First Search pops smallest $h$, i.e. key $=h(n)$. It ignores the road already paid for.
• A* pops smallest $f(n)=g(n)+h(n)$.

What this looks like: Dijkstra grows even, blind ripples; greedy dashes straight at the goal and can overpay; A* balances both.

(a) is admissibility — "$h$ never overestimates the true remaining cost." (b) is consistency (also called monotone) — the Triangle Inequality applied to the heuristic, holding for every edge $u\to v$ with cost $c(u,v)$, plus $h(\text{goal})=0$.

$g(S)=0$ — we have paid nothing to reach the start. $h(G)=0$ — a valid heuristic estimates zero remaining cost at the goal (this is part of the consistency definition and any sensible admissible heuristic satisfies it).

Manhattan distance to goal $(3,1)$:

• At $(0,0)$: $h=|0-3|+|0-1|=4$, $g=0$, so $f=0+4=4$.
• At $(1,0)$ (one step right, cost $1$): $h=|1-3|+|0-1|=3$, $g=1$, so $f=1+3=4$.

The $f$ stays at $4$ — the away-from-goal neighbour $(-1,0)$ would give $g=1,h=5,f=6$, so A* ignores it.

Read the figure: the blue dot is the start (label $g=0,h=4,f=4$); the green arrow to $(1,0)$ keeps $f=4$ because every step toward the goal trades one unit of $g$ for one unit of $h$ — the total is unchanged, so A* happily advances. The red arrow to $(-1,0)$ carries $f=6$: stepping away raises $h$ by $1$ while still paying $1$ of $g$, so its total jumps by $2$. Because A* always pops the smallest $f$, the red node sits at the back of the queue and is expanded only if nothing better remains — that is exactly the pruning that makes A* faster than Dijkstra's Algorithm.

Compute $f=g+h$: $f(P)=5$, $f(Q)=4$, $f(R)=6$. A* pops smallest first → $Q$ (4), then $P$ (5), then $R$ (6). Note $Q$ has $h=0$: it is a goal candidate, and since its $f$ is the smallest here, popping it returns an optimal-looking path — legitimate only if $h$ is admissible.

Manhattan distance itself is admissible ($h\le h^{\ast }$). Halving it makes it even smaller: $h^{\prime }=0.5h\le h\le h^{\ast }$. So yes, admissible — but weaker, so A* will expand more nodes (closer to Dijkstra). Under-estimating is always safe for optimality; it just costs speed.

Expand $S$ ($g=0$). Its successors go on the open list:

• $A$: $g=1$, $h=5$, $f=6$.
• $G$ (direct): $g=2.5$, $h=0$, $f=2.5$.

Smallest $f$ is $G$ at $2.5$, so A* pops the goal and returns cost $2.5$. But the true optimum is $S\to A\to G=2$. A* missed it because the inflated $h(A)=5$ made the good path look expensive ($f=6$).

Diagnosis: $h(A)=5>h^{\ast }(A)=1$ violates admissibility. Fix: clamp $h(A)\le 1$.

Read the figure: the two green arrows $S\to A\to G$ are the genuinely cheap route (total $1+1=2$), but node $A$ is tagged with the inflated $h(A)=5$, so its $f=1+5=6$ — the label deliberately shows the true remaining cost is only $1$. The red arrow is the direct edge $S\to G$ of cost $2.5$; with $h(G)=0$ its $f=2.5$. Since $2.5<6$, A* pops the red goal first and never gets around to expanding $A$. The picture makes the failure visible: an over-optimistic-looking number on the good path pushed it to the back of the queue.

Admissible? True remaining: $h^{\ast }(S)=2,h^{\ast }(A)=1,h^{\ast }(G)=0$. We have $h(S)=2\le 2$, $h(A)=0\le 1$, $h(G)=0\le 0$. ✔ All admissible. Consistent? Check edge $S\to A$ with $c=1$: need $h(S)\le c+h(A)=1+0=1$. But $h(S)=2>1$. ✗ Violated. So this $h$ is admissible yet inconsistent — proving admissibility is the weaker property. Along this edge $f$ actually drops ($f(S)=0+2=2$, $f(A)=1+0=1$), which is the tell-tale sign of inconsistency.

Admissibility check. True remaining costs: $h^{\ast }(S)=2$ (via $S\to B\to A\to G$), $h^{\ast }(B)=2$, $h^{\ast }(A)=1$, $h^{\ast }(G)=0$. Our heuristic $h(S)=0\le 2$, $h(B)=2\le 2$, $h(A)=0\le 1$, $h(G)=0\le 0$. ✔ Admissible. Consistency check. Edge $S\to B$ costs $c=1$: need $h(S)\le c+h(B)=1+2=3$ ✔, but edge $B\to A$ costs $c=1$: need $h(B)\le c+h(A)=1+0=1$, yet $h(B)=2>1$ ✗. Inconsistent — this is the flaw that will cause the re-open.

Trace A*:

1. Pop $S$ ($g=0$). Push successors:
   • $A$ via direct edge: $g=4$, $f=4+0=4$.
   • $B$: $g=1$, $f=1+2=3$.
2. Smallest $f$ is $B$ ($3<4$). Pop $B$, close it with $g(B)=1$. Push its successor $A$ via $B$: $g=1+1=2$, $f=2+0=2$. Now the open list has $A$ with $g=2$ (and the old $A$ with $g=4$ is superseded).
3. Smallest $f$ now is $A$ ($f=2$). Pop $A$, close it with $g(A)=2$. Push $G$: $g=3$, $f=3$.
4. Pop $G$, return cost $3$ — the true optimum $S\to B\to A\to G=1+1+1=3$. ✔

Where would the re-open show up? Swap the pop order that inconsistency permits: because $h(B)=2$ is inflated, $f(B)=3$ is larger than $f(A\text{-direct})=4$? No — here $3<4$, so $B$ is (luckily) popped first. To force the re-open we need $A$ closed via the expensive route before the cheap route is discovered. Give $B$ a genuinely large heuristic $h(B)=4$ (now inadmissible, but the point is the mechanism):

• After popping $S$: $A$-direct has $f=4+0=4$; $B$ has $f=1+4=5$.
• Now $A$-direct ($f=4$) is popped first and closed with the wrong, expensive $g(A)=4$; $G$ gets $g=5$.
• Later $B$ is popped, discovers $A$ via the cheap route with $g=2<4$. Since $A$ is already closed, A* must re-open $A$, update $g(A)=2$, and re-propagate to $G$ ($g=3$).

The clean, admissible-only re-open. Keep $h(B)=2$ (admissible) but make the direct edge look better by lowering it slightly: set $S\stackrel{2}{\to }A$ instead of $4$. Then after $S$: $A$-direct $f=2$, $B$ $f=1+2=3$. Pop $A$-direct first, close with $g(A)=2$. Pop $B$ ($f=3$), discover $A$ via $B$ with $g=1+1=2$ — a tie, no improvement, no re-open here. The reliable lesson is the general principle below; constructing a minimal admissible-only re-open requires the cheap route's $g$ to strictly beat the closed $g$, which needs the closed node's first route to have been mis-ranked by an inconsistent (yet still admissible) $h$ elsewhere on the frontier.

The principle that always holds. With consistency, $f$ never decreases along an expansion, so a node's $g$ is final the moment it is popped — never re-opened. Without consistency (even if still admissible), $f$ can dip, so a node closed via a worse-looking route may later gain a strictly cheaper path and must be re-opened and re-propagated. This is extra work, never a loss of optimality — admissibility still guarantees the shortest path (L5.2), consistency merely removes the re-work.

Let $u,v$ be points and $t$ the goal. Consistency needs $h(u)\le c(u,v)+h(v)$, i.e. $\Vert u-t\Vert \le \Vert u-v\Vert +\Vert v-t\Vert .$ This is exactly the Triangle Inequality for straight-line distances (a straight path from $u$ to $t$ can never be longer than detouring through $v$). It holds for all $u,v,t$. And $h(t)=\Vert t-t\Vert =0$. Both consistency conditions met. ✔ Since consistency ⟹ admissibility, the Euclidean heuristic is also admissible — the guarantee GNC Path Planning relies on.

Let $dx=|x_1-x_2|$, $dy=|y_1-y_2|$. The cheapest route uses as many diagonal steps as possible (each knocks down both $dx$ and $dy$ by $1$), then straight steps for the leftover. The exact minimum on an empty grid is the octile distance: $h=\sqrt{2}\cdot \min (dx,dy)+|dx-dy|.$

• Admissible? With no obstacles this equals $h^{\ast }$, so $h\le h^{\ast }$ always (obstacles only make the true path longer). ✔
• Consistent? It equals a true shortest-path metric on the empty grid, which obeys the triangle inequality, so consistent. ✔
• Why not Manhattan here? Manhattan $=dx+dy$ would overestimate because it forbids the cheaper diagonal — that could break admissibility (it counts $2$ where a diagonal costs only $\sqrt{2}\approx 1.41$). So plain Manhattan is the wrong tool for 8-connected grids.

Numeric check for $(dx,dy)=(3,1)$: $h=\sqrt{2}\cdot 1+|3-1|=1.4142\dots +2=3.4142\dots$

With $w=2$:

• $(0,0)$: $f=0+2\cdot 4=8$.
• $(1,0)$: $f=1+2\cdot 3=7$. The inflated $h$ pulls harder toward the goal, so the goalward node now has a strictly smaller $f$ ($7<8$), sharpening the search. You gain speed (fewer expansions). You lose exact optimality, but you keep a bound: the returned path costs at most $w\times$ the optimum. Here $w=2$ means "never worse than double optimal." This is a deliberate, controlled inadmissibility — not a bug.

With $h=0$, $f=g$, so A* pops smallest $g$ first — it is exactly Dijkstra's Algorithm.

• Admissible? $0\le 0\le h^{\ast }(n)$ always (true cost is never negative, because all edge costs $c\ge 0$). ✔
• Consistent? $h(u)=0\le c(u,v)+0=c(u,v)$ since edge costs are non-negative, and $h(\text{goal})=0$. ✔ So $h=0$ is a perfectly valid heuristic — just totally unguided. A* with $h=0$ is not broken, merely blind.

Let $C^{\ast }$ be the true optimal cost. Suppose, for contradiction, A* is about to pop a goal $G_2$ with $g(G_2)>C^{\ast }$.

1. A frontier node sits on an optimal path. Take any optimal path from start to goal. Not all of it is expanded yet (else the optimal goal would already be popped). So some node $n$ on this optimal path is currently on the open list — call it the boundary node.
2. Bound $f(n)$. Because $n$ lies on an optimal path, its true optimal total is $g(n)+h^{\ast }(n)=C^{\ast }$ (the cost to reach $n$ optimally plus the optimal remainder). Apply admissibility $h(n)\le h^{\ast }(n)$: $f(n)=g(n)+h(n)\le g(n)+h^{\ast }(n)=C^{\ast }.$
3. Bound $f(G_2)$. $G_2$ is a goal, so $h(G_2)=0$, giving $f(G_2)=g(G_2)>C^{\ast }$.
4. Chain the two. Combining steps 2 and 3: $f(n)\le C^{\ast }<f(G_2)$.
5. Contradiction. A* always pops the smallest $f$ first, so the frontier node $n$ (with $f(n)\le C^{\ast }$) would be popped before $G_2$ (with $f(G_2)>C^{\ast }$). Hence A* cannot pop the suboptimal $G_2$ first.

Therefore the first goal A* removes from the queue has cost $\le C^{\ast }$, and since $C^{\ast }$ is optimal it equals $C^{\ast }$: the returned path is optimal. ∎ This mirrors Bellman Optimality: the optimal cost decomposes as cost-so-far plus optimal cost-to-go ($C^{\ast }=g(n)+h^{\ast }(n)$ on an optimal path), and admissibility keeps the estimate on the safe side of that decomposition.

• Admissible? The straight-line distance ignoring the obstacle is $\le$ any real flyable path length (the real path must detour around the zone, so it can only be longer). Thus $h\le h^{\ast }$. ✔ Admissible.
• Consistent? Straight-line distance satisfies the triangle inequality for all points (L4.1), independent of obstacles, and $h(\text{goal})=0$. ✔ Consistent.
• Use it? Yes. It is optimistic (never overestimates), so A* stays optimal, and it still pulls the search toward the goal, exploring a narrow cone — exactly what limited on-board compute in GNC Path Planning wants. Ignoring the obstacle in the heuristic is fine; the obstacle is enforced by the graph's edges (you simply cannot traverse into the zone), not by the heuristic.

Sanity number: if start $=(0,0)$, goal $=(6,0)$, straight-line $h=6$; any obstacle-avoiding path is $\ge 6$, so $h\le h^{\ast }$ holds. (For a zone forcing a detour, say a semicircular arc of radius $3$, the true path is $\ge 3\pi \approx 9.42>6$ — strictly longer, confirming the estimate under-shoots.)