Graph search is a contract between the map discretization and the motion the robot can actually execute.
A Local Planner With Commitment Issues
Graph search: BFS, Dijkstra, A* turns maps and goals into constrained motion. The planner is not searching for a pretty line; it is choosing a feasible commitment under geometry, dynamics, uncertainty, moving obstacles, and recovery rules.
Problem First
Grid maps and roadmaps become actionable only after the robot defines nodes, edges, and costs. Breadth-first search assumes equal edge cost, Dijkstra handles positive costs, and A* adds a heuristic that focuses expansion toward the goal.
A* is correct when the heuristic is admissible, meaning it never overestimates the true remaining cost. Consistency gives an even stronger property: once a node is expanded, its best cost is known. Those guarantees matter when the graph stands in for physical space.
A shortest path is only meaningful on a graph that matches the robot body.
Formal Model
Most navigation methods can be read as constrained search or optimization:
$$ f(n)=g(n)+h(n),\quad 0\le h(n)\le h^*(n) $$
The cost term is graph distance or risk-weighted distance; constraints are traversable cells, obstacle inflation, motion connectivity, and heuristic admissibility.
- Build nodes from grid cells, topological places, or lattice states.
- Assign edge costs for distance, clearance, slope, turn penalty, and risk.
- Choose a heuristic whose units match the edge cost.
- Audit the found path against collision checks and controller feasibility.
Worked Diagnostic
Code Fragment 1 isolates graph-search invariants: frontier update, predecessor map, path cost, and heuristic behavior. The point is to verify the path object before handing it to a controller.
# Compute A* priorities for three frontier nodes.
# The admissible heuristic focuses search without changing cost units.
frontier = [
{"node": "A", "g": 4.0, "h": 6.0},
{"node": "B", "g": 7.0, "h": 2.0},
{"node": "C", "g": 5.0, "h": 5.0},
]
ranked = sorted((n["g"] + n["h"], n["node"]) for n in frontier)
print(ranked)
print(f"expand={ranked[0][1]}")Expected output interpretation. The frontier printout shows that node B is expanded first because its combined score $f=g+h$ is smallest, even though it is not the node with the smallest traveled cost alone. Nodes A and C tie at 10.0, which is a useful reminder that tie-breaking policy can still influence search order and runtime even when optimality is unchanged.
Tool Workflow
NetworkX can teach graph search in a few lines, while Nav2 global planner plugins apply the same idea to costmaps and robot goals. The shortcut saves manual priority queues, path reconstruction, and middleware integration.
Keep the tiny graph-search implementation as a test for admissibility, cost accumulation, and predecessor reconstruction. Use Nav2 global planners or OMPL when maps and robot constraints get large.
Replay a blocked corridor, wrong map cell, diagonal-motion mismatch, stale costmap, and localization offset. Graph search fails differently when the graph is wrong versus when execution is wrong.
Log open set size, closed set, predecessor map, final path, costmap snapshot, and controller tracking error. That evidence separates search quality from downstream execution.
Freeze grid resolution, obstacle inflation, heuristic, tie breaking, start-goal convention, and cost encoding before comparing BFS, Dijkstra, and A*. Small convention changes can dominate the result.
The frontier includes dynamic graph search, learned heuristics with admissibility checks, and multi-resolution planners that combine topological maps with local geometric grids.
Graph search is a contract between the map discretization and the motion the robot can actually execute.
Can you state the search space, cost function, constraints, replanning trigger, controller interface, and failure metric for graph search: bfs, dijkstra, a*? If not, the planner is not specified enough to deploy.
Graph search: BFS, Dijkstra, A* is ready for embodied use when route quality, dynamic feasibility, local control, and recovery behavior are measured in the same replay.
Run the panel on the same grid with uniform cost, weighted cost, and a blocked cell. Report expanded nodes, path cost, tie-breaking behavior, and the local controller command produced from the chosen path.
What's Next?
Continue to Section 30.3: Sampling-based planning, where this planning contract connects to the next embodied capability.
Section References
LaValle, S. M. "Planning Algorithms." Cambridge University Press, 2006. http://lavalle.pl/planning/
Open textbook reference for graph search, sampling-based planning, configuration spaces, and kinodynamic planning.
OMPL Project. "Open Motion Planning Library." Official documentation. https://ompl.kavrakilab.org/
Primary tool reference for sampling-based planners such as RRT, RRTstar, PRM, and kinodynamic variants.
ROS 2 Navigation Project. "Nav2 documentation." Official documentation. https://navigation.ros.org/
Primary documentation for global planners, controllers, costmaps, behavior trees, and recovery behaviors.