OSREC.016 studies how a mobile robot selects a route through an indoor map without driving through walls, shelving or other obstacles. Mapping tells the robot which locations appear occupied; path planning searches for a connected route between a start and a goal. The A* algorithm combines the cost already incurred with an estimate of the remaining cost. Its output is a candidate path, not a guarantee that a moving robot can safely execute every turn.
The chapter follows OSREC.015 on occupancy grids and navigation costmaps and OSREC.014 on pose-graph mapping. A reasonably accurate map and robot pose are prerequisites for meaningful planning.
How A* evaluates the next map cell
A planner treats traversable grid cells as nodes connected to neighbors. For every candidate node n, A* scores f(n) = g(n) + h(n). The term g is accumulated travel cost from the start; h is a heuristic estimating remaining cost to the goal. The algorithm generally explores promising low-score nodes while remembering better routes and avoiding blocked cells.
On an unobstructed four-connected square grid, Manhattan distance is an appropriate lower-bound heuristic when horizontal and vertical moves have equal cost. Euclidean distance is another lower bound, but may explore more nodes. With nonnegative costs and an admissible heuristic, correctly implemented A* can recover an optimal path on its defined graph. ROS 2 Nav2’s Smac 2D Planner documentation describes a cost-aware grid A* implementation.
Worked example: path length versus direct distance
Assume an invented map with 0.25-meter square cells. Start at grid coordinate (1, 1) and finish at (4, 5). A four-connected robot needs at least |4 − 1| + |5 − 1| = 7 moves, equivalent to 1.75 meters of cell-to-cell travel, provided an obstacle-free seven-move route exists. The straight-line distance is only √(3² + 4²) × 0.25 = 1.25 meters. A wall can increase actual route length beyond either estimate.
Eight-connected planning can permit diagonal transitions, but costs and corner-cutting rules must be defined. A geometrically short grid path is not necessarily drivable by an Ackermann-steered robot with a minimum turning radius. Nav2 provides distinct planner families, including grid-based and kinematically aware options.
Costmaps reward clearance, not merely empty space
Real robots have width and a footprint. Cells next to walls may receive increased traversal costs through inflation, steering routes away from hazardous clearances. The Nav2 Costmap2D specification documents the representation, footprint settings and obstacle-processing layers. Whether unknown space is traversable is an explicit policy choice, not a reason to assume it is safe.
When the world moves after planning
A forklift or pedestrian can invalidate a previously clear route. Updated obstacle observations change the local costmap, which may require replanning; a local controller also responds to the robot’s current motion and nearby hazards. OSREC.013 on state estimation explains pose uncertainty, while OSREC.012 on safety filters discusses constraints separate from global route selection.
A useful read-only lab uses a simulated grid and goal. Compare A* with Dijkstra’s algorithm under identical map costs, record planned length and expanded-node count, then insert an obstacle and recompute the route. Avoid declaring one algorithm universally faster based on a single test. Do not deploy experimental planner settings on occupied shop floors without validation and operational safety controls.
Learning conclusion: A* transforms a map into a costed route by combining distance already traveled with a goal-directed estimate. Successful robot navigation additionally requires current perception, adequate clearance, feasible motion and safe control.

Leave a Reply