How does my GPS work?

I use her often, but sometimes neglect her for long periods of time. I take her for granted, just assuming that she will be there and that she will perform the services that I need. When I ask her to do something, she pretty much always tells me where to go. And like any guy, I will get angry with her when she refuses to perform.

This could apply equally well to pretty much anything female in my life, but today I am referring to my GPS. Just in case you are wondering why I used the feminine pronoun, I have my GPS set to a female voice because I have become accustomed to doing what a woman tells me to.

As I was watching a squirrel navigate itself around through the trees today, I found myself pondering how a GPS works.

Starting out with a level playing field

Let's say that there is a football game going on, and they have to postpone the game. It's raining out, so they need to take the ball off the field. When the game resumes, they will need to put the ball back exactly where it was. That's when the MathPhone rings. "Hey Math Guy! We have a tape measure, and we can use the two goalposts to fix the position of the ball. How do we do it?" 

Now, I haven't watched all that much football, but I do seem to recall that there are a bunch of lines on the field that might be used to determine position. But let's say that I am either not allowed to use the yard lines or that somehow it never occurred to me that I could use them to describe where the ball is. I dunno. Maybe it doesn't make sense to use them because I need to make sure the ball is repositioned down to a zillionth of an inch. 

So, I take out my tape measure and measure from one goalpost to the ball, and then from the other goal post to the ball. I am thinking: "The football field is a two dimensional grid, so I should be able to nail down its position with two numbers, right?" 

Not quite. The red arc in the diagram below shows all the points that are 140' 7" from the left goalpost. The yellow arc shows all the points that are 253' 6" from the left goalpost. Note from the drawing that there are two points that satisfy both conditions. There are two locations that the ball could be. That's not gonna work!

So, I get out my post hole digger and buy a bag of cement to sink a third goalpost at the 50 yard line. It's not like anyone in the Green Bay area is ever gonna get that far down the field, right? When I make this third measurement, I get 156' 4". From the diagram below, it's clear that I can distinguish between the upper and the lower locations. The blue arc goes nowhere near the lower location. It's clearly in the upper position.

Aside from the possibility that my measurements are wrong, I think I'm home free. Measurements from three goalposts are enough to plant the ball exactly where it was. 

Being overly determined

But as is the case in most of my blog posts, things might not be quite that simple. If I were a pure mathematician with my nose firmly embedded in my well work copy of Euclid's The Elements, I would be done. I would accept my exorbitant consulting fees and head out for a beer. If my clients were desperate enough, I might even have enough for two beers.

But as an applied math guy, I realize that as certain as the uncertainty principle, there are tiny errors in any measurement. I am not talking about out and out mistakes. I mean, that there will be a variation from one measurement to the next. One would be tempted to think that if I were counting discrete things, the variation would be zero, but this is not the case, especially when counted little tiny things like photons and electrons. But that's an idea for a different blog post.

Given that there is some error, we will almost certainly run into a situation like in the diagram below. Any pair of the circles define a point, but the three points are not in the same place. 

What we have is an over-determined system: too many constraints, potentially leading to no solution. Originally we had an under-determined system: not enough constraints potentially leading to too many solutions.

How to deal with this? One way would be to just take the intersection of the two most reliable measurements. In our case, the goalpost at the 50 yard line is likely less accurate, since it may shift as the cement cures. 

Another way would be to take the simple average of the three intersection points. This will tend toward being more accurate than the intersection between any two. Just as a rough measure, the error will be reduced by the square root of the number of observations. (There are caveats and assumptions here. Like, the errors must not be correlated.)

A third way - and this is what an applied mathematician would recommend - is to do least squares optimization. That might come up in another blog post.

Leaving the plane

I mentioned that a squirrel inspired this post. How did I make that leap?

I was watching the squirrel make multiple leaps and musing about the relative difficulty of his navigational task compared to mine. My navigational task is basically decide if I should go left, right, forward or backward. Birds, bats, fish, porpoises, new world monkey, and squirrels all have the additional need to navigate up and down. I was musing about how much of the little critter's brain must be devoted to that task. 

Or maybe it's not all that much difficult. I dunno. It still got me thinking about navigation and three dimensions. And that's one of the things missing in the football field problem. When I had the task of defining the position of the ball on the field, I was constrained by the ball being on a level playing field. What is this is not the case?  What if I am required to fix the location of the ball if it is some distance above the field?

Now we have to go to three dimensions. I need to make sure, of course, that I am starting my measurement from a fixed point in space. So, let's just assume that I am allowed to drill a hole into the side of the goalposts to attach a screw hooks.

If I attach my tape measure to the screw hook, and stretch it out to 140' 7" or whatever, then I am free to move the end in any position along the surface of a sphere, for example, any position on the bluish-purplish sphere below. Similarly, a tape measure set to 253' 4" from the other goal post would describe the surface of the red sphere.

The intersection of the surface of these two spheres represents all the locations that the ball could be if I have only measured from two goalposts. As you can see from the absolutely breathtaking drawing that I made, the two intersect in a circle. (Of course, the intersection could be a point, or there could be no intersection at all. I am just looking at the one case. If the measurements are accurate, then there really should be an intersection.)

For the kinetic learners, imaging connecting the ends of those two tape measures. With both tapes fully stretched out, the ends are free to swing around in a circle.

So, as in the case of the plane of the football field, we have an under-determined system. In three dimensions, measurements from two goalposts allow us to narrow down the ball's position to a circle, rather than two points.

Now it starts to boggle my brain. What happens when we add a third goalpost?  Bear in mind that the intersection of the first two spheres was a circle. The intersection of the first and third must also be a second circle. And finally, the intersection between the second and third must be a third circle.

In other words, the collection of points that are the correct distance from all three goalposts is the intersection between these three circles, as below. If all goes well, then the intersection is two points. Funny. We had the same thing happen with two circles when we were working on the surface of the football field. So, if we need to fix the location of our football in three dimensional space, then we need four fixed points to measure from.

Where is the GPS tape measure?

I think many of my readers may have guessed by now that the goalposts are an analogy for the GPS satellites. Currently there are 31 operational, but the system could run with as few as 24. With 24, then no matter where you are on Earth, there are always four satellites to use as goalposts. (Isn't that funny? That is exactly the number I came up with!) I won't go into details about the orbits, but I found a website that does a good job of explaining the GPS satellites' orbits. 

I do want to address one question, though. Where is the tape measure connected to my GPS? The GPS works pretty much like that crazy gal I dated before I met my wife. The GPS is constantly sending out a little message that says what time it is up in GPS-ville. 

The GPS receives these messages and compares against its own time. The difference in time is the time it takes the time-stamp message to travel from the satellite to my GPS. In this example, there is a delay of about 17.8 milliseconds. Since light travels at about 300,000 km/second, this particular GPS satellite must be about 5,340 km away.