How Does a Car GPS Navigation System Work?

If you’re like most drivers, you probably use a GPS navigation system to get around. Many people even use GPS for familiar routes, just to receive traffic alerts and other warnings. These days, GPS is just something we take for granted. But when you think about it, it’s actually pretty remarkable. As a species, we’ve strapped complicated satellites to giant explosive rockets and blasted them into orbit. Now we use them to find the fastest route to an unfamiliar outlet store. This same GPS technology is also used in other devices, such as GPS trackers. If you’re using any kind of tracking technology, chances are it also uses GPS.

GPS navigation systems also use another advanced technology: route calculation. This is another feature we take for granted, but it’s not as simple as it seems. In fact, modern route calculation is almost as impressive as the underlying GPS technology itself. So, how is all this tied together? We’re about to look at a GPS navigation system from the bottom up. We’ll start with the basic GPS technology that determines location. Then we’ll discuss how your navigation system uses that information to find the fastest route. Let’s get started!

How True Range Multilateration Works

GPS navigation works on a principle called trilateration. True range multilateration is the practice of using four points of reference to find a location. This sounds complicated, but it’s actually pretty intuitive once you think it through. Here’s how it works.

True range multilateration works because an electromagnetic signal can be used to determine the distance between two points. Imagine you’re in New York, and your friend is in Philadelphia, and you’re communicating via radio. That radio signal will take some time to travel between you. The travel time will be about a thousandth of a second, but it’s there. If both of you had super-sensitive clocks, you could use that travel time to calculate the exact distance between you. This principle has been used for years, beginning in World War II.

Now, you might think that finding the distance between two points is useless. And, by itself, for most purposes, it is. But imagine you’re working in British Naval Intelligence in World War II, and you need to find German submarines. If one of your radio towers picks up a signal from a sub, that doesn’t help you much. But if two radio towers pick up the same signal, you know the exact time that each tower received the signal. Using the difference in time, you can calculate that the sub is along an arc between the two towers. Now you’re getting somewhere. If you add a third tower to the equation, you can pinpoint the submarine’s exact location. This process, called triangulation, was hugely successful during the war years.

GPS works the same way, although it requires four satellites instead of three radar towers. This is because it’s trying to fix your location in three dimensions instead of two. It’s also why GPS navigation is referred to as true range multilateration instead of as triangulation. By calculating the distance between your GPS unit and four satellites, your navigator knows your exact location. Publicly-available GPS units are accurate to within about 16 feet under most conditions. That said, accuracy can vary if there are obstructions like trees and bridges. Sometimes, GPS can fail altogether if there are major obstructions like a recessed highway with lots of overpasses. But those are edge cases. Under most circumstances, GPS is a highly-effective navigation tool.

The History of GPS

The first use of satellite navigation was the very first satellite, Sputnik. Scientists tried to track the new satellite, and learned that it could be tracked by shifts in the radio signal. The US Navy quickly jumped on board, and began their own experiments in the 1960s. Using an array of six satellites, observer submarines were able to track a target submarine with ease.

Given the success of this testing, the Department of Defense soon decided to build a complete navigation system. They used the Navy’s model for satellite navigation, and began launching a series of satellites, starting in 1978. At this time, GPS was known as the Navigation System with Timing and Ranging (NAVSTAR). At first, NAVSTAR was limited to military use, but Ronald Reagan opened it for civilian use in the mid-80s. When the satellite array was completed in 1993, it included 27 satellites: 24 primary satellites, and three backups. It was also renamed as the Global Positioning System (GPS), which is a bit easier to remember.

Now, people don’t typically think of the military when they think of GPS. They think of the thousands of civilian uses, from car GPS navigation systems to GPS luggage trackers. However, there are actually two grades of GPS: Standard Positioning Service (SPS), and Precise Positioning Service (PPS). SPS is used on all civilian devices, and is an open standard that anyone in the world can use for free. PPS is a more advanced standard with a higher level of accuracy. Exactly how accurate is still a secret, and probably will be for some time. PPS is encrypted, and access is limited to the US military, US government agencies, and some allied militaries.

With all of that being said, GPS technology is now 42 years old, and it’s starting to show its age. Moreover, other militaries are catching up. The Chinese military has succeeded in creating phantom ships in the South China Sea, using only GPS. GPS signals can also be easily jammed. This has often been the case in conflict zones in the Middle East, at least when state actors are involved.

Because of this, the US military has been looking for a more robust system. Current army research has focused on SpaceX’s Starlink satellite constellation. This constellation currently contains 700 satellites, with over 10,000 more to come over the next decade. They’re designed to provide internet to the entire planet, but they can also double as a location service. Because of the huge number of satellites, the network would be far more reliable. It would also be more accurate, as close as 18 inches for the civilian market. In addition, it would be virtually unjammable for the military. At the time of this writing, GPS still runs on the same 27 NAVSTAR satellites. But don’t be surprised if Starlink satellites come into play in the next few years.

How a GPS Navigator Calculates Your Route

So, we understand how a GPS navigator determines your location. But how does it know the fastest route from point A to point B? And why is the route sometimes different between the same two places?

To perform basic route calculations, a GPS navigator uses a formula called Dijkstra’s Algorithm. This algorithm was developed back in the 1950s by a Dutch computer scientist named Edsger W. Dijkstra. The algorithm is complicated and uses a bunch of calculus, so we won’t dig into the details here. If you’re a math nut, Wikipedia has all the nitty-gritty details.

Basically, Dijkstra’s Algorithm was created to find the shortest path between two points (“nodes”) in a network. The original variant was designed to work with any two nodes. Future variants of the algorithm have been used to find the shortest path between all nodes and one “source” node. These variants are frequently used in computer networking, to maximize router efficiency.

It doesn’t take a lot of imagination to see how Dijkstra’s Algorithm can be applied to roads. Imagine each intersection, driveway, and on ramp as a network node, with the various roads connecting them. Just as you can use Dijkstra’s Algorithm to choose a path through a network, you can use it for roads. This much is easy. Your router performs the same calculations in milliseconds.

However, the shortest geographic distance between two points isn’t always the fastest route. For instance, imagine you were to map the shortest geographic route from Maine to southern California. You’d probably spend much of the time driving on slow state routes and various back roads. It’s technically “shorter,” but it’s no way to drive across the country. A GPS navigation system needs to be smarter than that.

For instance, suppose the user selects the option for the fastest path. In that case, you need to take speed limit into account. You also have to consider stop lights, toll booths, traffic, and a host of other variables. But all of this can be programmed, right? Yes, but there are still more variables to consider. For instance, some roads are jammed during rush hour and fast the rest of the day. Similarly, some roads are extremely busy, but only once in a while, like the roads near a major sports stadium. Because of all these variables, different routes can be more efficient at different times. A good GPS system will take this into account.

In many cases, navigation systems can take into account up-to-the-minute traffic information. The most common example is Google Maps, which uses information from other Google apps. For instance, it uses accident and traffic reports from the Waze app in its calculations. Other navigation systems like Magellan and Garmin use similar traffic and accident information for some units. However, this feature typically requires either a smartphone connection or a dedicated data plan.

Final Verdict

As you can see, there’s a lot of technology behind your car’s GPS navigation system. To begin with, there’s the GPS satellite constellation itself. Using technology from World War II, it allows us to find our location anywhere on planet Earth. The real beauty is that it costs nothing for the average person. Because the satellites are owned and operated by the US military, they’re funded by the US taxpayer. And anyone, anywhere in the world can use them for everyday navigation and tracking.

Similarly, the navigation software itself is pretty impressive. The basic concept of Dijkstra’s Algorithm is well-known, and isn’t a huge innovation in and of itself. But keeping track of all the traffic variables is a headache even under the best of conditions. Modern app integration and wireless connectivity allow GPS systems to calculate your route with up-to-the-minute information. You might not notice all the under-the-hood mechanics, but you’ll notice the shorter drive time.