Path planning

You're late for class and there's a fire drill blocking the main corridor. Without thinking hard, you reroute — down the back stairs, through the canteen, out the side door. You didn't compute a mathematical solution; you did something even more impressive: you pictured the building, identified obstacles, and found an alternative sequence of connected spaces that gets you there. A robot needs to do exactly the same thing, but explicitly, in code.

That process — finding a collision-free geometric route from A to B — is called path planning.

What a path planner actually produces

A path is a sequence of positions (or poses — position plus orientation) that, when followed in order, move the robot from its start to its goal without passing through any obstacle. The path planner doesn't care yet about speed, acceleration, or how long each segment takes — that's the job of trajectory planning. It cares only about geometry: what route is feasible?

The map of free versus occupied space is usually represented as an occupancy grid (a discretised grid where each cell is marked free or blocked) or as a configuration space — a mathematical representation of all valid robot configurations.

Common algorithms

Two algorithms appear in virtually every robotics course and deployed system:

A* (A-star) treats the map as a graph, searches from start to goal, and uses a heuristic (a smart guess about remaining distance) to avoid exploring irrelevant parts of the map. It guarantees finding the shortest path if one exists. Most ROS-based mobile robots use A* or a variant like Dijkstra's algorithm as their global planner.

RRT (Rapidly-exploring Random Tree) is better suited for high-dimensional spaces and robot arms. It grows a tree by sampling random points in the configuration space and connecting them, until the tree reaches the goal region. It doesn't guarantee the shortest path, but it finds a path efficiently even in complex, cluttered environments.

A real example: warehouse robots

Amazon's Kiva robots (now Amazon Robotics) navigate warehouse floors by planning paths on a known grid map. A central server runs path planning for hundreds of robots simultaneously, assigning routes that avoid collisions between robots, not just between robot and shelf. The planner re-routes a robot within milliseconds if another robot's path creates a conflict.

Path planning versus motion planning

Path planning answers "where do I go?" Motion planning — a broader concept — also answers "how exactly do I move my joints or wheels to follow that path?" The two are often discussed together, but distinguishing them is useful: a valid path in abstract space still needs a motion planner to translate it into motor commands.

The classic A* algorithm was invented in 1968 to help a robot called Shakey navigate its room — making it one of the first algorithms ever written for a mobile robot.