# 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 …

1. #### How far off?

According to the odometer on the GPS, I've cycled 4085km this year, or a little shy of 20000km since I started recording back in early 2012.

I would have expected the errors to have averaged out over that great a distance.

1. #### Re: How far off?

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.

1. #### Re: How far off?

But... but... one in a million chances come up nine times out of ten!

1. #### Re: How far off?

True - but only because there are so many one in a million chances.

If only we could tell WHICH one a in a million chance was likely to come up...

2. #### Re: How far off?

According to Terry Pratchett, the 1-in-a-million chance ALWAYS comes up, but only if the odds are exactly a million to 1.

1. #### Re: How far off?

And still they come.

2. #### Re: How far off?

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.

1. #### Re: How far off?

You've obviously have not lived in the Netherlands ;)

2. #### Re: How far off? @Gomez Adams

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

1. #### Re: How far off? @Gomez Adams

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?

1. #### Re: How far off? @Gomez Adams

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.

1. #### Re: How far off? @Gomez Adams

The logical conclusion is that the drunk is faster than his sober friend... I'll be down the pub training for a 10k run so!

2. #### Re: How far off? @Gomez Adams

"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!

1. #### Re: How far off? @Gomez Adams

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.

2. #### Re: How far off? @Gomez Adams

> 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.

3. #### Re: How far off? @Gomez Adams

"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.

3. #### Re: How far off? @Gomez Adams

"the drunk always walks further than his sober friend"

I shall test that hypothesis tonight. I just need to find a sober friend.

1. #### Re: How far off? @Gomez Adams

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.

3. #### Re: How far off? @Gomez

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.

3. #### Re: How far off?

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.

2. 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.

1. #### Re: didn't they disable that 'feature'

It's not a bug it's a feature.

http://www.gps.gov/systems/gps/modernization/sa/faq/

Disabled in 2000.

2. #### It isn't that

"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.

1. #### Re: It isn't that

"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

1. #### Re: It isn't that

"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.

2. #### Re: It isn't that

Can @CM explain the build up of random movement comment a bit more...

1. #### Re: It isn't that

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.

1. #### Re: It isn't that...it's something else !

'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)

3. #### Re: It isn't that

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.

1. #### Re: It isn't that

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?

1. #### Re: It isn't that

"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.

2. #### Re: It isn't that

> I'd add that this is hardly original or shocking news.

Yup. Just one of those "Research Shows That ..." sort of headlines.

[ Having worked on GPS receivers me three ]

4. #### Re: It isn't that

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?

1. #### Re: It isn't that

My GPS watch suffers from the same problem and I put it down to cutting the corners. It probably doesn't sample sufficiently frequently. This may outweigh the problem described in the article.

1. #### Re: It isn't that

"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.

5. #### @Charles Manning

OK, I've glanced at the linked paper and the bit I'd really like to know I can't decipher:

What sort of ballpark for errors are we talking about here?

3. GPS has a built-in error for civilian GPS

Not a built-in error, a built-in lack of precision, which isn't the same thing and would have little or no impact on the problem described here.

4. "For accuracy you need US mil-spec units, like those found on cruise missiles."

Wrong...

You're getting confused with something called Selective Availability which was switched off years ago.

1. "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.

1. Er... wrong.

I think you need to have a re-read....

The encrypted P code is used to avoid 3rd parties sending out false GPS signals (imagine that...) The encrypted (non-SA) GPS signal is now so accurate as to make DGPS irrelevant.

5. "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.

3. I guess this means I'll have to change the targeting calculations for my drone? Use "real" position instead of waypoints maybe. Then again, this is civilian GPS which has built in errors.

4. #### "at high sampling rates "

5. This post has been deleted by its author

6. #### Is this a surprise?

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.

7. Any estimates of the percentage error for a representative unit?

1. That's going to vary depending on the number of 'visible' satellites and their location, weather conditions, and day/night.

In poor weather at night my old handheld Garmin will give me 20ft EPE whereas my phone won't even lock on to a signal.

8. 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!

1. > (in real life, not in the fake conditions these guys set up).

The article described walking a perimeter and being driven in a car - both of these are real-life applications.

2. #### Heck, I've even hit 18,500mph while cycling - apparently!

Hope you were wearing some sort of ablative cycling suit...

9. #### I've read the article but ....

I can't see where they give an estimate of the % error except that it appears to decrease the further you travel.

Personally, from using a GPS in a car and a motorcyle to record the distance I've gone, it matches pretty well to my car/bike mileometer over distances of over 100 miles. So, I think the errors do cancel themselves out (the overestimation of GPS vs the cutting of corners due to the sampling rate).

Does that make sense?

Alan

1. #### Re: I've read the article but ....

On short distances it seems fine when I use my tablet or fone for GPS. However my longest journeys have been 1700+ miles and on those the distances recorded by those devices have been significantly greater than my odometer showed or the original route plan suggested.

10. #### No surprise...

...to those of us who use GPS velocity measurements instead of position when blending & fusing them with inertial measurements for precise navigation - it gives a much more accurate result.

11. #### Overcharging?

I guess this is another stick with which black cab drivers can beat Uber.

1. #### Re: Overcharging?

What I'd give for HTML sarcasm tags...

2. #### Re: Overcharging?

Not really as in my experience, cockney black cabs don't seem travel more than a few miles out of their safe zone..

Cab in Birmingham, 60 mile round trip, no problem; try to cross a bridge in London, end of the world.

12. #### hangon ....?

So how does the app in my phone(s) do it quite well?

I use Endomondo and in conjunction with the mile markers on the road (every 0.25 miles), I get reasonable agreement.

Perhaps this is not as unknown as the article presents?

Anyone else use a run tracker notice this effect?

P.

13. #### Uber?

Does this mean the Uber charging mechanism has been overcharging if GPS has been overegging the distance?

Class action anyone?

14. #### How big is the error?

Is this anything worth bothering about? It says the distance is overestimated, but by how much?

If it's 10% then lots of people need to worry. If it's 0.01% then nearly everybody can ignore it.

1. #### Re: How big is the error?

By how much will depend on your actual velocity. Say GPS is 95% accurate to 2m (I'm generalising, but it will do), so for point to point distances at 1Hz when travelling at 100mph, that's not much.

However, sit still for a bit and see how often your GPS records 0.1kt. You've travelled a zero distance, but the GPS reports a non zero distance. As a percentage, that's infinite. Which is presumably why TFA referenced errors during walking.

2. #### Re: How big is the error?

You're right, a distinct shortcoming in the original article. Reg, can you fill in that info, rather than having us all come with our own math on it?

15. #### Walking the dog

I run and have used a variety of Garmin GPS watches over the years. Some have "smart recording" and some allow you to select a 1 second recording interval. I was told that typical accuracy for a wrist worn GPS unit was at best +/- 5 Metres from your true position, and that you should visualised going for a walk with a hyperactive dog on a 5 metre lead. While you are following the path the dog is dashing hither and thither around your location.

The software algorithms try to make sense of this erratic track and generally make a good job of it.

1. #### Re: Walking the dog

This is one of the odd situations where a high update rate makes things worse.

Let's assume the average off-path GPS error is 1m (with a random error of up to 5m the average error is 2.5m. We don't care average the error in the direction of travel, that will cancel out, so the error that matters will be 2.5/sqrt(2) or about 1.7m, these are wild hand waving numbers so call it 1m to keep things simple).

The errors will be on every point so the total error between two points could be double that. But the errors could also cancel out so stick to 1m for the off axis error between any two points..

It I walk 60 at 2m/s (about 4.5mph) and update at 1Hz then each second I travel 2m and have an error 1m, that gives my total GPS distance as sqtr(2*2 + 1*1)*30 = 67m or an error of 7m.

If my the GPS updates every 30 seconds I get an error of sqrt(60*60 + 1*1) = 60.008m, an error of 8mm.

This is assuming a straight line, if there was a corner then the GPS positions would cut the corner, the lower the rate the more they would shorten the path.

There is probably some rate of turn dependent ideal sample rate where the position noise cancels out the corner cutting effect.

This is all assuming stupid software, the software could realize that a given set of points are within the noise level of being a straight line and treat it as such. You could even round out corners and do a reasonable job of inserting the bits that got cut.

1. #### Re: Walking the dog

I forgot to add - this is all assuming GPS errors are random.

They aren't.

If you leave the receiver stationary the average difference in position 1 second to the next is far smaller than the average difference 1 hour to the next. A lot of the errors are caused by atmospheric effects and they don't change rapidly.

However if you are moving and a tree or building blocks the line of sight to an SV then you can get a big instantaneous position jump. These are fairly obvious to detect because the position may say you just traveled 10m in a second but the reported velocity won't have a corresponding jump. Unfortunately detecting them doesn't tell you which of the two positions was correct.

2. #### Re: Walking the dog

"This is one of the odd situations where a high update rate makes things worse."

That depends if you use the high rate directly or integrate the results first.

16. #### ok, I get what people are saying...

BUT does it actually make any difference in the "real world" when I navigate from my house to A.N.Other place?

1. #### Re: ok, I get what people are saying...

Only if you want to know how far you went afterwards.

17. #### Isn't this obvious?

Just turn on your GPS and leave it in the same place. Subsequent location readings will differ from each other by some error margin and thus it will think it has moved (i.e. that your speed is non zero)

Now imagine you're moving very slowly compared to the error margin and you can see that it will think you're moving much faster than you actually are.

18. A friend of mine asked me to investigate the tracklog from his GPS watch (Garmin) as the total ascent recorded on a 10km walk was an awful lot more than he felt could possibly be true. It turned out that the problem arose when he'd stopped for food and drink for 20 minutes. He'd chosen a spot in the shadow of cliff (restricting the number of satellites in view). The inaccuracies had accumulated and while he was sitting there the tracklog accumulated a total of nearly 1km of ascent (and descent).

1. Not too surprising, altitude measurements from GPS are even less accurate. Units designed for hiking and such often combine GPS with a barometric altimeter for just that reason.

19. #### QI

Where's Stephen Fry when you need him?

1. #### Re: QI

Busy trying to send his location back to the Satellite.

20. #### Bah!

What happens if you discard all the paths that have an unplanned route through Oslo per Google Maps?

21. #### So what is the real distance?

This reminds me of what someone told me 30 years ago. When working on the very first satellite navigation systems I found they calculated distances that were different to the longhand spherical trigonometry. - Navigation - the science of estimation and the art of guesswork. And here is the clue. What is the "real distance". A nautical mile is defined as a minute of arc, but because the earth is not a true sphere the length varies depending where it is measured. It differs by nearly 20m between poles and equator, so an average length is used. Of course, the satellites follow orbits that follow the shape of the earth - an oblate spheroid. So which is correct? the distance measured by GPS calculation from a satellite with a non-spherical orbit, or a land-based calculation with all sorts of averaging and compensation to arrive at a standard datum? Its easy to fix a position by lat and long.It's not quite so easy to decide exactly what the surface distance is between those two points.

22. #### It's official!

We now have definitive proof that Science has indeed gone too far!

## POST COMMENT House rules

Not a member of The Register? Create a new account here.