A-Star

A* is a path planning algorithm for situations where the robot has a map and needs to find a low-cost route from a start location to a goal.

Imagine a robot moving on a grid. Some cells are free, some cells are blocked by walls, and the robot can move one cell at a time. The planner's job is to decide which free cells to explore until it can connect the start to the goal.

Start With the Search Problem

On a grid, each cell can be treated as a node in a graph. Moving from one free cell to a neighboring free cell has a cost. A path is just a chain of these moves.

The robot needs to answer two questions:

Which cells should I explore next?
When I reach the goal, how do I reconstruct the best route back to the start?

Dijkstra's algorithm answers these questions by always expanding the cell with the smallest known cost from the start. This guarantees an optimal path, but it can waste time exploring cells that are cheap from the start but clearly point away from the goal.

Add a Goal-Directed Estimate

A* keeps Dijkstra's reliable cost tracking, then adds a simple estimate of how far each cell is from the goal. This estimate is called a heuristic.

In the grid demo below, the heuristic is Manhattan distance: how many horizontal and vertical moves remain if there were no walls. The heuristic does not replace the real path cost. It only helps decide which cell looks most promising to explore next.

The A* Score

For every candidate cell \(n\), A* keeps three values:

\(g(n)\): the cost already paid to move from the start to cell \(n\).
\(h(n)\): the estimated remaining cost from cell \(n\) to the goal.
\(f(n)\): the total score used to choose what to explore next.

The score is:

\[ f(n) = g(n) + h(n) \]

A* repeatedly chooses the open cell with the lowest \(f(n)\). A low score means the cell is both reachable from the start and promisingly close to the goal.

Step-by-Step Algorithm

Put the start cell in the open set.
Choose the open cell with the lowest \(f(n)\).
Move that cell to the closed set so it is not processed again.
Check each free neighboring cell.
Update a neighbor if this new route gives it a better \(g(n)\).
Stop when the goal is selected, then trace parent links back to the start.

If the open set becomes empty before reaching the goal, then no valid path exists through the free cells.

Pseudocode

OPEN_SET = {start node}
CLOSED_SET = {}

while OPEN_SET is not empty:
    current = node in OPEN_SET with the lowest f(n)

    if current is the goal:
        return reconstructed path

    move current from OPEN_SET to CLOSED_SET

    for each free neighbor of current:
        if neighbor is in CLOSED_SET:
            continue

        update g(neighbor), h(neighbor), and f(neighbor)
        store current as neighbor's parent
        add neighbor to OPEN_SET

return no path exists

Demo Notebook

See this Jupyter notebook for an example of A* in action:

Try It Yourself

Use the grid below to run the same idea interactively. Click and drag on the grid to draw walls. Drag the S (start) or E (end) node to reposition them, then hit Run A* to watch the algorithm explore and find the shortest path.

Start End Wall Open Set Closed Set Path

Click and drag to draw walls. Drag S or E to move them.