Drones and self-driving basicsMiddleLesson 2847 min read

Planning a path

Turn the world into a grid of free and blocked squares, then search for the shortest route. Learn breadth-first search and A*, the classic path planners.

✦ Ask the tutor 🧪 Lab · 30 min 📝 Lesson test

Speed

Lesson in motion

In 60 seconds

Planning a path

Turn the world into a grid of free and blocked squares, then search for the shortest route. Learn breadth-first search and A*, the classic path planners.

1/4

In simple words

Imagine a maze drawn on squared paper. You put your pencil on the start and try every square next to it, then every square next to those, like ripples spreading in a pond. The first ripple that touches the exit shows you the shortest way. A smarter trick: try the squares that point towards the exit first. That is the idea behind A*.

Once a machine knows where it is, it must decide how to get where it wants to go. A simple and very common way is to draw the world as a grid map: small squares that are either free or blocked. A delivery robot in a warehouse, a vacuum cleaner in a flat, or a drone flying over a field can all use grids like this.

Each free square is a place the robot can be. Two squares are connected if the robot can move directly between them, for example up, down, left or right. Now path planning becomes a search: find a chain of connected free squares from start to goal.

Breadth-first search (BFS)

BFS spreads out from the start one ring at a time: first all squares 1 step away, then 2 steps, and so on. Because it explores in order of distance, the first time it reaches the goal it has found a shortest path. BFS is simple and correct, but it wastes effort exploring in every direction, even away from the goal.

Python: BFS counts the fewest stepspython

from collections import deque

grid = [
    "S..#....",
    ".#.#.##.",
    ".#...#..",
    ".####.#.",
    "......#G",
]
rows, cols = len(grid), len(grid[0])
start, goal = (0, 0), (4, 7)

dist = {start: 0}
queue = deque([start])
while queue:
    r, c = queue.popleft()
    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] != "#" and (nr, nc) not in dist:
            dist[(nr, nc)] = dist[(r, c)] + 1
            queue.append((nr, nc))

print("fewest steps from S to G:", dist.get(goal, "no path"))
print("squares explored:", len(dist))

A*: search with a sense of direction

A* (say "A star") is like BFS with a compass. For each square it keeps two numbers: g, the steps taken from the start so far, and h, a guess of the steps still needed to reach the goal. It always explores next the square with the smallest f = g + h.

On a grid where you move up, down, left or right, a good guess is the Manhattan distance: rows apart plus columns apart. It never overestimates, because walls can only make the real path longer. When the guess never overestimates, A* is guaranteed to find a shortest path, and it usually explores far fewer squares than BFS.

1
Start
Put the start square in a priority list with f = h(start).
2
Pick
Take out the square with the smallest f.
3
Goal?
If it is the goal, walk back through the saved "came from" links to get the path.
4
Expand
For each free neighbour, if this route to it is shorter than any found before, save its cost and where it came from, and add it with f = g + h.
5
Repeat
Until the goal is found, or the list is empty (no path exists).

Planner	Finds shortest path?	Explores	Notes
BFS	Yes, when every step costs the same	Everything, ring by ring	Simplest correct method
Dijkstra's algorithm	Yes, even when steps cost different amounts	In order of cost from the start	For roads with different lengths or speeds
A*	Yes, if the guess never overestimates	Mostly towards the goal	The usual choice on maps
Greedy "go towards the goal"	No	Very little	Fast but can get stuck behind walls

Note

Real planners do more than find the shortest line. They prefer smooth turns, avoid squares near obstacles, respect speed limits and battery, and plan again when something changes. Many robots also plan in two layers: a global route on the map, and a local planner that reacts to things moving nearby.

Real example

A small team in Chennai builds a robot that carries files between offices on one floor. They draw the floor plan as a grid, mark walls and cupboards as blocked, and use A*. On day one it plans a route straight through a doorway that is usually closed. They add a rule: closed doors are blocked until a sensor sees them open. The algorithm was right; the map was wrong.

Try this. In the BFS code, change the # in the top row to .. Does the step count change? Does the number of squares explored change?

Watch and read more

Lab

A working A* planner that finds a valid, shortest path on a grid, or says there is none.

~30 min

The problem

This runs in your browser. The starter already has the grid, neighbours, the Manhattan guess and most of A*.

Finish TODO 1: when the goal is reached, walk back through came_from to build the path, and reverse it so it goes from start to goal.
Finish TODO 2: when you find a cheaper way to a neighbour, save its cost and where it came from, and push it on the heap.
Run it. The path is drawn with *.
Add a wall that cuts the grid in two, and check that astar returns None.

The check tests your planner on several grids: the path must start and end in the right place, move one square at a time, never enter a wall, and be as short as possible.

Practice lab

Edit the code and run it. Python runs in your browser — nothing is sent to our server.

Ctrl + Enter to run

import heapq

GRID = [
    "S...#.....",
    ".##.#.###.",
    ".#..#...#.",
    ".#.###.#..",
    "...#...#.#",
    ".#...#...G",
]

def find(grid, ch):
    for r, row in enumerate(grid):
        if ch in row:
            return (r, row.index(ch))

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

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def astar(grid, start, goal):
    """Return the shortest path as a list of (row, col) cells from start to goal,
    including both ends. Return None if there is no path."""
    heap = [(manhattan(start, goal), 0, start)]
    came_from = {start: None}
    cost = {start: 0}
    while heap:
        f, g, cell = heapq.heappop(heap)
        if cell == goal:
            # TODO 1: walk back from goal through came_from, then reverse
            return None
        for nxt in neighbours(grid, cell):
            new_cost = g + 1
            # TODO 2: if nxt is not in cost, or new_cost < cost[nxt]:
            #   save cost[nxt] and came_from[nxt], then push
            #   (new_cost + manhattan(nxt, goal), new_cost, nxt) on the heap
            pass
    return None

start, goal = find(GRID, "S"), find(GRID, "G")
path = astar(GRID, start, goal)
if path is None:
    print("No path found")
else:
    print("Path length (steps):", len(path) - 1)
    rows = [list(row) for row in GRID]
    for r, c in path[1:-1]:
        rows[r][c] = "*"
    print("\n".join("".join(row) for row in rows))

Output

No output. Add print(...) to see values.

You are done when

The path starts at S, ends at G, moves one square at a time and never enters a wall
The path length matches the shortest possible (the check compares it with BFS)
astar returns None when a wall splits the grid
The learner can explain what came_from stores and why the path must be reversed

Hard questions

Try to answer before you reveal. If you can answer these, you understood the lesson.

Q1What happens to A* if you use h = 3 × Manhattan distance?Reveal

The guess can now overestimate, so A* is no longer guaranteed to find the shortest path. It becomes greedier: it rushes towards the goal and usually explores fewer squares, but it may return a longer route. Some real systems accept this on purpose to plan faster, a trade-off called weighted A*.

Q2Why does the heap store g as well as f?Reveal

So that when a square is taken out, we know the cost of the route that put it there, and can compute the cost to its neighbours. A square can be pushed more than once with different costs; storing g with each entry keeps each route's cost correct. Some versions also skip an entry if a cheaper cost for that square is already known.

Please sign in to continue.

Questions people ask

Why does A* need a guess that never overestimates?

If the guess can be too big, A* may think a good route is worse than it really is, and finish with a longer path. A guess that is never too big (called admissible) keeps the shortest path safe. A guess of zero everywhere is also admissible; then A* behaves like Dijkstra's algorithm.

What if the robot can move diagonally?

Then each square has up to eight neighbours, diagonal steps usually cost about 1.41 instead of 1, and you need a different guess, such as the straight-line distance. Many planners also forbid cutting diagonally past the corner of a wall.

Do self-driving cars use grids?

Often in parts. Long routes are usually planned on a road network, like a map app does. Near the car, systems often use grids or other maps of free space to plan exact movements around obstacles.

What if the map is huge?

Grids get very big in 3D or over large areas. Planners then use coarser grids, graphs of important places, or sampling methods that try random points and connect them. The ideas of cost and a good guess still apply.

Lesson test

5 questions. Get 3 right (60%) to pass and complete this lesson.

Planning a path

Planning a path

Breadth-first search (BFS)

A*: search with a sense of direction

Start

Pick

Goal?

Expand

Repeat

Watch and read more

The problem

Practice lab

You are done when

Hard questions

Questions people ask