computer science//algorithms//graph search

Graph search is a family of algorithms that find a least-cost path through a graph of states by expanding nodes one at a time in some order, and it is how a warehouse robot, a car's navigation system or a network router chooses a route. The graph's nodes are places or situations, its edges the moves between them, each with a cost (distance, time, energy, risk); the answer is the cheapest chain of edges from a start to a goal.

Graph search is a family of algorithms that find a least-cost path through a graph of states by expanding nodes one at a time in some order, and it is how a warehouse robot, a car's navigation system or a network router chooses a route. The graph's nodes are places or situations, its edges the moves between them, each with a cost (distance, time, energy, risk); the answer is the cheapest chain of edges from a start to a goal.

What every member shares is the loop: keep a frontier of nodes reached but not yet expanded, take one out, look at its neighbours, record the best cost found so far to each, and stop when the goal is taken out. The members differ only in which node they take next. Uninformed search ranks the frontier by the cost already paid: Dijkstra's algorithm spreads from the start in rings of equal cost, like an oil stain, and is exact but blind to where the goal is. Informed search adds an estimate of the cost still to go: A* search expands the node whose cost so far plus estimated remainder is smallest, and with an estimate that never overestimates it stays exact while exploring far less.

A robot's floor becomes such a graph through an occupancy grid: each free cell is a node, each step to a neighbouring free cell an edge. That is the standard layout of a global planner in motion planning.

Grids drown in dimension. A 7-joint arm with 100 values per joint has 101410^{14}1014 cells (curse of dimensionality), so high-dimensional configuration spaces are searched by sampling instead, with RRT.

The shortest path is often the wrong one to drive. It grazes corners and ignores the vehicle's dynamics, which is why planning comes in layers: a global geometric search at about 1 Hz and a local planner with dynamics at 10 to 20 Hz.