GPS Always Overestimates Distances (i-programmer.info)

mikejuk writes: Have you had a suspicion that your GPS app is overestimating the distance traveled? It is something that runners and walkers complain about a lot. If so, you are probably correct -- but the reason isn't an algorithmic glitch. The answer lies in the statistics, and it is a strange story. If you make a measurement and it is subject to a random unbiased error, then you generally are safe in assuming that the random component will make the quantity larger as often as it makes it smaller. Researchers at the University of Salzburg (UoS), Salzburg Forschungsgesellchaft (SFG), and the Delft University of Technology have done some fairly simple calculations that prove that this is not the case for GPS distance measurement. Consider the distance between two points — this is along a straight line, and hence it is the shortest distance. Now add some unbiased random noise, and guess what? This tends to increase the distance. So unbiased errors in position give rise to a biased overestimate of the distance. There is an exact formula for the bias and in some cases it can be more than 20%. Is there a solution? Perhaps using velocity measurements and time to work out distance is better — it isn't biased in the same way, but how accurate it could be remains to be seen. So when your fitness band tells you you have run a 4-minute mile — don't believe it.

Comments

Simple problem with a simple solution

[carlhaagen]

As a sailor who use GPS alongside traditional navigation: stop using devices that poll and insert a new leg on your route every 5 seconds. If you lower the polling frequency to f.e. every 1 or 2 minutes this problem goes away. I realize that this doesn't work for people who insist on taking their morning run zig-zagging through city blocks.

Re:Simple problem with a simple solution

[Solandri]

That doesn't completely fix it. The problem is related to both polling frequency and positional error.

The reason is pretty obvious if your GPS device has ever been slow getting a fix on multiple satellites and has a large error circle. One moment it says you're at position x, 5 seconds later it says you've warped half a mile away. The larger the positional error, the greater the distance error. Assuming you're traveling a straight line path, the positional errors average out to zero only when the errors fall along the line you're traveling. Any positional error perpendicular to your direction of motion results in an overestimate of distance traveled by tracing your route as a zig-zag instead of straight.

That would suggest a smoothing algorithm could mostly fix this. Basically draw the simplest curve you can that goes through all the error circles around the breadcrumbs the GPS has recorded.

Re:Simple problem with a simple solution

[serviscope_minor]

Assuming you travel in a straight line, then all of those errors should be randomly distributed to both sides of your actual line of travel.

They're not though. There's temporal errors in the correlation. Various atmospheric effects cause bias, for example. There are various companies offering high end devices which can record the signals then post process them based on atmospheric data. WAAS does the same thing in a more timely manner but it's a little less accurate then the offline methods (as may be expected).

Also if you're getting errors due to multipath, you'll get effectively correlated errors until you move far enough that the receiver locks on to a different one of the reflections.

And finally, a lot of receivers use a simple Kalman filter to track the frequency/code position. This produces slight biases as well, because the model in the KF doesn't quite match reality. If you model the orbital mechanics of the satellite properly and use that as a feedforward step in the filter, then you remove another source of bias. Most receivers don't because there's just no real need to introduce the extra complexity, and small, correlated errors don't matter all that much.

Nonetheless there's just a sample of how temporally correlated errors creep in. Once you have temporal correlation, additional sampling doesn't help much and obviously can never get rid of errors whose time constant is longer than that of your filter.

As for the best fit line, you need to be careful there. You need to have a model which matches how the person runs. For example you might want piecewise linear, where the size of angle doesn't introduce cost (unless it's too small?), and there's an expected distribution of distances between joints, such that anything outside that distribution (too short) introduces cost.

It's a horrendous optimization problem, but the data's quite small, and I'd bet simulated annealing would solve it pretty well, as would a number of different heuristic algorithms.

Re:Simple problem with a simple solution

[Aighearach]

http://www.adafruit.com/datash...

That's the cheapo GPS chip that makers are using. ~$40 on a breadboad module, but more like $5 as an OEM part. Calculates and stores "up to 3 days" of satellite position, then uses a lookup table. That is part of why new units still take a long time to get a cold fix; they're calculating satellite positions.

This has been a standard feature since around 10-15 years ago when they started advertising improved urban accuracy. If you're not predicting locations, you'd have to do a cold fix every time you walked past a building! It would be basically unusable downtown. Like in the old days! Back then it was also largely unusable in the forest; you'd have to find a clearing, or else remain stationary for a couple minutes, to get a fix on a cheap unit. That is why back then for serious outdoor use people were dropping $500 on dedicated GPS units that had the predictive routines, and regular GPS was intended mostly for highway auto use where the sky is usually visible.

Almost everything predictive uses Kalman filters. That is not a sign of low quality. It is a system of using predictions and expected error rates to overcome noise. If the result quality is low, it is not because of using a Kalman filter it is because of having a low quality prediction routine, or an inaccurate expected noise level. There is nothing about orbital mechanics or radio propagation that makes Kalman filters a poor fit; actually, it is nearly the ideal case for them; the noise will have a Gaussian distribution.

Understatement of the day

[Sqr(twg)]

"it can be more than 20%" -Yeah, it can be an infinite number of %, if the actual distance travelled is zero, and the random error is not.

Re:Shortest distance is not a straight line

[MightyYar]

While technically correct, your correction is not really relevant to the discussion... Add random noise to the ideal arc and you get the same result - error that always goes up, never down.

Perhaps this explains my Garmin

[suprcvic]

I began running 5ks recently and the watch consistently reports my distance as 100 - 150 meters short of 5k when I finish. It is also fairly inaccurate in reporting my current pace particularly when I've turned a corner or made any kind of deviation from a straight line really. I've been running long enough at this point to know when I'm running a 9 minute/km pace (yeah, I'm a turtle) but my watch will occasionally say I'm running a 7 minute km.

Fantastic math there, guys

[macklin01]

This gem caught my eye:

To test the theory some experiments were performed. A consumer quality GPS was walked around a 10m square with segment lengths of 1m and 5m. The average measured segments were 1.2m and 5.6m. That is, an overestimate of between 20% and 60%. Clearly a smaller segment length is a good idea.

That's some amazing math there. (1.2 m - 1.0 m) / 1 m = 0.2, indeed a relative error of 20%. But (5.6 m - 5.0 m) / 5 m = 0.12, a relative error of 12%, not 60%! So, let's fix this thing, with of course the opposite conclusion:

To test the theory some experiments were performed. A consumer quality GPS was walked around a 10m square with segment lengths of 1m and 5m. The average measured segments were 1.2m and 5.6m. That is, an overestimate of between 20% and 12%. Clearly a longer segment length is a good idea.

Re:Fantastic math there, guys

[_Shorty-dammit]

It's not just that they can't even determine that it was 12% in that case. They're simply doing it wrong from the beginning. "Let's take a technology that gives us a measurement that contains a possible error of more than the length we are trying to measure, and then complain about how much of an error we got in that length!" The best accuracy I've ever seen reported on my GPS is 2 m. Why would I try to measure 1 m with that?! Go do the experiment with a 10 km square and see what your error is then. *sigh*

Re:Shortest distance is not a straight line

[MightyYar]

No, measurement error will actually bend space time.

Re:This seems really simple...

[aix tom]

The thing is, while there might be a function to correct the bias, that function most likely can't be applied to the "end result". For example, you can't just substract / add something to the distance calculated.

I suspect what they do is calculate the distance travelled between two measurements, and then add up that calculated distance. Which of course is a horrible way to do it, since in amplifies the errors in the location into bigger and bigger errors in distance.

They basically need to apply "smoothing" to the gathered data first. Back in the old days, when I still did analytics of physical measurement with "pen and paper" the standard way to plot a graph was to dot in the measurement, then squint your eyes and draw the resulting graph "smoothly through the dot-cloud". No exactly rocked surgery for anyone who has a basic understanding of physics and/or statistics. Makes one wonder who programmed those Apps. They probably took an API-Example for distance calculation and slapped an shiny GUI over it without further thought.

Re:Funny, my bar stool feels like it's moving

[davester666]

No, that was you having a movement on your bar stool.

Re:Strange reasoning and I'm no geometer but...

[ceoyoyo]

You're missing something.

Imagine you're running along in a one dimensional world. Any positioning errors will move any two points either directly towards each other or away from each other. The average bias should be zero.

If you allow two dimensions, errors can now occur to the right and left of your path, even if you're still running along in a straight line. Any lateral error, right or left, will increase the measured distance between points. That's where the bias comes from.

If I followed your post correctly, the effect you're referring to is the same as the interpolation error mentioned in the article, and actually tends to decrease the measured distance.

Consider a Fractal Cow

[goombah99]

Imagine for a moment that instead of going from point A to point B, you instead Zigged at 45 degrees then half way you Zagged back on the slant path to point B. Clearly then your total trip is sqrt(2) times the straigtline distance. But you went needlessly off the path. Instead we shall imagine that we can detect when we have deviated by 1 foot from the straight path. So we now execute a zig zag (45 degree) path turning each time we deviate by 1 foot from the true path. How far did we go? Oh my, it's still sqrt(2) times the straight line. We work hard and improve the duidance system so we now can detect when we are 1 micron from the straightline path. How far? still sqrt(2) times the straight line.

Indeed no matter how accurate we can detect the deviation so that the true path is beyond the capacity of any instrument to measure the deviation, say 1/100th of angstrom the same logic holds.

ergo all paths between A and B including the straight path are 1.41 times the straighpath distance.

Fractal hamburger.