How your sat-nav works out the best route

Sat navs are a fascinating offshoot of both the US military's desire to equip its units with the facility to find out their position and the ability to display maps on a computer screen.

But though the devices are extremely popular, the algorithms that they use in order to provide the shortest distance route to your destination are less well known.

There are two major algorithms that come into play with sat-navs. The first is perhaps the simplest: the ability of the unit to use the GPS (global positioning system) satellites to work out where in the world the unit is situated.

The second is rather more complicated: the ability of the sat-nav to determine the shortest distance from point A – where you are – to point B – where you'd like to be. There are other algorithms in play, mostly dealing with the visual display of the route to take, but these two algorithms are the most important.

The GPS satellite network started out as a US Air Force system to help determine the position of any receiver to an accuracy of 15 metres. Following the downing of the civilian KAL 007 airliner after it drifted into Soviet restricted airspace, Ronald Reagan promised to make the system available for civilian use once it became operational.

This happened in late 1993, and the unencrypted civilian signal was deliberately downgraded so that GPS units would only be accurate to about 100m. This limitation (known as Selective Availability) was removed in 2000.

The positioning algorithm is fairly simple. Currently there are 30 satellites spread out in medium Earth orbit, each transmitting the same information. The messages consist of three main pieces of data: the exact time the message was transmitted, precise orbital data for the satellite (known as the ephemeris) and the overall system health.

The GPS unit listens for these messages and interprets them. From the time of the message, the GPS unit can work out how long the message took to reach the unit, and, from that and the known speed of light, how far away the satellite is. From the ephemeris data, the unit can work out the direction to the satellite.

Calculating the position

Using just the messages from one satellite, the GPS unit is going to be somewhere on the surface of a virtual sphere centred on that satellite. That's fairly interesting to know, but not very helpful.

So the GPS unit listens for messages from other satellites. Using the messages from two satellites, the GPS unit can work out its position to be somewhere on the circle that forms the intersection of the two spheres centred on each satellite.

If you think about it geometrically, either the spheres don't intersect at all, or they intersect at just one point (the spheres just manage to 'touch'), or, in the more general case, they intersect as a circle. Think of soap bubbles joined together. Interesting to know, but again pretty useless.

Using three satellites, the GPS can calculate its position to be at one of two points on that circle from the previous case. Again, thinking geometrically, the intersection between a sphere and a circle is going to be either non-existent, a single point or two points.

So GPS units use the messages from at least four different satellites to resolve their location to a single point. GPS satellites are positioned in orbit so that from any point of Earth about 10 satellites will always be 'visible' in the sky, an ample number from which to calculate the position of a GPS receiver. The position of the receiver, using just the GPS satellites, is calculated to within about 15m.

The reason for the comparatively large error is due to many factors, including the atmosphere (light travels slightly slower in air than in the vacuum of space), any errors in the clocks involved, bouncing of the GPS signals off buildings and so on. Yet, as we all know, a GPS unit seems to be way more accurate than that.

The reason is that terrestrial sat-navs do not rely exclusively on GPS satellite signals: they also make use of other signals such as those from mobile phone towers and the like to refine their location to within a few metres.

If the GPS receiver is in a car and forms part of a sat-nav system, the unit will also make use of further information from the car itself, such as speed, distance travelled, acceleration and so on. This helps in urban environments where the GPS signal can be blocked by bridges, or by being in a tunnel, or messed up by being reflected off buildings and the like.

Of course, a further refinement is that, usually, the car is on a road, and so the sat-nav can 'fix' the location of the car to a road on its internal map.