graph search (planning)
Graph search is a family of methods for finding a route when the world has been boiled down to a graph — a set of dots (called nodes), each standing for a place or state the robot could be in, joined by lines (called edges) that say "you can step directly from this dot to that one," often with a cost attached for how expensive or long that step is. Picture a subway map: stations are the dots, the track segments between them are the lines, and you want the best way from your station to your destination. Graph search is simply the disciplined procedure for finding that best way through such a web of connections.
To use it for robot motion, you first have to turn the smooth, continuous space of poses into one of these graphs — typically by chopping it into a grid of cells, or by scattering sample poses and linking nearby safe ones. Once that graph exists, a graph-search algorithm explores it outward from the start, fanning across edges and keeping track of the cheapest way reached to each node so far, until it touches the goal; then it traces that record backward to read out the winning route. This is the backbone of a huge share of practical planners — the well-known names Dijkstra's algorithm and A* are both graph searches — and its great strength is a guarantee: if a route through the graph exists, these searches will find it, and (for Dijkstra, or for A* with an admissible cost estimate) it will be the cheapest one in the graph.
Lay a grid over a floor map: every open cell is a node, and each node links to its neighboring open cells. A graph search starting at the robot's cell spreads outward cell by cell until it reaches the goal cell, then reports the shortest chain of cells back home.
Grid cells become nodes, neighbors become edges — the simplest way to turn a map into a searchable graph.
Continuous pose-space must first be turned into a graph — by a grid of cells or by sampled poses — before any graph-search algorithm can run on it.