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
Your satnav unit has an inbuilt road network. This road network is attributed to contain data such as road speed, lat/longs.
Computationally, the road network is a computer structure called a graph. There are pathfinding algorithms that use various ‘weightings’ based on the road segment attributes. The gps signal is used to determine where in the graph the car is.
Source: ex-satnav developer.
Satnav data usually has two components…. the graphics or drawing coordinates… this is what appears on the screen.
There’s also underlying graph data that just consists of a bunch of nodes and segments…. there are computer science pathfinding algorithms that can find shortest/quickest routes. In some cars, this graph can be updated with live traffic info from SiriusXM or cellular data to improve the algorithm. The GPS signal is just a one-way signal from the satellites.
i am not an expert….but…
the computer in the sat-nav, armed with a lot of data, attempts to create a route from A to B. There are likely an insane number of routes between the two destinations, so the problem is broken down.
Imagine taking your country, and dividing it up into big squares. So now, the path from A->B is relatively easy. But big squares have no detail. So now the squares originally chosen, are sub-divided into littler squares, and the same approach is taken. Repeat until the relevant scale level is reached.
The above doesnt take into account, for example motorway/freeway, that may take a longer route, but be faster in time. So the code in the satnav will try out various shortest and quickest routes.
At the very local level, with lots of roads, intersections and other normal driving scenarios, it will use a different approach, maybe trying out a lot of permutations.
How it does it, appears magic. The earliest satnavs had underpowered CPUs and took forever to compute a route. Modern satnavs have a lot more power and sophistication.
So, yes, it is amazing what they do, but ultimately its a divide-and-conquer approach to breaking down a journey, stitching together the pieces, and checking other items (like traffic delays), to decide an optimal route.
Even a single road is likely to be broken up into multiple sub-segments, e.g. due to curvature of the road.
Not so long ago there were specialist mapping companies who drive around all day “mapping” all the roads, and they sold this database to SatNav makers. The more an area is mapped the easier it is for algorithms to work out possible routes, it’s a fairly simple matrix of options. These companies still exist, but additional data is now available.
Mobile phones share their location with Google and Apple if you let them, and so every minute of every day these phones are adding information to the databases owned by Google and Apple that map out the world. Since they’re reporting in real time, if one route isn’t moving as normal they can suggest alternatives. Based on movement patterns they can fairly accurately work out if you’re walking, using public transport, or driving. Many of the phones will be “local”, people whose own knowledge navigates issues, adding to the crowd sourced knowledge in the SatNav.
One thing I’d add – there is a lot of “guess and test” done to find the right route. With speed limit and distances for each road the navigation system can pretty quickly calculate how long it would take to get from point A to point B following a certain series of roads. So it checks lots of possible combinations to figure out the fastest route.
The SatNav knows where it is at all times. It knows this because it knows where it isn’t. By subtracting where it is from where it isn’t, or where it isn’t from where it is (whichever is greater), it obtains a difference, or deviation. The guidance subsystem uses deviations to generate corrective commands to drive the car from a position where it is to a position where it isn’t, and arriving at a position where it wasn’t, it now is. Consequently, the position where it is, is now the position that it wasn’t, and it follows that the position that it was, is now the position that it isn’t.
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