Remember when you were young and you were too excited to sleep because you were going on vacation the next day? Your parents would wake you up very early the next morning because they wanted to drive all the way to the south of France in one day. Then, sometime during the road trip, your parents would miss an exit and have no idea where to go. Their printed out ‘ANWB routeplanner’ did not tell them what to do in case they made a wrong turn. Nowadays, most people do not have this stress anymore, since most of us now make use of a TomTom or Google Maps. But how do these services know exactly where we are and where we need to go? The answer involves a lot of mathematics that will be explained in this article.
The GPS
Before we can say anything about the route to our destination, the service we use, whether it is a TomTom, Google Maps, or another navigation system, first needs to know the location of our vehicle. This location is determined using a Global Positioning System, better known as a GPS. The GPS is a worldwide radio-navigation system formed from a constellation of twenty-four satellites, each in its own orbit 11,000 nautical miles above the Earth, and five ground stations that make sure the satellites are working properly. The satellites each take twelve hours to orbit the Earth. The GPS receiver receives and interprets radio waves emitted by at least 4 Satellites.
3-Dimensional Trilateration
The GPS works based on a simple Mathematical Process named 3-dimensional Trilateration. That works like this. The GPS receiver receives a signal from some first satellite. Let’s say it measures your distance from the satellite to be 20,000 km away. This means that the receiver could be at any point in any direction on the surface of the green sphere with a radius of 20 000 km. Now, the receiver captures a signal from a second satellite. From this satellite, our GPS unit measures your distance to the satellite to be 17,000 km away. Now, you are localized to be on the intersection of the spheres of the satellites. We notice that the two spheres overlap to form a perfect circle. The receiver could be anywhere on that circle. Then, the receiver captures radio waves from a third satellite. We can see that the three spheres overlap at two points, which gives us two possible locations of the GPS receiver. Then, to determine the exact location, a fourth signal is received from a fourth satellite. This location corresponds to the only point of overlap of the four spheres.
Below, we show another way to see that the observations from four satellites can give the exact location of the GPS receiver. Notice that nowadays most GPS units use as many as six satellites, which can only improve the accuracy using least squares methods.
The Mathematics
So, how is this distance from a satellite to a receiver then calculated? We can determine the distance if we know the transit time and the speed of propagation of a signal. The GPS receiver clock is not perfectly synchronized with the satellite’s clock, due to the high speed of the satellite. So, we must determine the time offset between the clocks to accurately measure the distances. Now, we assume that we have the distance from four satellites and we know $(x_i, y_i, z_i)$, $i = 1,2,3,4$, which are the exact locations of the satellites. We must solve the following system of equations.
$$\sqrt{(x – x_1)^2 + (y – y_1)^2 + (z – z_1)^2} + ct_B = d_1$$
$$\sqrt{(x – x_2)^2 + (y – y_2)^2 + (z – z_2)^2} + ct_B = d_2$$
$$\sqrt{(x – x_3)^2 + (y – y_3)^2 + (z – z_3)^2} + ct_B = d_3$$
$$\sqrt{(x – x_4)^2 + (y – y_4)^2 + (z – z_4)^2} + ct_B = d_4,$$
where $c$ is the speed of light and $t_B$ is the receiver clock offset time (which is the difference between GPS time and internal receiver time). As there is just one clock offset time, this means that all the satellites must have perfectly synchronized clocks. That is one of the tasks of the control sites.
The system with unknowns $x, y, z$ and $t_B$ is solved by our GPS receiver. How is this solved then? We know it is multivariate and nonlinear. We know that numerous methods can solve this system. The most famous one is Newton’s method. Here, the general multivariate case of Newton’s method is used. It works like this. Let $\mathbf{f}(\mathbf{X}) = \mathbf{0}$ be the system to be solved, where $\mathbf{f}$ and $\mathbf{X}$ are column vectors $\mathbf{X} = (x_1, \dots, x_n)$ and $\mathbf{f} = (f_1, \dots, f_n)$. Each function $f_i(\mathbf{X})$ is a function of each of these $n$ variables. We define the $n \times n$ Jacobian matrix
$$J_\mathbf{f}(\mathbf{X}) = \frac{\partial f_i}{\partial x_j}, \quad 1 \leq i, j \leq n$$.
If $\mathbf{X}_0}$ is some starting vector, then the Newton iterations are
$$\mathbf{X}_{n+1} = \mathbf{X}_n – J_\mathbf{f}^{-1}(\mathbf{X})\mathbf{f}(\mathbf{X}),$$
where $J_\mathbf{f}^{-1}(\mathbf{X})$ is the inverse of $J_\mathbf{f}(\mathbf{X})$.
We do have to notice that there are many sources of error in GPS measurement. Examples are the atmosphere, ionosphere, satellite orbit errors, receiver noise, multipath ambiguities, and satellite clock errors.
The route
So, now we have the location of our GPS receiver. Then how is the route that we have to take determined? The services use a map which includes all roads of the world, along with their coördinates and lengths. The software knows the speed limit of each road, but they also take the traffic into account, which is determined by how fast other users drove at certain roads and at which moment of the day they did that.
This data is collected in a graph. This includes not only cities and crossings, but also houses and how they are connected using roads. A weight to each edge is given with information about time and distance.
When you choose a new destination, you can choose the shortest or the fastest route. The software then determines which route measures up to that. For this, the algorithm of Dijkstra is used by the service, which gives us the route which has the lowest weight in terms of time or distance.
Now, we can see that there is a lot of mathematics hidden behind the simple TomTom we use in the car. The small device calculates every step on your way to bring you to your destination, so you don’t have to take your printed out ‘ANWB routeplanner’ with you on vacation. So, next time you’re in the car, you can thank your device for doing all the mathematics for you.
This article was written by Deirdre Westenbrink
