A* Search

A shortest-path search algorithm that expands whichever node has the lowest cost so far plus estimated cost to the goal.

A* is a search algorithm for finding the shortest path on a graph or grid map, proposed in 1968 by Hart, Nilsson, and Raphael at the Stanford Research Institute for the Shakey mobile robot project. At each step it expands the node with the smallest f(n) = g(n) + h(n): g(n) is the actual cost already spent getting from the start to node n, and h(n) is an estimate of the cost from n to the goal (the heuristic function, such as straight-line distance). As long as h never overestimates the true remaining cost (called admissible), A* is guaranteed to find the shortest path; when h is always zero, it degenerates into Dijkstra's algorithm, which searches outward evenly in all directions. It's commonly used for global path planning in mobile robots and in game pathfinding; a robot arm's high-dimensional joint space usually calls for sampling-based planners like RRT instead. A variant that accounts for a vehicle's turning constraints is called hybrid A*.

ExampleA vacuuming robot navigating from the living room to the bedroom on an occupancy grid with 5 cm cells: each step costs 1, h is taken as the straight-line distance from the current cell to the bedroom, and A* finds the shortest route around occupied cells, which is then handed to a local planner to follow.

Also called

A*, A-Star

Related

Dijkstra's Algorithm · Hybrid A* · Path Planning · Costmap · Global Planning and Local Planning · Rapidly-exploring Random Tree

Sources

Wikipedia: A* search algorithm