3D Robotics

### Don't use GPS for odometry!

Very interesting research that shows that the statistical errors build up with GPS in a way that exaggerates distance traveled. Counterintuitive!

Have you had a suspicion that your GPS app is overestimating the distance traveled? 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.

The mathematics of GPS position finding are complex enough to be left to a code library, but lots of apps will take a set of co-ordinates and work out the distance between each adjacent pair on a path to work out the total distance traveled.

This is so simple and so intuitive that it is hard to see how it could possibly go wrong, but it does.

If you start thinking about how this algorithm could give you the wrong answer then your first conclusion might be that interpolation error might dominate. After all the user is taking a curved path through the world and your GPS calculation is approximating this curve with a set of straight line segments. A moment's thought should reveal that this suggests that the GPS distance will be less than the true path. This is correct, but in practice GPS measurements are taken often enough to make interpolation error small.

The reason is all down to the errors in the positions and how these errors accumulate.

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. This is how it seems to be with GPS  there are errors in positioning that are inherent in the system but certainly don't show any particular bias. Given this observation you would expect the distance between two points located with unbiased random error would also be unbiased, i.e. it would be on average bigger as often as it was smaller than the true value.

However, you would be wrong.

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. Irrespective of the distribution of the errors, the expected measured length squared between two points is bigger than the true length squared unless the errors at both points are identical.

That is, if you have two points p1 and p2 and errors in measuring x and y at each, the squared distance measured between them will come out as bigger than the true distance unless the errors are such that they move both points by the same amount - which is highly unlikely in practice.

How can this be?

Consider the two points and the straight line between them. This straight line is the shortest distance between the two points. Now consider random displacements of the two points. The only displacements that reduce the distance are those that move the two points closer together, for example displacements along the line towards each other. The majority of random displacements end up increasing the distance.

This is the reason that unbiased errors end up biasing the distance measurement.

So given that the GPS path is just a sum of distances computed between pairs of points, the total estimated distance is going to be bigger than the true distance because of random errors.

A little more work and the researchers derive a formula forhow much of an Over Estimate of Distance OED is produced:

OED= (d+ var - C)1/2 - d

where var is the variance in the GPS position and C is the autocovariance (correlation) between the errors. Notice that the more correlated the errors, the smaller the over estimate.

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.

Is there anything to be done?

The researchers point out the measurement of speed is not subject to the same problem. GPS devices can measure speed using Doppler shift and this is accurate and not subject to the same measurement bias. It might well be that you can get unbiased distances by integrating velocity measurements over time.

Runners and other athletes have long complained that GPS devices overestimate their performance and there have been lots of suggestions as to why.

This research does seem to have come with the answer - statistics.

Peter Ranacher, Richard Brunauer, Wolfgang Trutschnig, Stefan Van der Spek & Siegfried Reich (2015): Why GPS makes distances bigger than they are, International Journal of Geographical Information Science, DOI: 10.1080/13658816.2015.1086924

Via Robohub

• I could have chosen better wording above. My point was that wandering in position does not matter for an odometer. An odometer does not care where you end up. It only cares how far you went to get there. Sure some error will still accumulate because your velocity measurement is not zero mean, and your speed estimate has an inherent bias. However, this error will accumulate much slower than adding the distances between PVT solutions.

Although this is a more accurate (but still biased) odometer estimate, it would not be able to map your path in multiple dimensions.

• Carrier phase measurement is indeed used to derive velocity information in GPS receivers. Under open sky situation accumulating velocity vector one could have accurate relative movement from a known initial position until code-carrier divergence effect accumulated. Since most GPS watch odometer involve using tiny antenna resulting in noisy measurement, compounded by fluctuating signal under tree foliage and multipath problems, it’s simply not practical to use such technique, but resorting to adding up code phase derived position differences, with some scheme to reduce error.

Performance comparison results shown here provides idea why we plan to offer an entry level GPS-only receiver with RTK capability for hobbyist, not that hardware difference is minimal and software engineer don't need to eat. :-)

• Your RTK GPS sounds great! It makes sense that it can be priced similar to other GPS because the hardware differences are minimal, but we all know that engineers need to eat too. RTK GPS requires a lot more engineering!

One point of these articles is that velocity vector measurements can be made using carrier phase without a reference station. These velocity measurements have much less noise than the PVT solution, which lessens the estimation bias when estimating speed from the velocity measurements. Just like your RTK GPS, these GPS odometer companies could easily use carrier phase instead of pseudo-range. However, these companies chose to deliver a poor product to save a few cents per unit. Everybody that bought a hardware GPS odometer should feel cheated.

• Pedometers count steps. If using GPS to calibrate pedometer, then back to square one with questionable GPS accuracy for odometry. :-)

With some form of pinning implemented to avoid static position drift, GPS pedometer accumulates straight segment distance between two points, a measuring wheel adds up all the curvature distance on the road, might be this causing GPS odometer underestimating distance you experienced.

Yes, we have interesting RTK developments in the past months. I’m currently waiting for a breadboard friendly version to return next week. If performance checks out OK, we'll make available a GPS-only receiver with RTK capability at comparable price of GPS receivers selling on DIY electronics store, effectively making RTK GPS receiver seen on Kickstarter 2 years ago affordable to hobbyists at 1/10 of the price. Will make a posting after this design checks out OK.

• Well, pedometers have been around for a long time.  Supposedly they can be fairly accurate and can even automatically calibrate themselves though I don't have any experience with them.

I guess the point here though is the intelligence of the software can make a big difference.

For GPS that would be the positioning filter.  I've tried some more odometer tests with the Garmin I mentioned and, if anything, I've been seeing slight under estimates on distance.  Of course I'm doing it in relatively good GPS reception areas.

So Oliver, your RTK GPS receiver seems to be available to order.  It should be an excellent odometer - under very good GPS receiving conditions.  Time for a post announcing it!

• GPS wanders like below when static. GPS odometry implemented by adding distance of two consecutive points will eventually accumulate distance over time. As the object move faster, this noise like effect on each piecewise segment being accumulated becomes smaller percentage-wise, thus GPS odometry result will be more accurate moving at faster speed.

GPS odometer function in products today try to reduce such static distance accumulation by implementing some speed cut-off threshold. So under open sky without multipath, GPS odometry can be usefully accurate.

GPS being a measurement process on the received signal, the result becomes noisier as antenna gets smaller. Runners and athletes complain about GPS not accurate mostly due to small sized antenna used in GPS watch resulting in noisier measurement and also multipath induced errors.

For moving objects without wheel, if don’t use GPS for odometry, what other affordable choice is there?  :-)

• I disagree with the title.  GPS makes an excellent odometer!

Of course the real question is an odometer for what?  Walking around in a small area only 10 meters wide?  In an urban environment not that great for GPS reception?  Using some wristwatch GPS with a terrible antenna?   Under those conditions a GPS probably won't do well as your movements are nearing the noise level in the measurements.  But the typical DIYdrones reader is likely flying an aircraft around in a somewhat regular pattern over an area at least half the size of a football field if not larger.  This is usually a very good GPS receiving environment.

The actual GPS hardware and software used can make a big difference too.  DIYdrones found this out several years ago when they switched to the Ublox chipset from the MTK.  There was a lot less noise with the Ublox.

As a little experiment I pulled out an older Garmin GPSMAP 76 hand-held unit and headed over the the local high school football field.   Using the track log feature I set it to record a position every second and then walked the painted perimeter of the football field.  I did this ten times.  After each time I saved the tracklog and the receiver computed a perimeter.  The ten perimeters I got were:  346.89, 348.10, 345.88, 346.29, 344.64, 345.09, 348.48, 345.57, 349.40, and 345.87 yards.  The average was 346.62 yards.  An American football field perimeter is 346.66 yards long.  All errors were less than 1 percent.  Not a bad odometer at all.

• This effect is typical for positioning algorithms that only use pseudoranges for position calculations. Because the error added by multipath (reflections of the GNSS signals) typically increases the pseudoranges, the distance travelled will look longer than it actually is. When using phase-based positioning techniques like RTK the effect is much less because phase measurements are affected less by multipath.

Also note that there is a correlation between the errors on the position. Most low cost chipsets only output the variances (for example only east, north & up separately) and not the covariances (the east-north correlation for example). You can easily see this if you plot the horizontal position of a static receiver in a perfect open-sky environment over a long time. The result will not be a perfect circle, but an ellipse with a larger error in the north-south direction because there are less satellites in the northern part of the sky (or southern part in the southern hemisphere). This ellipse will be slightly tilted because of the correlation between east-west & north-south errors.

Anyway, note that the odometer in a car makes a much larger error than most GPS-based odometers (even low cost ones) - so the impact of this phenomenon should not be overestimated.

• I'm glad that the online article does not contain the error. It restores my faith in peer reviews.

• I think the "60%" figure was actually just typo in the online article (rather than the paper). Actually, it looks like they fixed it. :)