computer science//algorithms//graph search//A* search

A* search is a best-first graph search algorithm that always expands the node with the smallest cost paid so far plus estimated cost still to go, and it is the standard way a mobile robot, a game character or a vehicle navigation stack finds a shortest path on a map. Published in 1968, it runs today in the planners of ROS 2's navigation stack (Nav2) and in every grid-based route finder.

A* search is a best-first graph search algorithm that always expands the node with the smallest cost paid so far plus estimated cost still to go, and it is the standard way a mobile robot, a game character or a vehicle navigation stack finds a shortest path on a map. Published in 1968, it runs today in the planners of ROS 2's navigation stack (Nav2) and in every grid-based route finder.

Each node nnn is ranked by

f(n)=g(n)+h(n),f(n) = g(n) + h(n),f(n)=g(n)+h(n),

where g(n)g(n)g(n) is the real cost from the start to nnn and h(n)h(n)h(n) a heuristic estimate of the cost from nnn to the goal. On a warehouse occupancy grid where the robot moves in four directions, a natural hhh is the Manhattan distance, the sum of the horizontal and vertical gaps to the goal: walls can only make the real path longer.

With an admissible heuristic the search returns the optimal path, and the better the heuristic informs without overestimating, the less it explores.

An admissible heuristic never overestimates the true remaining cost. With h=0h=0h=0 A* is Dijkstra's algorithm; with the perfect hhh it walks straight down the optimal path and expands nothing else.

Overestimating buys speed for a bounded loss. Weighted A* multiplies hhh by ε>1\varepsilon>1ε>1: it searches more greedily toward the goal, and the path it returns costs at most ε\varepsilonε times the optimum. Running it with a decreasing ε\varepsilonε turns it into an anytime algorithm, a fast rough path first and better ones while time remains.

Its cost is memory as much as time. A* keeps every node it has reached in its open and closed lists, which on large maps can be the binding limit on an embedded computer; the Euclidean distance is admissible too, but on a four-connected grid the Manhattan distance is tighter and expands fewer nodes.

A grid path ignores the vehicle. A car-like robot cannot turn in place, so Nav2 offers Hybrid A*, a variant that searches over continuous positions and headings and returns paths the vehicle can follow; in many dimensions (an arm's joints) grids give way to sampling methods such as RRT (motion planning).