typodupeerror

## GPS Always Overestimates Distances (i-programmer.info) 131

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 discussion has been archived. No new comments can be posted.

## GPS Always Overestimates Distances

• #### Simple problem with a simple solution (Score:5, Informative)

on Sunday November 15, 2015 @11:46AM (#50934687)
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 (Score:5, Interesting)

on Sunday November 15, 2015 @12:43PM (#50934943)
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: (Score:2)

Mostly. But the problem is in the time period you're averaging; if you take a longer average, the positional error would still average out. The reason it makes the zigzag is that the resolution we demand for our movements is different than the granularity of the noise errors.

Users want the small movements that are smaller than the expected noise level of the sensor. It might be possible to simply also take a longer average, and normalize the A-B distance based on that, while preserving the zigzag. That way

• #### Re: (Score:2)

You solidified what I was thinking a bit better. The first thing that came to mind was the infinite coastline paradox.
• #### Re: (Score:2)

Nope. The problem is reduced when you poll more often.

• #### Re: (Score:2)

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.

I've honestly never had this be a serious problem when running. I've even compared it to chip times at running events and the pace my GPS puts me at is typically within a second of the official race time. Now I've never tried this in NYC or somewhere else with serious urban canyons, i have done it in other cities with blocks of tall buildings.

• #### Re: (Score:2)

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.

My dad hired a "carpenter" once who measured every board 16 inches from the previous board. By the time he got 20 or 30 boards nailed in, his being off 1/8 inches each measure had ballooned to being off almost 6 inches and the boards having a noticeable lean.

I think the other issue they're dealing with besides skew is that you shouldn't be looking at the average distance between two points to calculate the distance as the "average" is always going to be greater or equal to the straight line shortest. You

• #### This seems really simple... (Score:2)

If the bias is known to be X percent on average, how about you subtract those X percent from the number to get an unbiased result? You might even come up with a way to estimate the bias in each particular case based on input from the sensors.

I thing apps like RunKeeper are already doing this sort of thing, because they seem pretty accurate to me, if perhaps a little too optimistic...

The thing is, you don't win users by under-estimating their achievements.

• #### less than 1% error in our driving testing (Score:2)

We tested a gps a couple of times over a few miles each time. This was using a handheld Windows device, for which my friend built software to function as a taxi meter.

I think TFA tried to measure distances that are two small - 1 meter and 10 meters. It describes one source of error - random errors increase the measured distance. However, there is another source of error in the opposite direction which compensates for the first. Due to sampling occasionally, the GPS-based measurement measures a curve as

• #### Consider a Fractal Cow (Score:5, Interesting)

on Sunday November 15, 2015 @03:25PM (#50935559)

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.

• #### Understatement of the day (Score:5, Insightful)

on Sunday November 15, 2015 @11:48AM (#50934699)

"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: (Score:2)

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

The infinite case is probably the most common, too, since the real motion of an apparently stationary device is smaller than the granularity of the position reading. People are just sleeping peacefully, not even realizing that their GPS positional error is infinite.

• #### Re: (Score:2)

It's up to 20%, based on measurements in a "10m square."

Real world, it's insignificant - especially with regard to what the summary refers to - " It is something that runners and walkers complain about a lot."

Basically, it overestimates because most of the random errors cause the measured distance to be further. Picture an arc with the center at one point, and the arc passing through the other. That's an equal-distance line. The closer the two points, the more over-distance bias there is. The farther betw
• #### Re: (Score:2)

In any case, the bias cannot be more than the GPS positioning error, maybe a couple of meters if you're having a bad day. I'd like to know who these runners/walkers are who are complaining about an extra meter or two.

"an extra meter or two" every 10 meters can add up to a huge distance over the course of a couple miles.

• #### Re: (Score:2)

The average is much less than that. That's merely a maxima. And, if you're using GPS as an odometer, you're doing it wrong - that's not what it's designed for.
• #### Re: (Score:2)

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

That's an odd use case for a GPS.

• #### Areas and volumes, not lengths (Score:1)

If it's purely a timing error, projected into 2D or 3D space, then for a number of variables having an evenly-distributed (or normal) error, most of the resulting positions will be 'far away'. For example, if you create a 7x7 grid, with yourself in the center square, and pick one of the 49 squares randomly, only 1/49 is correct, another 8/49 are within 1 distance, another 20/49 are within 2 distance, and so on, because the number of squares available increases for any given distance.
• #### Perhaps this explains my Garmin (Score:4, Informative)

on Sunday November 15, 2015 @12:18PM (#50934853)
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.
• #### Re: (Score:2)

According to this article (okay, okay, the summary), GPS error causes measured distances to be systematically overestimated.

What you're talking about -- a different but noticeable factor -- is that GPS polling frequency causes measured distances to be systematically underestimated. Because it's only sampling once every N seconds and then, because there's quite a bit of noise, applying a smoothing function to the result, it cuts the corners off of paths. It can cause pretty substantial underestimation, even

• #### Re: (Score:1)

Which Garmin model do you have? I have the Forerunner 610 and find it quite accurate but it depends on what you're doing. If you're running a 5K, then you're likely doing lateral or diagonal shifts from time to time to get by someone slower in front of you, or worse, a few people running side-by-side at a slower pace than you want to run; so you're adding distance. You might also wander off to the side to grab a few cups off the water table or you might be running in the middle of the course when the distan
• #### Re: (Score:2)

If you are running on a track your Garmin watch is accurate enough to underreport when worn on your inside wrist and overreport when worn on your outside wrist.

If you are running on a track and the polling frequency of your GPS is too low (not a factor with my Garmin) you also get the problem of underreporting due to chording the curve.

• #### Re: (Score:2)

that's my experience as well which is the opposite of what the study claims. It seems to under-report distance, which causes lower measured speed. Indeed, with dropped measure points ( corners, running under trees or dense urban environment) it just counts less distance.
About the current pace, that's a bit to be expected. I noticed it's doing error correction as well, where at first it seems to under-report, and the next 30 seconds it's claiming I'm running much faster.
• #### And where does "velocity" come from? (Score:2)

GPS is a position determination technology. GPS-based "velocity" is calculated by GPS device based on change in position (distance) and time. It is subject to exactly the same error as the position itself.

Apropos, in the GPS navigation software I work on, tracking uses adaptive smoothing precisely for the purpose of reducing the distance error.

• #### Doppler Shift (Score:2)

A very common way to get better velocity data (used for example in consumer grade ublox and mediatek receivers) is to directly measure the doppler shift of each satellite signal. Since you accurately know where each satellite is and their velocities, you can use the doppler shift between each satellite's signal to determine your own velocity with respect to them. The main advantage of this technique is that it is not affected by atmospheric propagation-delay variations (the signal might come later, but the

• #### Re: (Score:2)

Sorry, that's simply wrong:

The basic output (usually once per second for most GPS chipsets) consists of 7 parameters:

X,Y,Z and dX,dY,dZ along with T, wth the x,y,z values in an Earth Centered Earth Fixed coordinate system. I.e. velocity is an intrinsic output of the processing, resulting from the need to determine doppler values for all visible sats in order to track them.

Past this point many GPS units will do lots of post-processing, for some of them this includes using a lowpass filtered velocity model th

• #### Re: (Score:2)

If you work on GPS navigation software, you must be aware that GPS computes an instantaneous speed using doppler shift of the satellites. This is completely different from position delta based speed calculation.

• #### Re: (Score:2)

I would bet you though that 100% of the smartphone software used for tracking runs does not do that.

90% of the software used however does smooth out using one algorithm or another the run, because the coastline effect is too noticiable(basically if you had infinitely small polling time, the route would appear infinitely long)

• #### Quite the opposite (Score:2)

My experience is that my iPhone under reports my runs by at least 100m every 5km (I get variances of 100-300m under reported for the same 5.7km loop that I run once it twice a week.

I ran the Richmond-upon-Thames 10k last year and after crossing the line I had apparently only gone 9.8km. Other people at the finish mentioned their Garmins had reported even less. I wrote an email to the organiser who came back to me with a plausible explanation and a defence that they were IAAF measured (with a certificate c

• #### Re: (Score:2)

It would be genuinely easy to build an Arduino (or whatever)-based GPS logger for under \$50 that would let you actually set the GPS frequency, support PPS, etc. A GPS module with a nice big antenna is about \$13. An SD card reader module is \$3. Arduino Nano clones are \$3. All the code can be filched from examples.

• #### The interesting bit (Score:2)

The interesting thing about this is not that they've found an explanation for why a GPS always overestimates (which is pretty obvious), but rather that they've taken the time to work out the statistics and quantify this overestimate. Imagine a GPS implementing this, and therefore able at any point in time to give the expected error. It might tell you that it measured a path of 10 km, but that, because of the type of noise present, the actual path was probably closer to 9 km. You could even take that a bit f

• #### Fantastic math there, guys (Score:5, Interesting)

on Sunday November 15, 2015 @12:30PM (#50934901) Homepage

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 (Score:5, Insightful)

on Sunday November 15, 2015 @02:28PM (#50935377)

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: (Score:2)

That's a really great point. So much of this has to do with sampling frequency vs. resolution. The whole thing is funny. The original article is bad enough, but the post on the article is that much worse.
• #### Re: (Score:2)

Exactly. If the resolution on my measuring device is 2 m then all I can measure is multiples of 2 m, so 2 m, 4 m, 6 m, etc. This is perfectly acceptable for distances many times greater than 2 m, and would give me a pretty accurate measurement of a 10 km distance. I would be very happy with the amount of error present in a 10 km measurement made with such a device. But I couldn't measure 1 m with that any better than I could measure the spark plug gap for the plugs in my car with it.

• #### No sh*t (Score:1)

"the expected measured length squared between two points is bigger than the true length squared unless the errors at both points are identical." WTF are they squaring the points' positions?
• #### Just go by time, forget distance (Score:2)

When you run the same route each day - which I'm betting most work-a-day runners do, then you only need your time. You know your pace and cadence, forget the tech (and I have an Apple watch, plus an older Nike fuel...).

If you are running while on a work trip, maybe it helps but again, but you probably are just trying to get your workout before your meeting; fussing with workout tech just adds stress and that's what you are trying to combat with the run!

If you are running on vacation, what the hell is wro
• #### What? (Score:2)

A trivial calculation (really, I figured that out a long time ago), with a non-trivial solution.

*Ideally* you would not use the GPS signal with a Kalman filter in the input, but for distance calculations en the end of the trip you should use a variant of the filter which can "look into the future" for each point.

While the best estimate for the position at any given point in time can only be based the past data (and Kalman filters are ideal for estimating this under this condition), the estimation of a point

• #### Unless you run in a circle (Score:1)

... like on a track. In which case it'll cut the corners and underestimate.

In case it was not clear to everyone reading TFS, "GPS Always Overstimates Distances" is incorrect. The point of TFA is that, on average, distances are overestimated. GPS distance estimates are subject to random error, and the random error is biased. So more often than not, the estimate will be too large, but not "always". A better headline would have been, "GPS Usually Overestimates Distances". Less sensational, but more accurate.

• #### Haha, explains fudge factor in my app... (Score:2)

So, a few years ago I wrote a "Taxi Meter" app for iPhone (though got bored and never released it...).Not meant to be a real taxi meter, but a novelty, say to get the kids your ride-share partner to get a grasp how much running around you are doing, and what it would cost to get a taxi instead...

I had to multiple by a fudge factor

The fudge factor was good enough - it got it well under the 2% required for a real taxi meter. I checked it by driving specific routes and then plotting the routes on Google Ear

• #### Not GPS but some silly mapping application (Score:1)

Probably Google Maps for Anderhoid as that's what people generally mean when they refer to GPS. The title is very misleading, I thought this was about GPS receivers overestimating the distance they are from a given GPS satellite, which would lead to much the same location but far below sealevel (assuming it is overestimating each satellite by the same amount)
• #### Researchers? (Score:2)

You need to be a researcher in order to rediscover the effort of noise on sampling?

• #### Or not (Score:2)

Just do course smoothing and you can reduce the bias to zero.

Either way I don't know what my watch does but I have 5 marathons recorded and the recorded distances ranged from 41.95 to 42.5. Being Boston Qualifiers they were at least 42.195 so 4/5 were overestimates and a total error of less than 1%.

I also do a series of XC races where the published distances (measured by mountain bike) are notorious for being 5-10% longer than peoples GPS. Assuming the bikes aren't horribly calibrated the explanation is the

• #### The GPS trail distance problem (Score:2)

I hike with a club two days a week, and on every outing there are several of us who measure distance and elevation change with a GPS. Our distance measurements are always different, because of the interval between readings for each device.

Imagine a twisty trail being hiked. Whenever your GPS takes a reading, it's like pushing a map pin identifying one specific point on that trail. Think of your device's distance measure as a thread stretched from pin to pin all the way along the trail. See how the sum of al

• #### Drunken walk (Score:2)

A similar effect can be obtained when walking (don't recommend driving) home from the pub on a friday night. The distance seems twice as far....

• #### Another reason linking up with the car is useful (Score:1)

The car can report its current velocity and compass reading, something that phones have a hard time doing on their own. For this reason and others, I look forward to a proper car to phone interface.

• #### that's news? (Score:1)

have you never ever watched the indoor jitter without you moving at all on any tracking app you just installed to check out?
• #### Path Jitter, integrated (Score:2)

Likely the GPS is subject to path jitter. You might run in a straight line but the GPS path will suffer jitter of 10's of meters or more to each side of your straight path. For overall distance it adds up all those imaginary zigs and zags and boom, long run.

• #### It's all about Jensen's Inequality (Score:1)

Jensen's inequality [wikipedia.org] says that if f(x1, ..., xn) is a convex function (curving upwards in all directions), and (x1, ..., xn) is a random vector, then the mean value (probability-weighted average) of f(x1, ..., xn) is higher than f evaluated at the mean value of (x1, ..., xn). It's easy to see this if n=1 and there are only two possible values of x, because the line drawn from (a, f(a)) to (b, f(b)) always lies above the graph of the function f.

If you take f(x1, x2, x3, x4) to be the measured distance betwee

• #### Doppler Velocity and Uncorrelated Position Errors (Score:2)

The authors suggest that doppler velocity calculations should be immune to the kind of overestimation they claim sampling position measurements suffers from. I don't think this can be the case.

Let's first focus on what is wikipedia claims is the largest source of error: signal delay from the ionosphere. It seems reasonable to assume that this delay changes in a continuous manner with time. However, that means that the (non-shared) error introduced into position measurements as a result also shows up in t

• #### Not always (Score:2)

GPS Always Overestimates Distances

Only if you travel in a straight line (and even then, only if you calculate your distance based on all your way points, and don't just use your start and end positions). That's why I zig-zag everywhere I go.

• #### Not surprising (Score:1)

This news is not surprising to me, although in my case it seems to go both ways. I've run races with a BibTag while tracking it on my phone and so far, it either comes up short or makes me a faster runner than the official time registration.

I also map out routes beforehand sometimes and I always try to make the mapped route a little longer so I know the GPS will go the distance. Not 20%, though.

• #### Two Things (Score:1)

1) Set your Garmin sampling frequency to 1-second. Always. The default of "auto-magically" or "as-needed" is not sufficient. Especially when doing a run or bike ride on a course with lots of turns or on a track.

2) If the over-estimation is fairly consistent, then what does it really matter to the average amateur? If a route that you regularly time is actually 5 miles and not really 5.15 miles, who cares? What matters is your time over that same distance. It's a like a scale that is low by 2 pounds. It doe

#### Related LinksTop of the: day, week, month.

Basic is a high level languish. APL is a high level anguish.

Working...