I’m keen to understand how a SatNav works out how to get me from A to B.
I understand at a basic level how it receives a number of GPS signals so can work out where it is. I’d like to know what it then does to navigate me through all the different road systems to get me to my destination.
In: Technology
The navigation algorithm has access to the database of all road segments with all turn restrictions and speed limits. It runs a shortest path finding algorithm based on [the Dijkstra’s algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). “Shortest” does not necessarily mean shortest distance, it can also find shortest time-wise (aka fastest) route. The algorithm is exactly the same.
The original Dijkstra’s algorithm is not suitable for medium and long range route finding. It would bog down finding 30+ miles route in a city of 10 million people because too many road segments needs to be considered. Instead a hierarchical modification of the algorithm is used. All road segments are classified to be 0,1,2,etc. levels. Level 0 road segments are considered for short routes. Level 1 roads are considered for longer routes. Level 2 roads are considered for even longer routes and so on. Freeways are the top level roads considered for the longest routes. Each next level is significantly (3-30 times) smaller than the previous level.
The algorithm first runs the original Dijkstra’s algorithm on all level 0 roads around the source and destination points. Then at some point either based on heuristics or on calculated parameters it stops considering the level 0 road segments and starts going only though level 1 segments. Since the number of road segments in each level is getting smaller the algorithm runs exponentially fastest than the original Dijkstra’s algorithm.
Latest Answers