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

WHY does A* exist?

WHAT are the pieces?

HOW does A* relate to Dijkstra and Greedy? (the 80/20 core)

DERIVATION 1 — Why admissibility ⇒ optimal path

Step 1. Let $C^*$ be the true optimal cost. Suppose A* is about to pop a goal node $G_2$ whose path cost is $g(G_2) > C^*$ (a suboptimal goal). We show this is impossible. Why this step? If we prove A* can never pop a worse goal first, the first popped goal must be optimal.

Step 2. Because the true optimal path exists, somewhere on the open list (frontier) there is a node $n$ lying on an optimal path. Why? Any path from start to goal that hasn't been fully expanded has at least one "boundary" node sitting on the frontier.

Step 3. For that $n$: $f(n)=g(n)+h(n)\le g(n)+h^*(n)=C^*.$ Why this step? $h(n)\le h^*(n)$ is admissibility, and since $n$ is on an optimal path, $g(n)+h^*(n)$ equals the optimal total cost $C^*$.

Step 4. But $G_2$ is a goal so $h(G_2)=0$, hence $f(G_2)=g(G_2)>C^*$. Combining: $f(n)\le C^* < f(G_2)$.

Step 5. A* pops the smallest $f$ first, so $n$ would be popped before $G_2$. Contradiction. ∎ Why this matters: the very first goal A* removes from the queue is guaranteed optimal — admissibility is exactly the condition that buys this guarantee.

DERIVATION 2 — Why consistency ⇒ admissibility (and never re-expand)

Step A: consistent ⇒ admissible. Take any path $n=v_0\to v_1\to\dots\to v_k=\text{goal}$. Apply consistency along it: $h(v_i)\le c(v_i,v_{i+1})+h(v_{i+1}).$ Sum from $i=0$ to $k-1$ (telescoping the $h$ terms), with $h(v_k)=0$: $h(n)\le \sum_{i=0}^{k-1} c(v_i,v_{i+1}) = \text{cost of that path}.$ Why this step? It holds for every path, in particular the cheapest one, so $h(n)\le h^*(n)$. Done — consistency is stronger than admissibility.

Step B: $f$ is non-decreasing along expansions. For an edge $u\to v$: $f(v)=g(v)+h(v)=g(u)+c(u,v)+h(v)\ge g(u)+h(u)=f(u),$ using consistency $c(u,v)+h(v)\ge h(u)$. Why this matters: $f$ never decreases as we go deeper. So when a node is popped its $g$ is already final → A never needs to re-open a closed node*. With a merely-admissible (but inconsistent) heuristic you may have to re-expand, which is slower.

Worked Example 1 — grid with Manhattan distance

Grid, 4-directional moves cost 1 each. Heuristic $h=$ Manhattan distance $=|x_1-x_2|+|y_1-y_2|$.

• Why admissible? Each move changes Manhattan distance by at most 1 and costs 1, so the straight count never overestimates the true number of moves.
• Why consistent? For neighbours $c(u,v)=1$ and $|h(u)-h(v)|\le 1=c(u,v)$, so $h(u)\le c(u,v)+h(v)$. ✔

Start $(0,0)$, goal $(2,2)$:

• $h(0,0)=4$, $f=0+4=4$.
• Moving to $(1,0)$: $g=1$, $h=3$, $f=4$. Same $f$ — A* keeps moving goalward, never expanding $(-1,0)$ whose $f=2+5=7$. Why this step? The away-from-goal node has higher $f$, so A* simply ignores it — that's the speedup over Dijkstra.

Worked Example 2 — inadmissible heuristic breaks optimality

Nodes $S\to A\to G$: $c(S,A)=1,\,c(A,G)=1$ (total 2). Also $S\to G$ direct $=2.5$. Set a bad $h(A)=5$ (overestimate; true is 1).

• $f(\text{via }A \text{ at }A)=1+5=6$. $f(G\text{ direct, on open})=2.5+0=2.5$.
• A* pops the direct $G$ first → returns cost $2.5$, missing the true optimum 2. Why this matters: overestimating made the good path look expensive. Steel-man fix: clamp/lower $h$ so $h\le h^*$.

Worked Example 3 — Euclidean heuristic for a drone (GNC)

Continuous space, moves along grid but the true robot can fly diagonally; cost = Euclidean length. Use $h=$ straight-line (Euclidean) distance.

• Straight line is the shortest possible path ⇒ $h\le h^*$ ⇒ admissible.
• It also satisfies the triangle inequality ⇒ consistent. Why GNC cares: admissible Euclidean $h$ guarantees the planner returns the genuinely shortest flyable route, while exploring a narrow cone toward the target — crucial when compute is limited on-board.

Flashcards

Connections

• Dijkstra's Algorithm — A* with $h=0$.
• Greedy Best-First Search — A* with $g$ dropped.
• Heuristic Functions — Manhattan, Euclidean, Chebyshev.
• Priority Queue / Min-Heap — data structure ordering by $f$.
• Triangle Inequality — the geometric root of consistency.
• Weighted A* and Bounded Suboptimality
• GNC Path Planning — rovers, drones, spacecraft.
• Bellman Optimality — relation $g(v)=g(u)+c(u,v)$.

Concept Map

Hinglish (regional understanding)