One of the most fundamental graph search algorithms in computer science is Dijkstra’s, and it is great for many purposes!
In this note, we will go through some other algorithms that are more commonly used in robotics, since we sometimes have more information and we are willing to give up optimality for better runtime.
First, let’s go through the Best-First Search general algorithm, where we will explore new nodes in order of priority.
$pq = [ \ ] \ \textnormal{priority queue, ranked by f(s)}\\ \textnormal{Add start node to pq}\\ \textnormal{While queue not empty:}\\ \textnormal{\ n = pq.pop()}\\ \textnormal{\ if n == goal:}\\ \textnormal{\ \ return path by backtracking}\\ \textnormal{\ else: add children to pq}\\ \textnormal{return fail}\\$
The best f(s) is one that can model the whole cost of the node
⇒ f(s) = g(s) + h(s)
For Dijkstra, f(s) is simply the cost-to-come g(s)
Obviously, it is impossible to know the true cost-to-go. However, we can estimate the cost-to-go h(s) if we have some additional information. We call this h(s) a heuristic estimate
In the robotics motion planning context, this could be the straight line euclidean distance to goal.
More advanced techniques can also involve learned heuristics as well as more complex domain knowledge
If we incorporate this heuristic, and use f(s) = g(s) + h(s), for some heuristic h(s). Then, we call this new best-first search algorithm A* Search.
Graphical comparison between Dijkstra’s and A*
As above, A* explores fewer number of nodes (i.e. faster) than Dijkstra’s. Yet, the path is just as optimal as Dijkstra’s.