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.

Related

• D* Lite Algorithm (variant of A*)