OSREC.016: A* Path Planning for Robots

Rich oil painting of a Latino robotics engineer reviewing a grid map and path on a monitor while an autonomous wheeled robot navigates a warehouse, with the original BitcoinVersus.tech neon-green watermark on black at bottom-left.

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.

Computerphile, “Path Planning for Robotics.” Assistant Professor Ayse Kucukyilmaz explains the robot path-planning problem and practical navigation challenges.

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.

The Construct Robotics Institute, “How to Teach ROS 2 Path Planning: Compute Routes Without Moving the Robot” (July 2026). Demonstrates costmaps, planner configuration and route visualization in RViz without actuating the robot.

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.

2 responses to “OSREC.016: A* Path Planning for Robots”

  1. […] where to go; a local controller selects the next feasible motion. The distinction builds on OSREC.016 on A* search and OSREC.015 on […]

    Like

  2. […] OSREC.016 lesson on A* examined the shortest-path search over a graph with known costs. D* Lite allows edge costs to […]

    Like

Leave a Reply