A-Star

◀ Go to Preliminaries

Go to RRT ▶

A* is a widely used graph traversal and pathfinding algorithm that finds the path from a given initial node to a given final node while minimizing the total cost (distance plus any other costs). It uses a combination of Best First Search and Dijkstra’s algorithm.

Demo

See this Jupyter notebook for an example of A* in action:

A* vs Dijkstra

A* Algorithm

Dijkstra’s Algorithm

Basics of A*

A* works by trying to choose the most promising path at every step.
To do this, it keeps track of three values for each node it explores.

• g(n) – the actual cost from the start node to the current node.
  This represents how far we have already traveled.

• h(n) – the estimated cost from the current node to the goal.
  This estimate is called the heuristic. A common heuristic is the straight-line distance to the goal.

• f(n) – the total estimated cost of going through this node to reach the goal.

The formula is:

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

The algorithm always chooses the node with the lowest f(n) value because it appears to be the cheapest path overall.

Intuition

You can think of A* like navigating in an unfamiliar city.

When deciding which street to take, you consider two things:

1. How far you have already walked.
2. How far you estimate you still need to go to reach your destination.

A* combines these two pieces of information to decide which direction looks most promising.

Instead of exploring every possible path, it focuses on paths that seem likely to reach the goal faster.

How A* works

1. Start by putting the starting node into a list of nodes that need to be explored (called the open list).

2. While there are still nodes in the open list:

3. Select the node with the lowest f(n) value.

4. Remove it from the open list and mark it as explored.

5. Look at all neighboring nodes that can be reached from the current node.

6. For each neighbor:

7. Compute the cost g(n) from the start to this neighbor.

8. Estimate h(n) from the neighbor to the goal.

9. Compute f(n) = g(n) + h(n).

10. Add the neighbor to the open list if it has not been explored yet.

11. If the goal node is reached, the algorithm reconstructs the path by following the parent nodes back to the start.

12. If the open list becomes empty before reaching the goal, it means that no valid path exists.

Why A* is useful

A* is one of the most popular path planning algorithms because it finds optimal paths efficiently.
It is widely used in:

• robotics navigation
• video game AI
• GPS route planning
• autonomous vehicles