Informed Search · Projects · Amittai Siavava

Informed search uses a heuristic estimate of the cost remaining to the goal to decide which state to expand next, reaching the goal after touching far fewer states than blind search. This project drives a robot across a grid maze of obstacles to a target cell, comparing A* search against greedy best-first search.

Each frontier state $n$ is scored by

f (n) = g (n) + h (n),

where $g (n)$ is the cost already paid to reach $n$ and $h (n)$ estimates the cost from $n$ to the goal. A-star always expands the state of lowest $f$ . Greedy search drops the $g$ term and expands by $h$ alone — quicker to commit, but with no account of the path so far it can settle for an expensive route.

A* scores each frontier node by f = g + h, the cost paid plus the estimate remaining, and expands the smallest. Edge labels are step costs; the accent route S-A-C-G is the optimal path the search returns.

On a grid the estimate is a distance to the goal cell. For four-connected movement, Manhattan distance

h (n) = ∣ x_{n} - x_{g} ∣ + ∣ y_{n} - y_{g} ∣

counts axis-aligned steps; when diagonal moves are allowed, Euclidean distance $(x_{n} - x_{g})^{2} + (y_{n} - y_{g})^{2}$ fits the true geometry. Both are admissible — never overestimating the real remaining cost — which is exactly the condition under which A-star returns an optimal path.

Two properties of a heuristic control what A* guarantees:

Admissible. $h (n) \leq h^{*} (n)$ at every node, where $h^{*} (n)$ is the true remaining cost. The estimate never overshoots.
Consistent. $h (n) \leq cost (n, m) + h (m)$ across every edge $(n, m)$ — a triangle inequality on the estimate. Consistency implies admissibility, and it makes $f$ nondecreasing along any path, so A* settles each node's optimal $g$ the first time it expands it and never reopens one.

Admissibility is enough for optimality, and the argument is short. Let $C^{*}$ be the optimal cost and suppose a suboptimal goal $G_{2}$ with $g (G_{2}) > C^{*}$ sits on the frontier. Some node $n$ on an optimal path is on the frontier too, and there

f (n) = g (n) + h (n) \leq g (n) + h^{*} (n) = C^{*} < g (G_{2}) = f (G_{2}) .

A* expands the smaller $f$ first, so it reaches $n$ — and eventually the true goal — before it would ever remove $G_{2}$ . Overestimating breaks this: an $h$ larger than $h^{*}$ can inflate a good node's $f$ past a bad goal's and let the bad goal out first.

Among admissible heuristics, larger is better. If $h_{2} (n) \geq h_{1} (n)$ everywhere, $h_{2}$ dominates $h_{1}$ , and A* with $h_{2}$ expands no more nodes than with $h_{1}$ : every node A* can safely skip under $h_{1}$ it also skips under $h_{2}$ . The pointwise maximum of two admissible heuristics is itself admissible and dominates both, which is why heuristics are often combined by taking their max.

Algorithm:

\textsc{A-Star}(start, goal)

— least-cost-first search on

f = g + h

1
input: a start cell, a goal cell, a heuristic $h$
2
frontier $\gets$ priority queue holding $start$ with key $h(start)$
3
$g[start] \gets 0$
4
while frontier is not empty do
5
$n \gets$ remove the state of least key from frontier
6
if $n = goal$ then return the path traced back to $start$
7
for each neighbor $m$ of $n$ do
8
$c \gets g[n] + \operatorname{cost}(n, m)$
9
if $m$ is unseen or $c < g[m]$ then
10
$g[m] \gets c$ ; set $m$ 's parent to $n$
11
insert $m$ into frontier with key $c + h(m)$
12
return failure

Greedy search often expands fewer states, since it heads straight at the goal, but it gives up optimality: a heuristic that points toward a dead end walks the robot into it. A-star pays for more expansions with a guarantee — under an admissible heuristic the first goal it removes from the frontier sits on a shortest path. Setting $h = 0$ collapses A-star to uniform-cost search, and a sharper $h$ narrows the search toward the goal without breaking that guarantee.

A-star and greedy best-first, live on a random grid maze. Cells light up as the search visits them (green) and holds them on the frontier (yellow); the found route is traced in orange. A-star expands by g + h and always returns a shortest path; greedy chases h alone — watch it touch fewer cells but sometimes hand back a longer route. The note keeps score against the true shortest path.

A-star search

frontiervisitedpathwall

References

Project repository
Reference notes: Informed Search and A*
Reference notes: Heuristic Functions and Memory-Bounded Search

╌╌ END ╌╌