Turning Free Space Into a Graph
Before a robot can plan a route, it needs a way to describe "all the places it could be." A clean way to do this is to overlay a grid on the world and chop the floor into square cells. Each cell is either open (the robot can stand there) or blocked by an obstacle — this split between free space and obstacle space is the foundation of planning. The open cells become the places we are allowed to visit.
Now connect each open cell to its open neighbors — the cells just north, south, east, and west (and often the four diagonals too). Each connection is an "edge" you can travel along, and each edge has a cost: usually the distance to step across it. What you have built is a graph — a collection of dots (cells) joined by lines (moves). Finding a route is now exactly the same as planning a trip on a subway map: hop from station to station until you reach your stop.
This reframing is powerful because computer scientists have studied graph search for decades. Once the world is a graph, we can borrow well-understood, provably correct algorithms instead of inventing something fragile. The grid also quietly handles the robot's body: by marking any cell the robot can't fit into as blocked, the search only ever returns paths that pass a collision check.
Dijkstra: A Flood That Fans Out Evenly
Dijkstra's algorithm is the patient, careful way to find the shortest route. Picture pouring water onto the start cell. The water spreads outward, always filling the nearest dry cell next. Because it always grows from the cheapest-reached frontier first, the moment the flood touches the goal you know you've arrived by the shortest possible route — nothing cheaper could have gotten there sooner.
- Give every cell a running "cheapest cost from start" tally. The start is 0; everything else begins at infinity (unreached).
- Repeatedly pick the unsettled cell with the smallest tally — the cheapest frontier — and "settle" it; its cost is now final.
- For each neighbor, check whether reaching it through this cell is cheaper than its current tally. If so, lower the tally and remember this cell as the way you got there.
- Stop when you settle the goal. Then walk the "how I got here" links backward from goal to start to read out the path.
A*: Dijkstra With a Sense of Direction
Dijkstra's blindness — fanning out evenly, even away from the goal — is wasteful when you already know roughly where the goal is. A* search fixes this by giving the flood a sense of direction. For every cell it adds a heuristic: a cheap guess of how much distance still remains to the goal, usually just the straight-line ("as the crow flies") distance.
Where Dijkstra ranks cells by cost-so-far alone, A* ranks them by cost-so-far plus the heuristic guess of cost-still-to-go. In one short formula, it scores each cell by f = g + h: g is the real distance already traveled from the start, and h is the estimated distance left. Cells that lie toward the goal score lower on f and get explored first, so the search leans hard in the right direction and ignores most of the map behind it.
priority of a cell f(cell) = g(cell) + h(cell) g(cell) = real cost from start to this cell (known) h(cell) = guessed cost from this cell to goal (estimate) Dijkstra is just A* with h = 0 (no sense of direction).
From Textbook Grid to Robot Map
A real robot doesn't get a tidy grid handed to it — it builds one from its sensors. The usual product is an occupancy grid map: a grid of cells where each value is the robot's belief that the cell is occupied, free, or unknown. That belief map is exactly the open-versus-blocked picture Dijkstra and A* need to run.
Before planning, robots usually convert the occupancy grid into a costmap, where cells carry not just "blocked or not" but a graded cost of being there. Cells hugging an obstacle get inflated to a high cost even when technically free, which nudges the planner to leave a comfortable margin rather than scrape the walls. Feed that costmap to A* and you get routes that are short and sensibly clear of danger.
In practice, A* over a costmap is the classic global planner inside a robot's navigation stack. It draws the big-picture route across the whole map; a separate, faster local planner then turns that route into smooth, moment-to-moment motion commands and dodges things that pop up after the map was made. This split between global and local planners is why a delivery robot can both head across a building and swerve around a passing cart.
Where Grids Run Out of Room
Grids are wonderful, but they have two honest limits. First, they blur fine geometry: a cell is either open or closed, so a doorway just barely wide enough for the robot can vanish if it straddles a cell boundary, and a path is locked to right-angle and 45-degree steps unless you smooth it afterward. Remember, too, that the grid plans a route in space — a path, not a trajectory — leaving speed and timing for a later stage to fill in.
The second limit is fatal for arms. A flat floor is a 2D grid; a robot arm with six joints lives in a six-dimensional configuration space, where a "cell" is one combination of all six joint angles. Chop each dimension into just 100 steps and you get 100^6 — a trillion — cells. No flood, however clever its heuristic, can settle a trillion cells. The grid simply blows up.
That explosion is exactly why high-dimensional planners abandon the full grid. Instead of visiting every cell, sampling-based planning scatters random points through the configuration space and connects only the ones that turn out collision-free — methods like the Rapidly-exploring Random Tree (RRT) grow a path toward the goal without ever enumerating the whole space. That is the natural next step once a grid can no longer fit in memory.