A* Path Planning
A* searches a grid map for the shortest path. It explores cells in order of the cost so far plus a guess of the cost still to go, so it heads toward the goal instead of searching in every direction.
Click or drag on the grid to draw walls. Drag the start or goal to move them.
The cost
\(g(n)\) is the cost of the path from the start to cell \(n\). \(h(n)\) is a guess of the cost from \(n\) to the goal, here the straight-line distance. A* always expands the cell with the smallest \(f(n)\).
What to notice
Run the same map with all three algorithms and compare the number of cells explored. Dijkstra spreads out evenly in all directions. Greedy rushes toward the goal and explores very little, but it can return a longer path. A* explores much less than Dijkstra and still finds the shortest path, as long as the guess \(h(n)\) never overestimates the true cost.
Nav2's global planners work on the same idea, using a costmap built from the robot's map instead of a simple grid.