Slashdot Mirror
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.
This gem caught my eye:
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:
OpenSource.MathCancer.org: open source comp bio
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.
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.
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.
SJW n. One who posts facts.
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.
Some drink at the fountain of knowledge. Others just gargle.