A* search
Also: A-star
A graph-search algorithm prioritizing traveled cost plus estimated remaining cost.
It expands nodes by f(n)=g(n)+h(n); completeness and optimality depend on graph and heuristic conditions.
- Formula
f(n)=g(n)+h(n)
Example A* finds a lowest-cost grid route with an admissible heuristic and nonnegative edge costs.
Common misconception A* does not itself model robot footprint, dynamics, or changing obstacles.