Path Planning: A* and the Inflated Map
With a map in hand, 'how do I get there' becomes graph search: grow outward from the start, greet the goal, walk the breadcrumbs back — after fattening every wall by half a robot.
Builds on: 5.2 Mapping: A Floor Plan from a Spinning Laser
The map becomes a graph
An occupancy grid is secretly a graph: each free cell a node, each neighbour-step an edge. Finding a route is then textbook search. The simplest — Dijkstra’s method — grows a frontier outward from the start like ripples in a pond, always expanding the cheapest-so-far cell, until a ripple touches the goal. Walk the breadcrumbs backwards: shortest path, guaranteed.
The ripples are thorough and wasteful — they explore away from the goal as eagerly as toward it. A* (“A-star”) adds one number: each frontier cell is ranked not by distance-so-far alone but by
The guess h steers the ripples toward the goal, collapsing the search to a corridor along the promising direction. The guarantee survives one condition: h must never overestimate (straight-line distance never does — you can’t beat a straight line). Optimistic guesses keep the answer perfect; they only change how much work finding it takes.
Inflation: planning for a robot that has a body
Raw A* treats the robot as a point, and produces paths that shave corners by zero millimetres — geometrically perfect, physically a scraping noise. The standard cure is honest and blunt: inflate every obstacle by the robot’s radius before planning. The fattened map’s point-paths are exactly the real robot’s safe paths. Layer on a further soft “cost cushion” — cells near walls legal but pricier — and paths acquire the polite wall-clearance of a good driver, hugging the middle of corridors without being told to.
Plans meet reality
The world moves — a door closes, a cat sits in the corridor. Real navigation stacks therefore run two planners: a global one (this lesson) charting the whole route on the map, and a fast local one dodging what the lidar sees right now, re-planning several times a second. The global plan is the intention; the local planner is the reflexes. And when the cat wins anyway, the stack’s last resort is honourable retreat: back up, re-plan, try again — the navigation equivalent of Unit 3’s loop, running at journey scale.
A* is not a robot algorithm — it is the algorithm for cheapest-route problems. Your sat-nav runs it over road graphs; game characters over walkable meshes. Robotics’ contribution is the inflation trick: teaching a pure point-mathematics to respect a body.
⚗️ Lab — The Route Table
A grid world with drawable walls. Set start and goal, watch the frontier ripple, then the path appear. Toggles for A* vs Dijkstra; a slider for inflation.
- Run Dijkstra, count the explored cells; switch to A* and count again. Same path, a fraction of the pond.
- Set inflation to zero and study how the path kisses every corner. Raise it to the robot’s radius and watch doorways it no longer fits through.
- Draw a wall across the found path and re-plan — then find the inflation value at which the only door closes entirely.