The robot navigation problem is getting a mobile robot from its current pose to a goal without hitting anything, which requires three answers: where the robot is, what the surroundings look like, and which route to drive. Open-source navigation software such as Nav2, the successor to the ROS Navigation Stack, splits the work into localization, a costmap of the environment, a global planner, and a local controller. Route search is classic AI, and the best-known method is A* from 1968.
Key takeaways
- Navigation combines localization (where the robot is), mapping (what surrounds it), planning (the route), and control (the actual wheel commands).
- In Nav2, the environment is a 2D grid of cells classed as unknown, free, occupied, or inflated, and the global planner searches that grid.
- A* adds a heuristic estimate of remaining distance to a cheapest-path search, and with an admissible heuristic it still returns an optimal path.
- Wheel odometry drifts, so a separate localization source such as a particle filter or SLAM corrects the robot's position over time.
- Robots also need recovery behaviors, such as clearing a costmap or backing up, because plans fail in real spaces.
Three questions behind every trip
A robot that only knows its goal cannot move toward it. It also needs a position and a picture of free space. The Nav2 documentation on state estimation describes two coordinate transforms that carry the position estimate. The first links the map frame to the odometry frame and comes from a global positioning source, with GPS, SLAM, and motion capture given as examples. The second links the odometry frame to the robot body and comes from odometry, which can use wheel encoders, lidar, radar, visual-inertial methods, or an inertial sensor.
The split exists because odometry drifts. Small errors in wheel counts add up, and the global source periodically corrects the offset. Nav2 documents an adaptive Monte Carlo localization method (AMCL), a particle filter that localizes a robot within a static map, and names SLAM Toolbox as its default SLAM option. SLAM, short for simultaneous localization and mapping, is defined in the standard 2006 tutorial by Hugh Durrant-Whyte and Tim Bailey as the question of whether a robot placed at an unknown location in an unknown environment can incrementally build a consistent map while determining its own location in that map.
The grid the planner searches
Nav2 represents the world as a costmap, a regular 2D grid in which each cell holds a cost and falls into one of four classes: unknown, free, occupied, or inflated. Layers write sensor data from lidar, radar, sonar, or depth images into it. The global planner searches this grid for a path, and local control samples it to choose motion commands. Inflated cells mark space around obstacles.
Searching a grid is a graph problem. Each free cell is a node, each move to a neighboring cell is an edge, and the cost of an edge is the distance or risk of that step. Nav2 lists several planner plugins, including NavFn, three Smac variants (2D, Hybrid-A*, and State Lattice), and Theta Star.
A worked example with A*
Hart, Nilsson, and Raphael introduced the method in "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," published in IEEE Transactions on Systems Science and Cybernetics in July 1968. The idea is to rank cells by f = g + h. Here g is the cost already paid to reach a cell, and h is an optimistic guess of the cost remaining. On a grid where moves are up, down, left, and right, the Manhattan distance (rows apart plus columns apart) never overestimates the true cost, so the answer stays optimal.
Illustrative example: take an 8-by-8 grid, start in the top-left corner, goal in the bottom-right corner, and a small wall of five blocked cells in the middle. The shortest route is 14 moves. If each cell stands for 0.1 meter, that is 1.4 meters. The table compares two searches on this grid. The counts come from a short script written for this article, using the tie-breaking rule that prefers cells farther along a path, and different tie-breaking changes the A* count.
| Search | Heuristic | Path length | Cells expanded |
|---|---|---|---|
| Dijkstra | None (h = 0) | 14 moves | 59 of 59 free cells |
| A* | Manhattan distance | 14 moves | 15 |
Both find the same route. The heuristic only changes how much of the map is examined before the goal is reached, which matters when a planner must re-run several times per second as sensors update.
From path to wheel commands
A planned path is a list of positions, not a set of motor commands. The Nav2 documentation gives these jobs to separate servers. The planner server computes a path from the current pose to the goal. The smoother server refines the path by reducing raggedness and abrupt rotations and by adding clearance from obstacles. The controller server follows the path and computes control efforts from a local environment representation. A behavior tree coordinates the servers, so planning, control, and recovery run in a defined order.
Recovery matters because real spaces change. The Nav2 documentation lists clearing the costmap when sensor faults leave false obstacles, backing up or spinning in place when the robot is stuck, and alerting an operator after a total failure.
Limits and common misconceptions
- A shortest path on the map is not always a good path to drive. Corners, robot size, and sensor noise are why smoothing, inflation, and local control exist.
- A* needs a map. Where the map is unknown or has changed, the robot has to build or update it, which is the job of SLAM.
- An optimal path assumes the costs are right. If a cell is wrongly marked free, the plan is optimal only for the wrong map.
- Nav2 is described as a framework for mobile and surface robots. Other robot types have different motion constraints.
FAQ
Is A* machine learning?
No. A* is a search algorithm with a hand-designed heuristic and no training data. Learning methods can be added to parts of a navigation system, such as perception, but the planner itself is classic AI search.
Why not follow the odometry alone?
Odometry accumulates error, so a robot using it alone drifts away from where it believes it is. Nav2 pairs odometry with a global positioning source that corrects the drift.
What is the difference between global and local planning?
The global planner finds a route across the whole known map. The local controller follows that route while reacting to what the sensors see within a short distance.
Does the Manhattan heuristic work for every robot?
It works for grids with four-way moves. If diagonal moves are allowed or the robot has turning limits, a different admissible heuristic or a different planner is needed.
Related reading
- How AI approaches problem solving
- Heuristics in AI search
- Advances in AI robotics
- Formulating problems as search
More in AI Basics.
Last verified: October 2026
Sources
- Navigation concepts, Nav2 documentation, Nav2 project, 2026
- State estimation, Nav2 documentation, Nav2 project, 2026
- Navigation servers, Nav2 documentation, Nav2 project, 2026
- Hart PE, Nilsson NJ, Raphael B, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics, 1968
- Durrant-Whyte H, Bailey T, Simultaneous Localization and Mapping, Part 1, IEEE Robotics and Automation Magazine, June 2006