A-Star Algorithm

gap-in-knowledge First heard of it when I got asked what it was and to explain it during my interview with RR for a robotics SWE position.

Refer to: A* Implementation Guide

The A* algorithm is pretty similar to Dijkstra’s Algorithm except that A* adds in a Heuristic Function towards the goal node, thereby focusing on 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^{\prime }$ with step cost $c$, $h(n)\le h(n^{\prime })+c$

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

Related

• D* Lite Algorithm (variant of A*)