Path planning is the computation of a collision-free route from a start configuration to a goal configuration for a robot, usually chosen to minimize a cost such as length, travel time, energy or risk. In robot navigation, it answers the question of which way to go, after localization has answered where the robot is and before the controller turns the route into motor commands.
Strictly, a path is a purely geometric sequence of positions, while a trajectory adds timing, velocity and acceleration along that path. Many planners now produce both at once, but the distinction still matters, because a geometrically valid path can be impossible to follow at the speed or with the steering a real vehicle has.
How path planning represents the robot and its world
Path planning works in the configuration space, the space of every possible pose the robot can take. A wheeled robot on a floor has a configuration of position x, y and heading, while a robot arm has one dimension per joint, typically six or seven. Obstacles are mapped into this space, and planning reduces to finding a connected route through its free part.
For mobile robots, the environment is commonly stored as an occupancy grid or a costmap. The costmap inflates each obstacle by the robot’s radius plus a safety margin, so the planner can treat the robot as a single point. Grid size grows quickly: a 100 m by 100 m area at 5 cm resolution already contains 4 million cells, and adding 72 discrete headings multiplies the state count to 288 million.
| Representation | What it stores | Best suited to |
|---|---|---|
| Occupancy grid | Free, occupied or unknown per cell | 2D indoor and warehouse navigation |
| Costmap | Graded traversal cost per cell | Preferring clearance, avoiding risky zones |
| Roadmap graph | Nodes and edges along known lanes | Fixed routes in factories and depots |
| Collision geometry model | Meshes or primitives for checks | Robot arms in high-dimensional spaces |
Main families of path planning algorithms
Path planning algorithms fall into graph search, sampling-based, optimization-based and reactive families, and they differ mainly in the guarantees they give. A planner is complete if it always finds a path when one exists, and optimal if the path it returns has the lowest possible cost.
| Family | Representative methods | Guarantee | Typical domain |
|---|---|---|---|
| Graph search | Dijkstra, A*, D* Lite | Resolution complete and optimal on the grid | 2D mobile robots |
| Sampling-based | PRM, RRT, RRT* | Probabilistically complete; RRT* asymptotically optimal | Arms and high-dimensional spaces |
| Optimization-based | CHOMP, TrajOpt, MPC formulations | Local optimum only | Smoothing and refining a rough path |
| Lattice and kinematic search | State lattices, Hybrid A* | Feasible for a given vehicle model | Cars, forklifts, tractors |
| Potential fields | Attractive goal, repulsive obstacles | None; can stall in local minima | Simple reactive behavior |
A* dominates grid planning because a good heuristic, such as straight-line distance to the goal, focuses the search. As long as the heuristic never overestimates the remaining cost, A* still returns an optimal path. Sampling-based planners avoid building an explicit grid, which is why they handle a seven-joint arm where a grid would be astronomically large.
Global and local path planning
Practical navigation systems split the problem into a global planner that computes the whole route on the known map and a local planner that follows it while reacting to obstacles the map does not contain. Local reaction overlaps with obstacle avoidance, which is usually implemented inside this local layer.
| Aspect | Global planner | Local planner |
|---|---|---|
| Scope | Start to goal across the whole map | A few meters around the robot |
| Input | Static map and global costmap | Live sensor data and local costmap |
| Update rate | On demand or about 1 Hz | About 10-50 Hz |
| Typical methods | A*, Dijkstra, Hybrid A* | Dynamic window approach, timed elastic band, MPC |
| Output | Geometric path | Velocity commands or short trajectory |
The split keeps computation manageable, but it creates a known weakness: a local planner sees only its window, so it can steer into a dead end that the global planner would have avoided. Robust stacks therefore trigger global replanning whenever the local planner reports that progress has stalled.
Choosing a path planner
The right planner depends on the dimension of the configuration space, the vehicle’s kinematics and how fast the environment changes. The decision table summarizes common situations.
| Situation | Recommended approach | Reason |
|---|---|---|
| Differential-drive robot indoors | A* on a costmap plus a local planner | Turns in place, so geometric paths are feasible |
| Car-like vehicle or forklift | Hybrid A* or a state lattice | Respects the minimum turning radius |
| Six- or seven-joint arm | RRT-Connect, then smoothing | Grids are impractical in many dimensions |
| Frequently changing map | D* Lite or fast incremental replanning | Reuses earlier search effort |
| Fixed lanes in a factory | Graph search on a roadmap | Predictable, auditable traffic |
Common path planning failures
- Kinematically infeasible paths. A grid path with sharp corners cannot be driven by a car-like robot; the planner must model the turning radius or the path must be smoothed accordingly.
- Wrong inflation radius. Too little inflation lets paths graze walls; too much closes doorways that are physically passable.
- Narrow passages. Sampling-based planners rarely draw samples inside tight gaps, so they can fail to find a path that clearly exists.
- Oscillating plans. Two routes of almost equal cost can alternate between cycles, making the robot hesitate; a small bias toward the current plan prevents this.
- Ignoring moving obstacles. Treating people as static leads to plans that cut across their walking direction; prediction-aware costs reduce such conflicts.
A non-technical view
Path planning is a robot’s version of choosing a route on a map before setting off. It looks at where walls, shelves and other obstacles are and works out a way to the goal that avoids all of them.
Like a driver using a navigation app, the robot first picks the overall route and then makes small adjustments on the way when a person or a cart suddenly blocks the corridor. If the way is fully blocked, it simply plans a new route.
A concrete example
A hospital delivery robot carries medication between floors. Its map of one floor covers 120 m by 80 m at 5 cm per cell, or 3,840,000 cells. The costmap inflates every wall by the robot’s 0.35 m radius plus a 0.15 m margin, so the global A* planner keeps the robot at least half a meter from walls wherever the corridor allows.
Along the route, a local planner running at 20 Hz slows the robot near doorways and steers around beds parked in the corridor. When a corridor is fully blocked by a cleaning crew, the local planner stops making progress, the global planner reroutes through a parallel corridor in under a second, and the delivery arrives a minute later instead of waiting for the corridor to clear.