---
title: "Path planning, explained with a napkin"
slug: path-planning-explained
date: 2026-08-14
url: https://mohammadhameed.dev/posts/path-planning-explained
tags: ["robotics", "explainers"]
---

The fastest way to understand autonomy research is to stop trusting the
word "optimal." Here's the whole idea of my master's thesis, at napkin
resolution.

## The grid is the point

Picture a city map as graph paper. Every square has a cost. A\* works
the way a careful planner would: it keeps a queue of partial routes and
always extends the one whose *estimated* total — what you've spent so far
plus a hopeful guess about the rest — looks cheapest. When it reaches the
destination, the route is provably optimal for the numbers you fed it, as
long as those hopeful guesses never overestimate what's left. That last
condition is the whole thing. The estimates are only as honest as the map.

```python
# the honest version: cost is not distance
def cell_cost(cell, aircraft):
    risk = risk_model[cell.resolution].interval  # mean AND confidence
    return (
        cell.distance
        + risk.mean * aircraft.time_in_cell
        + risk.width * aircraft.caution_weight   # the "I might be wrong" term
    )
```

That last line is where every real deployment lives. The risk is an
*interval*, not a point, because a map is always coarser than the world.

## Where the grid lies

Uniform grids lie in two directions at once:

1. Over boring fields, they pretend to know more than they do (and burn
   compute per square kilometre).
2. Over stadiums, they pretend to know less than they do — one "medium"
   cell averaged from an empty parking lot and a full crowd.

The fix is a **layered quadtree**: subdivide where consequence lives.

<Figure src="/images/posts/path-planning-explained-alt.svg" alt="Coarse cells, fine cells, and a route threading between the honest ones" caption="A quadtree admits its own resolution; a uniform grid can't." />

<Callout type="note">
Every level of the tree is queryable mid-flight, so the aircraft can ask
"how sure are you about that cell?" at exactly the moment it needs to
decide whether to trust the map.
</Callout>

## The part that surprised me

The 27,000-route simulation did not prove risk-aware routes are safer in a
way a statistician could point at. It proved they are *explainable*. When a
route bent 800 metres around a school at 3 p.m. and cut the corner at 6 a.m.,
every reviewer — pilots, regulators, engineers — read the intent off the
shape. The planner had become legible.

That's the transferable lesson for anyone building AI systems that people
have to trust: **optimality wins the demo; legibility wins the deployment.**

The long version, with all the math I skipped, is
[the thesis](https://hdl.handle.net/1880/125583). The five-minute version is
the [project page](/projects/risk-aware-path-planning).