Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 38 ยท Path Planning

A* Path Planning for Robots

Understand A* search: the f = g + h rule, admissible heuristics, tie-breaking and weighted A*, and compare it with Dijkstra in runnable Python.

Dijkstra expands cells in every direction like a spreading puddle. If the goal is to the east, spending effort on the west is wasteful. A* (pronounced "A star") keeps Dijkstra's guarantee of an optimal path but uses a heuristic, an estimate of the remaining distance, to steer the search toward the goal.

It is the workhorse of game pathfinding and robot navigation, and the base for many later planners (D*, Theta*, Hybrid A*). You will implement it, test two heuristics, and measure how much work it saves compared with Dijkstra.

The idea: f = g + h

For each cell A* tracks:

  • g(n): the exact cost from the start to n found so far.
  • h(n): a heuristic, a guess of the cost from n to the goal.
  • f(n) = g(n) + h(n): the estimated total cost of a path through n.

A* always expands the open cell with the smallest f. If h is zero everywhere, A* is exactly Dijkstra. A better h pulls the search toward the goal.

Three numbers per cell

g Cost from the start. Known.
h Guess to the goal. Heuristic.
f = g + h Expand the smallest f first.
1 / 2

Heuristics for grids

The standard choices depend on which moves are allowed (with unit straight steps):

Moves Heuristic Formula
4-connected Manhattan abs(dx) + abs(dy)
8-connected, diagonal costs 1.414 Octile (dx + dy) + (1.414 - 2) * min(dx, dy)
Any direction Euclidean sqrt(dx*dx + dy*dy)

A heuristic is admissible if it never overestimates the true remaining cost. Straight-line distance is admissible because no path can be shorter than a straight line. With an admissible heuristic A* returns an optimal path. If it is also consistent (h(a) <= cost(a, b) + h(b) for every edge) then each cell is expanded at most once, which makes the simple implementation below correct.

Overestimating on purpose, for example h = 2 * euclid, makes A* greedier and faster but loses the optimality guarantee. That is called weighted A*, with a bound: the path costs at most w times the optimum.

Implementing A*

The code is Dijkstra with a different priority. Compare it to the previous lesson: only the heap key changes from g to g + h.

Python A* versus Dijkstra: nodes expanded

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the o marks (cells A* expanded). They form a narrow cone toward the goal compared with the numbers for Dijkstra. The weighted run expands even fewer cells but may return a slightly longer path.

Tie-breaking and the open list

When many cells share the same f, the order matters. Breaking ties in favor of the larger g (or the smaller h) makes A* dive toward the goal and expand fewer cells on open maps. You can do this with a heap key such as (f, h, cell).

The set of cells waiting to be expanded is the open list; cells already expanded form the closed list. In the code above the heap is the open list and closed is the closed set.

Python Heuristics compared on an open map

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Octile is the tightest admissible choice for 8-connected grids, so it expands the fewest cells while staying optimal. Manhattan overestimates when diagonals are allowed, so it expands the fewest cells here, but on maps with obstacles it can return a path that is not the cheapest. Matching the heuristic to the move set is part of designing the planner.

Beyond plain A*

  • Replanning. When the map changes, D* Lite repairs the old search instead of starting over. Mobile robots in unknown spaces use it.
  • Any-angle paths. Theta* checks line of sight so paths are not forced onto grid directions.
  • Cars. Hybrid A* searches over (x, y, heading) with motion primitives so the path respects turning limits.
  • Bidirectional and anytime variants trade memory and quality for speed.

Grid-aligned paths are jagged and ignore the robot's dynamics. Treat the A* output as a coarse route, then smooth it and add timing before sending it to the controller.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In A*, a cell's priority is...

    f is the exact cost so far (g) plus the heuristic estimate to go (h). Using g alone gives Dijkstra, h alone gives greedy best-first search.
  2. 2. What does it mean for a heuristic to be admissible?

    Admissible heuristics are optimistic. That is what guarantees A* returns an optimal path.
  3. 3. On a 4-connected grid with unit steps, which heuristic is admissible and tight?

    Manhattan distance equals the true cost on an obstacle-free 4-connected grid, so it never overestimates.
  4. 4. What happens with weighted A* (h multiplied by w > 1)?

    Inflating h makes the search greedy. You trade guaranteed optimality for speed, with a known bound.

Summary

  • A* expands the cell with the smallest f = g + h; with h = 0 it is Dijkstra.
  • An admissible (and consistent) heuristic keeps the result optimal; use octile for 8-connected grids.
  • Overestimating (weighted A*) is faster but only bounded-suboptimal.
  • Tie-breaking and a heap-based open list matter for speed.
  • Variants (D* Lite, Theta*, Hybrid A*) handle changing maps, any-angle motion, and vehicles.

Next: Potential Fields and Bug Algorithms