GPS, you've gone too far this time People writing GPS software need to re-think their approach to measuring distance, because the system has a built-in bias to over-estimate how far you've moved. That's the conclusion of a group led by geo-boffin Peter Ranacher of the University of Salzburg, in a paper published in the International Journal of Geographical …
The whole point of this story is that the errors don't "average out", because it's a systemic bias. The distance will always be measured as longer than it actually is.
It's easy to see why:
- Draw a straight line between two points
- Select 4 points, equally spaced, along that line
- Now, apply a random error - a small displacement in a random direction - to each of those 4 points, and draw a new line linking the ends of the line via the 4 displaced points.
No matter how small the random error is, the net effect is to create a path that's longer than the straight line.
And the same applies if you start with a non-straight line. It would be a one-in-a-million level coincidence for the random errors to produce a path that was shorter than the one actually traversed.
But how many journeys are absolutely straight lines? Most are winding paths and you might expect perturbations to the true position of the intermediate measurement points to be as likely to be on the inside of a local bend as on the outside which would underestimate the true distance travelled balancing out the overestimates from being on the outside of the local bend. I suspect the explanation given is more complicated than that.
The best way to picture this problem is a drunk man walking home from the pub. Is he walking in a straight line? Is he sticking to the middle of the path?
The answer is no in both cases. He is in fact constantly zig-zagging across the path. If for every metre his sober companion has walked the drunk has crossed the path once, it means he's actually walked 1.12 meters (Pythagoras and assuming a path 0.5 metres wide))
This would hold true for curved as well as straight paths, the drunk always walks further than his sober friend
Thanks for that useful explanation. I can see that it is certainly true if the path has high walls either side, but what about a wiggly footpath across an open field? Isn't it possible that the drunk will actually take a shortcut in these circumstances?
But then, with the 10 metre box described in the article, I'm pretty sure that time intervals between samples would sometimes cause the corners to appear to have been cut, and the overestimate still appears.
My other concern is whether this applies where maps are used --- an earlier reg article 'tested' GPS units against each other and tried to compare their accuracy. I was surprised how close they were to each other, and wonder if that is caused by snapping the route to a path on the map?
The drunk can't take a shortcut in this metaphor, because he is bound to his sober friend. The sober friend is the true position of the walker, and the drunk is true position +/- some error. So in a working GPS drunk is always close to sober within the error margins (the high walls on the path.)
In the 10 metre box example, cutting the corner won't decrease the overall length measured as the next measurement is just as likely to be outside the box which increases the distance the error covers. For any path - square, circle or winding lane - the error has a 50/50 chance of being on one side or the other, which is what causes the zigzagging that increases perceived distance.
"This would hold true for curved as well as straight paths, the drunk always walks further than his sober friend."
In other words, the sober one walks a shorter path, so to speak. This is why someone I know (you can't choose family) insists on never changing the lane on the motorway. Because it's shorter. The frustrating thing is that it's mathematically correct!
It may me geographically shorter, but it may also be temporallly longer due to traffic or an accident. If people change lanes frequently, it's usually because the lane is backed up and moving slowly, so going around may requiring traveling further in terms of length but also allows traveling at a higher speed, offsetting the loss.
> In other words, the sober one walks a shorter path, so to speak. This is why someone I know (you can't choose family) insists on never changing the lane on the motorway. Because it's shorter. The frustrating thing is that it's mathematically correct!
Eh? Changing lane frequently to be on the inner radius of any curve would always be shorter.
"This is why someone I know (you can't choose family) insists on never changing the lane on the motorway."
Presumably this means he sticks to the left hand one, as he can't change from that to the others.
Didn't think so. Hopefully he'll get a ticket sooner or later.
The way I have thought of it: assume that the error is represented by a circle around the actual position (with the size of the circle being equivalent to the noise introduced by the error). Draw an arc centred on the previous location and passing through this circle's centre; that is, the radius of the arc is the true distance between the two points.
The area of the circle of confusion which is inside the arc, on the side of the previous point, is always going to be smaller than the other side; if the error is evenly distributed radially, then there is a small but significant chance of the error falling to the 'large' sector rather than the 'small' (and very little chance of it falling actually on the accurate arc itself).
Which suggests rather counter-intuitively that the best way to measure distance is to take distant samples rather than closer ones, though that would of course ignore any waypoints off the straight and narrow.
Actually, no. If you think about it, a "random variation" is more likely to be on the outside of any given bend than on the inside (because the outside, by definition, occupies more than 180 degrees of the circle around that point).
But the principle is the same anyway, no matter how much you wind. Take any path and add random perturbations to it, and it gets longer, not shorter. That's the principle behind fractals. The only way to make it shorter would be to remove perturbations, and the odds of achieving that by random adjustment are infinitesimal - like improving an audio signal by adding white noise.
People generally don't walk in perfectly straight lines. Roads and paths are rarely perfectly straight lines. GPS measure in straight lines because they sample at discrete intervals, instead of constantly, so they are always going to under-estimate. Is this not more significant? Unless the sample rate is equal or less to the interval of one of my steps, it is always going to under estimate my path length.
Say I'm walking a path that curves back on itself. If my GPS samples at the start of the curve, and then at the end of the curve, it will calculate that I have walked far less than I actually have.
Think of it as the difference between digital at a low sample rate, and analog.
Ask the US military - they clearly explain that GPS has a built-in error for civilian GPS units. For accuracy you need US mil-spec units, like those found on cruise missiles.
That's why Europe launched Galileo and the Ruskies their own one as well. Proper accuracy. It's a pity all those glorified sweat bands are US spec and therefore unreliable.
"Ask the US military - they clearly explain that GPS has a built-in error for civilian GPS units"
You're talking about Selective Availability where the pseudoranges are stretched to "move" positions. That was turned off over 10 years ago. That can be easily eliminated with any correction source such as WAAS.
Having worked with GPS receivers (including code therein) I can assure you you have the wrong end of the stick.
This extra distance is caused by the accumulation of random movement, since that tends to add distance rather than remove it.
The suggestion they gave is to integrate from velocity. That's a fair way yo do things.
Different GPS receivers from different vendors use very different calculations (especially in filtering) to measure position and distance. The cheapie receivers in cellphones etc are particularly poor.
Top end receivers (commercial - not military) can get positions as good as 20millimetres.
"That was turned off over 10 years ago"
That was turned off in Gulf War I because there wasn't enough military GPS kit to go round and some vehicles had to rely on civilian kit.......to those who knew it was one of the first indications that the allied attacks on Iraq were imminent
"to those who knew it was one of the first indications that the allied attacks on Iraq were imminent"
That, and for GW2, the entire constellation being switched off for a few hours. It wasn't convenient for a friend of mine using it to navigate over water between New Zealand and the Chatham Islands as it meant a hurried midflight transition to pencil and paper.
The Pacific Ocean is awfully large and the islands are very small. Not a good situation in an unpressurised light twin when you're not expecting that and you're well beyond radar coverage.
Can @CM explain the build up of random movement comment a bit more...
I'm not CM, but...
The shortest distance between two points is a straight line. If you divide that straight line into, say, 10 segments, and the end points for each segment as calculated by GPS are slightly off from the actual position, the resulting join-the-dots path will be a zigzag. That is always going to be longer than the simple straight line distance between the start and final endpoints.
'The shortest distance between two points is a straight line.'
You have to remember that we live on a giant ball, the shortest distance on the surface of a sphere is a great circle.
The sober one will walk a straight line which is a longer distance, the drunk will stagger with a bias towards the downhill, the drunk on average walks closer to the great circle and so covers less distance (as long as you don't count the backwards lurches)
Having also worked on GPS systems (including I think some of the receivers Charles worked on) and now working for a company that bases it's core business on giving accurate distance measurements from GPS I'd add that this is hardly original or shocking news.
Our products don't look at the difference in location, we integrate velocity to give distance and have been doing so for years. As long as you don't have high accelerations it's trivial and works really well on any receiver. With heavy acceleration you have to start worrying about which receiver you are using.
It's quite shocking news to those of us who thought GPS was (only) a positioning system. Taking a (numerical) derivative and (numerically) integrating it to arrive at a more accurate measurement than the original data would be quite bizarre.
Presumably the explanation lies in the Doppler measurements. These are an additional source of raw data and so it is much less surprising to be told that they can be used to improve the accuracy of the positional ones. Is that it?
"Presumably the explanation lies in the Doppler measurements. These are an additional source of raw data and so it is much less surprising to be told that they can be used to improve the accuracy of the positional ones. Is that it?"
Correct.
A GPS receiver measures the frequency of the signals from the satellites. This will be offset from the theoretical frequency by the doppler caused by the relative velocities of the satellite and the receiver.
After subtracting the satellites orbital motion and the earths rotation you are left with the effect of the receivers motion.
This allows you to calculate velocity in a method that is completely independent of the position calculation (well ok you need to know your location to subtract the earths motion but a 100m error in that doesn't have much impact).
For short term relative motion integrating this velocity is more accurate than position delta. It's not much use for long term position, as with any integral of a noisy value it will drift over time. And it's useless for absolute position.
Question for Charles Manning
My wife and her running colleagues are always complaining that their GPS watches (different brands) invariably under record the distance run in a measured event. Typically a 10km run would be shown as 9.9km or thereabouts. They get particularly annoyed when a Marathon (42.195km) is 'short', as many of statistics tracking sites they use won't recognise it as a Marathon.
I assumed this was because the sampling points were straightening out curves but you seem to say this may not be the case.
So what would cause the short recording of their runs?
"My GPS watch suffers from the same problem and I put it down to cutting the corners. "
Given the other comments about acceleration and some chipsets not being wonderful, the fact that it's swinging around on the end of your arm probably has a lot to do with the inaccuracy.
As a crosstest, putting it in a pocket or pinning to the shirt would be a first step.
"You're getting confused with something called Selective Availability which was switched off years ago."
Er I think you will find that you are wrong. While Selective Availability is turned off, without access to US military specification GPS units you won't have access to the encrypted P code stream only the C/A code for civilian operation. This is something completely different to Selective Availability and gives the military specification units higher precision than civilian units can achieve without the use of an accuracy enhancement system such as DGPS.
"they clearly explain that GPS has a built-in error for civilian GPS units."
Selective availability was disabled over 15 years ago. The newer birds don't even have the ability to enable it. http://www.gps.gov/systems/gps/modernization/sa/faq/
There's still an error there but this is down to the lower resolution of the civilian signal vs the military one and that's down to the bitrate.
This post has been deleted by its author
Just from running a bit, back in the days, I came to the same conclusions and it didn't take a lot of thinking to figure out that it was due to jumpy GPS coordinates. Indeed, you could collect some distance just by standing around.
But it's good to see that the people over at the Geographical Information Science club get their moment of enlightenment.
Anyone who uses GPS tracking a lot will know the situation.
Sometimes it overestimates and sometimes it underestimates (in real life, not in the fake conditions these guys set up).
GPS traces often show corners being cut because position is only recorded every few seconds and distance recorded based on straight-lines between those points.
At other times you get a weak fix and find that you've been weaving all over the road (and adjacent fields, rivers etc) thus appearing to be further than you really travelled.
Heck, I've even hit 18,500mph while cycling - apparently!
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
