A* search: guide the search with a lower bound

A route with fewer moves can cost more. On the map below, six moves through costly cells cost 11; an eight-move detour costs 8.

A* search uses a lower bound on the remaining cost to guide its next choice. You will calculate that priority, watch the search unfold, and see what fails when the estimate grows too large.

Define the map and its costs

The example has seven columns and five rows. Coordinates run from x = 0 to 6 and y = 0 to 4, with y increasing down the diagram. The start is (0, 2), and the goal is (6, 2).

Each open cell is a graph node. An edge allows one move up, down, left, or right into another open cell. Diagonal moves are absent.

Moving into a cell pays its entry cost. The start costs zero before any move. Cells (1, 2) through (5, 2) cost 2 to enter; all other cells cost 1.

These costs are abstract units. They could represent a chosen travel penalty, but this example gives them no time or distance unit. The goal is the smallest sum of edge costs.

Add cost so far to an estimate

For each discovered node n, keep three values:

• g(n): the cheapest cost found so far from the start to n.
• h(n): an estimate of the remaining cost from n to the goal.
• f(n): the priority used to choose the next node.

The frontier holds discovered nodes waiting for the search to examine their outgoing edges. A* removes the frontier node with the smallest f. This combines a known partial route with a prediction about its continuation, as Hart, Nilsson, and Raphael developed in the original A* paper.

The value g can improve while the search runs. A heuristic does not change the actual edge costs; it changes which candidate receives attention first. Setting h = 0 gives the cost-only priority used by Dijkstra's algorithm.

Build a Manhattan lower bound

The Manhattan distance counts the horizontal and vertical moves still needed if obstacles disappear:

Every legal move changes one coordinate by one. Reaching the goal therefore requires at least d(n) moves. Since each move costs at least 1, d(n) also bounds the remaining cost from below.

Walls can force extra moves. Costly cells can add penalties. Neither can reduce the minimum cost below this bound; LaValle uses the same obstacle-free argument to construct a grid heuristic.

An admissible heuristic never exceeds the true minimum remaining cost, h*(n). Here we use nonnegative estimates and h(goal) = 0:

If the cheapest legal move cost c_min, the corresponding bound would be c_min d(n). Changing the move rules requires checking the bound again. Allowing a diagonal step of cost 1, for example, would make ordinary Manhattan distance overestimate some routes.

Follow the search loop

Start with g(start) = 0 and all other costs unknown. Put the start in the frontier, then repeat:

1. Remove the frontier node u with the smallest g(u) + h(u).
2. If u is the goal, return its route by following stored parent pointers.
3. For each legal neighbor v, compute the candidate cost g(u) + cost(u, v).
4. If that candidate improves g(v), update its cost and parent. Add v to the frontier, reopening it if it left the queue earlier.

If the frontier becomes empty, no route connects these endpoints in this finite graph. Discovering the goal does not finish the search. The algorithm waits until the goal itself leaves the priority queue.

With an admissible heuristic, positive edge costs, and reopening on improvement, this procedure returns a minimum-cost route on a finite graph. Before an expensive goal route could win the queue, a frontier node on a cheaper route would have a smaller f. The original paper gives the admissibility argument.

To make the animation repeatable, this implementation breaks equal-f ties using lower h, then the node's row order from top left. Equal-cost alternatives can still exist. A different tie rule can change the chosen route and the work count.

Check the estimate across each edge

A consistent heuristic also satisfies this local condition for every legal edge u → v:

For the Manhattan estimate, neighboring distances differ by exactly one. Each edge costs at least one, so the inequality holds. Together with h(goal) = 0, consistency also gives admissibility by adding these inequalities along a route.

Consistency keeps f from decreasing along an extended route. Once a node leaves the queue, its g is final, and later routes cannot require reopening it. MIT's informed-search lecture explains this condition and its connection to search priorities.

Admissibility alone allows estimates that violate this local condition. Such estimates can require revisiting an expanded node. The code keeps that reopening rule even though zero and Manhattan need no reopening on these maps.

Follow the first decisions

At the start, g = 0, h = 6, and f = 6. Removing the start discovers these three candidates:

Candidate	g	h	f
(0, 1)	1	7	8
(1, 2)	2	5	7
(0, 3)	1	7	8

The search first chooses (1, 2). Its estimate suggests a promising shortcut even though entering it costs 2.

After four queue removals, the next node is (1, 1), with g = 2, h = 6, and f = 8. The initial widget pauses here. Its seven frontier entries show the alternatives still waiting.

Finishing the Manhattan search returns this route:

(0, 2) → (0, 1) → (1, 1) → (2, 1) → (3, 1)
       → (4, 1) → (5, 1) → (6, 1) → (6, 2)

All eight destination cells cost 1, so the total is 8. Going straight across row 2 costs 2 + 2 + 2 + 2 + 2 + 1 = 11. The lower detour also costs 8, but the stated tie rule chooses the upper one.

Compare three search priorities

Heuristic search

Which route looks cheapest?

Rank each frontier node by f = g + h. Here g is the best route cost found so far; h estimates the remaining cost. Each move pays the destination cell's number.

A* map presetCostly shortcutOpen gridWall with a gapDisconnected goalStart equals goal

A* heuristicZero (Dijkstra)Manhattan lower boundAggressive: 2 × Manhattan

A* search step

4 of 11 queue removals

Step A* searchFinish A* search

Only horizontal and vertical moves are legal. Coordinates use x right and row y down. The starting cell is free; every later cell adds its entry cost. Ties use lower h, then row order from top left.

Map and current search

Search status

Searching

Queue removals (count)

4

Expanded nodes (count)

4

Discovered nodes (count)

11

Frontier nodes (count)

7

Next node (x, y)

(1, 1)

Next g

2

Next h

6

Next f

8

Path cost

Pending

Dijkstra reference cost

8

Searching. 4 nodes expanded. Next priority: 8.

Frontier at this step

The first row leaves the queue next. Priorities sort by f, then h, then row order.

Queued nodes and their costs

Node	g	h	f
(1, 1)	2	6	8
(0, 3)	1	7	8
(3, 2)	6	3	9
(1, 3)	3	6	9
(2, 1)	5	5	10
(2, 3)	5	5	10
(0, 0)	2	8	10

Completed searches on this map

These results run all three choices to completion. Expanded counts exclude the final goal removal. They count search work, without measuring runtime.

Heuristic comparison

Heuristic	Cost	Expanded
Zero	8	33
Manhattan	8	10
2 × Manhattan	11	6

Manhattan is a lower bound here because every cardinal move costs at least 1. Multiplying by 2 removes that guarantee. A cheaper route to a previously expanded node reopens it; zero and Manhattan need no reopening on these grids.

Reset A* experiment

Finish the default search, then choose Zero (Dijkstra) and finish again. Both return cost 8. Manhattan expands 10 nodes, while zero expands 33 with these tie rules.

The queue removals count includes the final goal removal. The expanded nodes count excludes it because the search stops before examining the goal's outgoing edges. The completed comparison table uses these same definitions.

Try Wall with a gap and follow the route through the opening. Disconnected goal empties the frontier without a route. Start equals goal returns cost 0 after one removal and no neighbor expansions.

Changing the map or heuristic rewinds to step zero. Move the step slider to revisit earlier decisions. The completed comparison table always shows full searches on the selected map, even while the main diagram shows an intermediate step.

See an overestimate return a worse route

Choose Costly shortcut and Aggressive: 2 × Manhattan. This mode uses h(n) = 2d(n), doubling the goal estimate while leaving the map costs unchanged.

At the start, its estimate is 12 even though the best full route costs 8. Along the costly middle row, its priorities keep favoring progress toward the goal. The goal leaves the queue with route cost 11 after 6 expansions.

The comparison now reads:

Estimate	Returned cost	Expanded nodes
Zero	8	33
Manhattan	8	10
Twice Manhattan	11	6

The aggressive mode performs fewer expansions here and returns a worse route. This example is a weighted A* choice with weight 2; it deliberately loses the lower-bound property. A larger heuristic does not preserve ordinary A*'s minimum-cost guarantee.

Expansion counts describe this map and queue rule. They do not measure runtime: heuristic evaluation, queue operations, and memory access also cost work. A weak heuristic can save little, while an expensive one can consume its search savings.

Connect the graph to robot motion

A* optimizes the graph supplied to it. A robotics graph must define what each node means and which transitions a robot can actually follow.

For a moving body, configuration space accounts for the robot's shape when marking forbidden positions. A graph edge also needs a check along the whole motion; clear endpoints alone leave the space between them unchecked.

The grid's minimum-cost route depends on its cell size, allowed moves, and cost model. It can differ from the shortest continuous path. A car's turning limits or an arm's joint constraints can require a richer state and a different set of edges.

Finer grids also grow quickly as the number of state dimensions rises. Rapidly exploring random trees build a tree from sampled configurations and checked connections. That lesson examines a different way to search continuous free space.

Reproduce the search in Python

This standard-library example uses the same costly shortcut, entry costs, and tie rules. A set stores the frontier, and min selects its next entry. That keeps the example short; large searches usually use a priority queue.

WIDTH, HEIGHT = 7, 5
START, GOAL = 14, 20
costs = [1] * (WIDTH * HEIGHT)
for x in range(1, 6):
    costs[2 * WIDTH + x] = 2


def neighbors(node):
    x, y = node % WIDTH, node // WIDTH
    candidates = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
    return sorted(
        ny * WIDTH + nx
        for nx, ny in candidates
        if 0 <= nx < WIDTH and 0 <= ny < HEIGHT
    )


def search(weight):
    def h(node):
        x, y = node % WIDTH, node // WIDTH
        return weight * (abs(x - 6) + abs(y - 2))

    g = {START: 0}
    parent = {}
    frontier = {START}
    expanded = 0
    while frontier:
        node = min(frontier, key=lambda n: (g[n] + h(n), h(n), n))
        frontier.remove(node)
        if node == GOAL:
            route = [node]
            while route[-1] != START:
                route.append(parent[route[-1]])
            route.reverse()
            return g[node], expanded, route
        expanded += 1
        for neighbor in neighbors(node):
            candidate = g[node] + costs[neighbor]
            if candidate < g.get(neighbor, float("inf")):
                g[neighbor] = candidate
                parent[neighbor] = node
                frontier.add(neighbor)
    return None, expanded, []


for weight in (0, 1, 2):
    cost, expanded, route = search(weight)
    print(f"weight={weight}: cost={cost}, expanded={expanded}, moves={len(route) - 1}")

Expected output:

weight=0: cost=8, expanded=33, moves=8
weight=1: cost=8, expanded=10, moves=8
weight=2: cost=11, expanded=6, moves=6

The code keeps the best g for each node across removals. A later strict improvement adds that node back to the frontier, so it supports reopening. Equal-cost candidates leave the current parent unchanged.

Try it yourself

Exercise 1: calculate the next priority. On the costly shortcut map, suppose (2, 1) has g = 3. Calculate its Manhattan h and f. A second node has g = 4 and h = 4; which wins this implementation's tie rule?

Show the priority calculation

From (2, 1) to (6, 2), h = |2 − 6| + |1 − 2| = 5. Its f is 3 + 5 = 8.

The second node also has f = 4 + 4 = 8. It wins the tie because its h = 4 is smaller. This tie choice changes the search order without changing the graph costs.

Exercise 2: test a changed move rule. Suppose a diagonal from (5, 1) to goal (6, 2) becomes legal and costs 1. Does ordinary Manhattan remain admissible at (5, 1)? Give a cost bound that remains valid for cardinal and diagonal moves costing at least 1.

Show the changed lower bound

Manhattan gives |5 − 6| + |1 − 2| = 2, while the diagonal reaches the goal for cost 1. It therefore overestimates and fails admissibility at that node.

With these moves, use max(|x − x_goal|, |y − y_goal|). Each step changes either coordinate by at most one, so the larger coordinate gap still gives a lower bound on the required moves. For (5, 1), that bound is 1.

Sources and further study

• Hart, Nilsson, and Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the original 1968 treatment of heuristic graph search and admissibility.
• Steven LaValle: A-star in Planning Algorithms, including the cost-to-come plus cost-to-go view and the grid lower-bound example.
• Emilio Frazzoli, MIT: Informed Search, including admissible estimates, consistency, and search on motion-planning graphs.

Next, use collision checking to decide whether a proposed graph edge represents a motion the robot can follow.