I4 · Problem Solving and Reasoning: Classical AI

Informed Search and A*

Informed search uses a heuristic function h(n), an estimate of the cost from a state to the goal, to explore promising states first. A* search expands the state with the lowest f(n) = g(n) + h(n), where g(n) is the cost so far. If the heuristic is admissible, never overestimating the true remaining cost, A* is guaranteed to find an optimal path, usually exploring far fewer states than uninformed search.

15 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

A maps app finds the fastest route across a city of a million road segments in a fraction of a second. It cannot check every road. It uses a sense of direction: roads heading towards your destination are tried first.

Informed search uses a heuristic function h(n), an estimate of the cost from a state to the goal, to explore promising states first. A* search expands the state with the lowest f(n) = g(n) + h(n), where g(n) is the cost so far. If the heuristic is admissible, never overestimating the true remaining cost, A* is guaranteed to find an optimal path, usually exploring far fewer states than uninformed search.

In simple words

To walk to a temple you can see on a hill, you naturally head towards it. That sense of "how far is it from here?" is a heuristic. A* combines how far you have already walked with how far the temple still looks, and always continues from the spot where that total is smallest.

Overview

  • Informed (heuristic) search uses an estimate of the distance to the goal to search more efficiently.
  • A heuristic h(n) estimates the cost from node n to the goal; g(n) is the cost so far.
  • A* expands the node with the lowest f(n) = g(n) + h(n).
  • If h never overestimates (admissible), A* is guaranteed to find an optimal solution.
  • A* was published by Hart, Nilsson and Raphael in 1968 for the Shakey robot.
  • Better heuristics expand fewer nodes; a perfect heuristic would walk straight to the goal.

Why it matters

A* is one of the most used algorithms in AI and computing: route planning, robot navigation, video-game characters, puzzle solving and many planning systems rely on it. Designing good heuristics is a core skill in classical AI.

Key terms

Heuristic h(n)
An estimate of the remaining cost from state n to the goal.
g(n)
The actual cost of the path from the start to n.
f(n) = g(n) + h(n)
The estimated total cost of a path through n.
Admissible heuristic
One that never overestimates the true remaining cost.
Greedy best-first search
Expands the state with the lowest h(n) only; fast but not optimal.
Manhattan distance
The sum of horizontal and vertical distances; a common grid heuristic.

Types

Several informed search algorithms exist, and heuristics themselves come in types. These are the main ones.

1. Greedy best-first search

Expanding the node that looks closest to the goal by h(n) alone.

  • How it works: It ignores the cost already paid, so it is fast but not optimal and can be misled by dead ends.
  • Example: Driving towards whichever junction is closest to the destination as the crow flies, even if the road loops back.
  • When to use it: Use it when a quick, good-enough path matters more than the best path.

2. A* search

Best-first search ordered by f(n) = g(n) + h(n).

  • How it works: It balances the cost so far with the estimated cost remaining; with an admissible and consistent heuristic it is complete and optimal.
  • Example: Map apps and game characters finding shortest paths around obstacles.
  • When to use it: Use it as the standard choice for shortest-path problems where a good heuristic exists.

3. Memory-bounded variants (IDA* and beam search)

Versions of heuristic search that limit memory.

  • How it works: IDA* runs depth-first searches with an increasing f-limit; beam search keeps only the k best nodes at each level, losing optimality.
  • Example: Language models use beam search with k = 4 or 5 to choose likely word sequences.
  • When to use it: Use them when A*'s memory use is too large for the problem.

4. Admissible and consistent heuristics

Admissible heuristics never overestimate the true cost; consistent ones also satisfy h(n) ≤ cost(n, n′) + h(n′).

  • How it works: Straight-line distance is admissible for road travel because no road is shorter than a straight line; consistency makes A* never revisit nodes.
  • Example: For the 8-puzzle, the number of misplaced tiles and the Manhattan distance of tiles are both admissible.
  • When to use it: Use them whenever you need guaranteed optimal paths from A*.

5. Relaxed-problem and learned heuristics

Heuristics built by solving an easier version of the problem, or learned from data.

  • How it works: Removing a rule, such as letting tiles pass over each other, gives an easier problem whose exact cost is an admissible heuristic; pattern databases and neural networks can also estimate costs.
  • Example: Manhattan distance comes from relaxing "tiles may only slide into the blank" to "tiles may move to any neighbour".
  • When to use it: Use relaxation to design heuristics systematically, and learned heuristics for very large domains.

Explained in detail

Why combine g and h?

Uniform-cost search uses only g(n), the cost so far, so it spreads out evenly in all directions, wasting effort on paths heading away from the goal. Greedy best-first search uses only h(n), rushing towards the goal, but it can be lured down a path that looks close but turns out long. A*, published by Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute in 1968 for the Shakey robot project, balances both. A path is promising if it is cheap so far and looks close to the goal. When h is admissible, A* never rejects the optimal path, because its estimated total can never look worse than its true cost.

Good heuristics

ProblemHeuristicWhy it is admissible
Road route between citiesStraight-line distance to the destinationNo road can be shorter than a straight line
Grid moves up, down, left, rightManhattan distanceEach move covers at most one row or column
8-puzzleSum of each tile's Manhattan distance to its targetEach move shifts one tile one square
Any problemh = 0Trivially admissible, but A* becomes uniform-cost search

Among admissible heuristics, larger is better: a heuristic closer to the true cost prunes more states. A common way to invent one is to solve a relaxed version of the problem, ignoring some rule. Ignoring walls gives the Manhattan distance; ignoring that tiles block each other gives the 8-puzzle heuristic.

A* in practice

  • On a grid with obstacles, A* with Manhattan distance typically explores a narrow band towards the goal rather than the whole map.
  • Its weakness is memory: it keeps every frontier state. Variants such as IDA* and weighted A* trade optimality or speed for memory.
  • Large-scale route planners add pre-processing, such as precomputed shortcuts between important junctions, so queries take milliseconds.
  • Video games have used A* for decades to move characters around obstacles.

Tie-breaking matters too: when several states have the same f, preferring the one with the smaller h, the one closer to the goal, avoids exploring many equally promising states and makes A* much faster on open maps, as the example below shows.

How it works

  1. Formulate the problem with step costs.
  2. Design an admissible heuristic, often by relaxing a rule.
  3. Keep a priority queue ordered by f = g + h.
  4. Repeatedly expand the lowest-f state, updating g for cheaper paths found.
  5. Stop when the goal is removed from the queue; its path is optimal.

In code

astar.py
import heapq

grid = [
    "S...............",
    "................",
    "..........#.....",
    "..........#.....",
    "..........#.....",
    "..........#.....",
    "...............G",
]
rows, cols = len(grid), len(grid[0])
find = lambda ch: next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == ch)
start, goal = find("S"), find("G")

def neighbours(r, c):
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
            yield nr, nc

def search(heuristic):
    frontier, g, expanded = [(heuristic(start), heuristic(start), 0, start)], {start: 0}, 0
    while frontier:
        f, h, cost, node = heapq.heappop(frontier)  # ties broken by smaller h
        if cost > g[node]:
            continue
        expanded += 1
        if node == goal:
            return cost, expanded
        for nxt in neighbours(*node):
            if cost + 1 < g.get(nxt, float("inf")):
                g[nxt] = cost + 1
                h_next = heuristic(nxt)
                heapq.heappush(frontier, (cost + 1 + h_next, h_next, cost + 1, nxt))

manhattan = lambda n: abs(n[0] - goal[0]) + abs(n[1] - goal[1])
print("Uniform-cost (h = 0): path length %d, states expanded %d" % search(lambda n: 0))
print("A* (Manhattan):       path length %d, states expanded %d" % search(manhattan))

Output

Uniform-cost (h = 0): path length 21, states expanded 108
A* (Manhattan):       path length 21, states expanded 22

Try it yourself

Heading for the temple

A pilgrim crosses a town of winding lanes towards a hilltop temple.

Admissible or not?

For shortest road distance between cities, is each heuristic admissible?

  • Actual road distance plus 10 km

  • Zero

  • Straight-line distance

  • Twice the straight-line distance

Common mistakes

  • Using an overestimating heuristic and assuming the result is optimal.
  • Using greedy best-first search when the shortest path matters.
  • Forgetting A*'s memory demands on very large problems.

Check yourself

Question 1

1. What does A* minimise when choosing the next state?

Question 2

2. What makes a heuristic admissible?

Question 3

3. Why is Manhattan distance admissible on a four-direction grid?

Summary

  • Informed search uses a heuristic estimate of the remaining cost.
  • A* expands the lowest g + h and is optimal with an admissible heuristic.
  • Good heuristics come from relaxed problems and dramatically reduce the states explored.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: Red Blob Games: Introduction to the A* algorithm · Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition)