A-Star Algorithm

• A* Implementation Guide

The A* algorithm is similar to Djikstra’s algorithm except that A* adds in a Heurisitic Function towards the goal node, thereby focusing the search.

For A* search to be optimal, the heuristic function $h(n)$, should be:

1. Admissible, or never overestimating the true cost, and
2. Consistent, which means that the estimated path cost to the goal of a new node in addition to the cost of transitioning to it from the previous node is greater or equal to the estimated path cost to the goal of the previous node. To put it in an equation form, $h(n)$ is consistent if for every node $n$ and successor node $n’$ with step cost $c$, $h(n)\le h(n’)+c$.

A typically used heuristic is Euclidean Distance from the current node to the goal node.

Why ever use A* then?

Imagine when the search tree is huge. A* reduces the number of tree nodes required to be visited. Although I would argue maybe explore using MCTS in that case.

Related

• D* Lite Algorithm (variant of A*)