Navigation & SLAM

A* Algorithm

A* is a best-first graph search algorithm that finds a least-cost path between nodes by expanding the frontier in order of estimated total cost, the sum of the cost-so-far and an admissible heuristic estimate of the remaining cost. Introduced by Hart, Nilsson, and Raphael in 1968 during work on the Shakey robot project, it is guaranteed to return an optimal path when the heuristic never overestimates. Variants such as weighted A*, D* Lite, and Hybrid A* extend it to replanning and kinodynamic settings.

Why it matters for physical AI

Grid- and lattice-based A* variants remain the workhorse of global path planning in mobile robot autonomy stacks, providing predictable, optimal routes that learned local policies can then track and refine.