How does Ardupilot do it?? GPS accuracy issues !!! Distance Calculations

OK, firstly i’m sorry if this question has been posted elsewhere, i’ve had a good look in the forum and i haven’t really found an answer.

I’ve read a whole load about calculating gps positions using arduino and the problems relating to accuracy, i know there’s a couple of posts relating to accuracy issues and i thought about adding to them, but they’re in the old “read only” forum and this is only kinda related.

I know that “Floats have only 6-7 decimal digits of precision” and that doubles are essentialy the same, so my question is…

How does the Ardupilot module calculate gps distances so accurately? How have those cleaver people worked around the float/double issue?

I’m working with some pretty large distances (up to 1000’s of kilometers), so the initial accuracy of the fix during the calculations is really important as is rounding errors!!

Any other work around’s would great.

I'm working with a gps also, I'm using the TinyGPS library, its a life saver. The tinyGPS library can read in the NMEA statements from a gps and load them into floats. These NMEA statements are decimal equivalent to the hours, minutes,seconds of "normal" gps coordinates. The way that those decimal values are calculated, a change of .00001 is actually only about 6-8 inches (depending if it is latitude or longitude and location) while a change in the "ones" position can be hundreds of miles. So the float can handle great accuracy , besides most GPS with NMEA only output down to the 5th place which is still within a float's range. I don't know much about the Ardupilots but i would guess that is accurate enough to navagate. I

@wkuace

I think you (or i) my have misunderstood floats, i maybe did not explain fully in my post i should have quoted the entire paragraph, so here it is.

"Floats have only 6-7 decimal digits of precision. That means the total number of digits, not the number to the right of the decimal point. Unlike other platforms, where you can get more precision by using a double (e.g. up to 15 digits), on the Arduino, double is the same size as float."

the 6-7 bit i believe is to take into account the "." in the statement, ie one of the "digits or precision" is the "." so you can further reduce your accuracy if you have a decimal point.

So as i understand it this means that if i have an NMEA statement that says my position is 121°35'.87663 my float will only record 121°35'.8 and who knows whether it will round up or down the following figures to make it .8 or .9.

So now we are up to a 0.099minute out with both the position and the destination waypoint, which then will increase after its put into the haversign formula due to rounding errors.

There is already a thread in the old "read only" http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1294325235 so for more stuff in gps's and floats have a look there.

It's all very frustrating.

Is there a way to put everything to the left of the decimal into a long, and everything to the right of it into another long, and work with the number that way?

year, i guess i could put 2 longs together and deal with it that way, but i would still really like to figure out how ardupilot does it?

afclewis: year, i guess i could put 2 longs together and deal with it that way, but i would still really like to figure out how ardupilot does it?

ArduPilot_2_7/GPS_NMEA.pde:102

afclewis: @wkuace

I think you (or i) my have misunderstood floats, i maybe did not explain fully in my post i should have quoted the entire paragraph, so here it is.

"Floats have only 6-7 decimal digits of precision. That means the total number of digits, not the number to the right of the decimal point. Unlike other platforms, where you can get more precision by using a double (e.g. up to 15 digits), on the Arduino, double is the same size as float."

the 6-7 bit i believe is to take into account the "." in the statement, ie one of the "digits or precision" is the "." so you can further reduce your accuracy if you have a decimal point.

So as i understand it this means that if i have an NMEA statement that says my position is 121°35'.87663 my float will only record 121°35'.8 and who knows whether it will round up or down the following figures to make it .8 or .9.

So now we are up to a 0.099minute out with both the position and the destination waypoint, which then will increase after its put into the haversign formula due to rounding errors.

There is already a thread in the old "read only" http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1294325235 so for more stuff in gps's and floats have a look there.

It's all very frustrating.

What you are missing is that a float gives you six or seven significant figures in base 10, not six or seven digits in base 10. That's a major distinction. Seven signficant figures will give you precision as good as the GPS system is actually capable of. Over a hemisphere, seven signficant figures in distance works out to a spatial resolution of a couple of meters. It is possible there's a bug in Arduino floating point implementation, of course.

Fixed point is great for applications like this -- there are plenty of libraries and references for it floating around the web. I have no particular ones to recommend, however.

afclewis:"So as i understand it this means that if i have an NMEA statement that says my position is 121°35'.87663 my float will only record 121°35'.8 "

I believe you will get an error if you try to load a string into a float. 121°35' 53" in decimal equivalent is 121.598056. you also have to allow for N/S and E/W.

Don't forget, GPS is +/- 5-10 meters anyway. If you require accuracy, you should look at Vincenty's formulae.

afclewis:"So as i understand it this means that if i have an NMEA statement that says my position is 121°35'.87663 my float will only record 121°35'.8 "

What the GPS outputs is a string, not a float. It's up to you to decide what to do with that string in your program. You are correct that if you decide to store that value in a float you will lose precision.

The string consists of three parts: degrees, minutes, and seconds. Degrees is an integer between 0 and 359, minutes is an integer between 0 and 59, and seconds is represented by five digits between 00000 and 99999. All three of those values fit comfortably into unsigned integers.

The usual way to deal with data elements like that is to create a struct to hold them. For instance:

 typedef struct 
  {
      unsigned int degrees;
      unsigned int minutes;
      unsigned int seconds;
  } GPSCoordinate;

Then it's simple to write utility functions to populate a structure from a string, to write the value of a structure as a string, and to calculate the difference between two structures.

If I were doing this I'd make a class library so I could use c++, which really lends itself to this kind of work.

@DCContrarian Many thanks i'll have a see if i can do as you suggested, seems like a good plan. I'm not sure my coding is up to making a class library, but i'll give it a go and see what happens.

afclewis: ... seems like a good plan.

No this is not a good plan and will not get you anywhere. You need to convert GPS coordinates to variables of type float in order to use them in your distance calculation formula.

Single precision (32-bit) float is all you need to do these calculations with a precision and accuracy suitable for any practical purpose. The “trick” is to convert the NMEA GPS coordinates to radians (not decimal degrees). Further, you should calculate distance as an arc rather than a metric value. You will only convert it back to a metric value for display purposes.

Start with reading the NMEA output and convert coordinates to radians. Once you have this working, you can proceed to code for distance calculations.

Some facts:

  • Float as implemented on the Arduino is in accordance with IEEE 754. This is single precision (32 bit) float.
  • IEEE 754 uses a 23 bit mantissa (determines precision), 8 bits for a two’s complement exponent (determines range) and 1 bit for sign.
  • Precision expressed as a number of decimal digits can be calculated from the formula log10(2**24) which is approximately 7.225 decimal digits.
  • The float library on Arduino is coded in optimized assembly for the AVR range of micro controllers.
  • Using floats for basic arithmetic (multiply, divide, add, subtract) is generally faster on the Arduino than using 32 bit integers, but add somewhat to the initial code size.

@BenF

Many thanks, for your comment, i did have a good think about the previous statement before instigating it and never actually started writing the code, so all good there.

I'll set about converting the NMEA string to radians tomorrow. Thanks for the detail about how a float is made up, things making more sense now.

BenF:
Single precision (32-bit) float is all you need to do these calculations with a precision and accuracy suitable for any practical purpose. The “trick” is to convert the NMEA GPS coordinates to radians (not decimal degrees). Further, you should calculate distance as an arc rather than a metric value. You will only convert it back to a metric value for display purposes.

Start with reading the NMEA output and convert coordinates to radians. Once you have this working, you can proceed to code for distance calculations.

Some facts:

  • Float as implemented on the Arduino is in accordance with IEEE 754. This is single precision (32 bit) float.
  • IEEE 754 uses a 23 bit mantissa (determines precision), 8 bits for a two’s complement exponent (determines range) and 1 bit for sign.
  • Precision expressed as a number of decimal digits can be calculated from the formula log10(2**24) which is approximately 7.225 decimal digits.
  • The float library on Arduino is coded in optimized assembly for the AVR range of micro controllers.
  • Using floats for basic arithmetic (multiply, divide, add, subtract) is generally faster on the Arduino than using 32 bit integers, but add somewhat to the initial code size.

What I proposed was 16-bit integer math, not 32 bit. I can’t believe float math – which requires an add-on library – is faster than 16-bit integer math, which is done through native instructions. In any case, for an individual calculation the difference is going to be microseconds; unless you’re tracking millions of devices the difference is going to be immaterial.

Converting to radians does nothing to improve your precision. You start with degrees anyway and then multiply and divide which introduce additional rounding errors. It makes no difference that degrees are 3-digit decimal numbers and radians are 1-digit, the internal representation is base-2.

Here’s an experiment: take the measurement given, 121°35’.87663. In excel, convert it to radians, and at every step round your result to seven significant digits. Then convert it back to degrees, also rounding at every step. When I do that I get 121°35’.87400. Three significant digits were lost in the conversion.

With a float, you’ve got 23 bits of precision. Is that enough?

As a float, you are representing a value with a 23-bit binary times a multiplier. Your precision is determined by the incremental change when the lowest order bit flips. It’s the circumference of the earth divided by 2^23. That’s about 15 feet. Regardless of what units you pick, that’s the smallest increment that can be measured. Unless you are very careful rounding errors can creep in and make your precision significantly worse.

What it really gets down to is precision vs accuracy. The string you get reports a measurement in minutes with five decimal places. This level of precision implies the measurement is accurate to 1/100,000 of a minute. A degree of minute is roughly 1.1 miles; 1/100,000 of a minute is about one half inch. By using integers you maintain that precision. I agree that this precision is greater than the accuracy of the GPS.

Is float precision enough? You tell me. It’s probably close to the accuracy of the measurement. I know if it was me I’d rather design in greater precision than lesser, and design to preserve the precision I was given rather than lessen it.

What I proposed was 16-bit integer math, not 32 bit. I can't believe float math -- which requires an add-on library -- is faster than 16-bit integer math, which is done through native instructions.

This is general information, unrelated to your post. The AVR microcontrollers used with Arduino do not have native instructions for multiply and divide and rely on compiler generated code. There is no reason whatsoever to avoid integer math, but speed is not a reason to get overly creative towards avoiding floats.

DCContrarian: Converting to radians does nothing to improve your precision. You start with degrees anyway and then multiply and divide which introduce additional rounding errors. It makes no difference that degrees are 3-digit decimal numbers and radians are 1-digit, the internal representation is base-2.

Yes it does. Trigonometry in C requires radians and so keeping the source and intermediate results in the same format avoids repeated conversions and loss of precision. More significant however is to calculate distance as an arc. This prevents loss of precision resulting from intermediate calculations with small values (angles) and large values (distances).

DCContrarian: With a float, you've got 23 bits of precision. Is that enough?

Actually you have 24 bits (sign bit included) and yes this is enough.

DCContrarian: As a float, you are representing a value with a 23-bit binary times a multiplier. Your precision is determined by the incremental change when the lowest order bit flips. It's the circumference of the earth divided by 2^23. That's about 15 feet. Regardless of what units you pick, that's the smallest increment that can be measured. Unless you are very careful rounding errors can creep in and make your precision significantly worse.

Correct that for 24 bits and you will be close.

DCContrarian: What it really gets down to is precision vs accuracy. The string you get reports a measurement in minutes with five decimal places. This level of precision implies the measurement is accurate to 1/100,000 of a minute. A degree of minute is roughly 1.1 miles; 1/100,000 of a minute is about one half inch. By using integers you maintain that precision. I agree that this precision is greater than the accuracy of the GPS.

GPS accuracy is referenced to absolute position. When we navigate and do repeated calculations we can expect relative position reports much better than the general stated accuracy. We can not expect inch accuracy with float calculations, but this was not what was asked for.

DCContrarian: Is float precision enough? You tell me. It's probably close to the accuracy of the measurement. I know if it was me I'd rather design in greater precision than lesser, and design to preserve the precision I was given rather than lessen it.

The problem with your proposal is that you will have to write your own functions for trigonometry and basic arithmetic to maintain precision.

I have written a marine autopilot based on an AVR microcontroller and so it’s a bit more than speculations on my part.

BenF: The problem with your proposal is that you will have to write your own functions for trigonometry and basic arithmetic to maintain precision.

No, I'm not proposing that at all. This is what I proposed:

Then it's simple to write utility functions to populate a structure from a string, to write the value of a structure as a string, and to calculate the difference between two structures.

The only calculation I propose is the difference between two structures -- subtraction. You're absolutely right that to do sine/cosine calculations you need floats. However, by storing the received values in a format that preserves precision you can do subtraction that preserves precision. You can then take the subtracted value and convert it to a float. If it's small -- like hundreds of feet -- that conversion will preserve precision, and that precision is likely important. If it's large -- thousands of miles -- precision is lost but it's likely not important.

If you convert to a float before doing subtraction you lose precision in all cases.

DCContrarian: The only calculation I propose is the difference between two structures -- subtraction.

The difference in longitude (the distance moved in the west to east direction) depends on latitude. If we travel along the equator this can be approximated as an arithmetic difference, but for any other latitude (such as somewhere in North America) this is not so. To account for this difference we need the trigonometric functions. Precision becomes the least of your worries if you ignore this fact.

BenF:

DCContrarian: The only calculation I propose is the difference between two structures -- subtraction.

The difference in longitude (the distance moved in the west to east direction) depends on latitude. If we travel along the equator this can be approximated as an arithmetic difference, but for any other latitude (such as somewhere in North America) this is not so. To account for this difference we need the trigonometric functions. Precision becomes the least of your worries if you ignore this fact.

Got it, a move of X degrees east and Y degrees north is not the same distance everywhere on the globe, it depends on latitude.

There are several formulas for calculating distance between two points on a sphere, but for any of them, your inputs are going to be the latitude of the first point, the latitude of the second point, the difference in latitude between them and the difference in longitudge between them.

My point is that for calculating the differences in latitude and longitude, you preserve precision by subracting first and converting to radians second rather than converting to radians and then subtracting.

For short distances -- like hundreds of yards -- to exploit the full precision of the GPS signal the floating point library on an Arduino is inadequate, at least using great-circle calculations. If two points are a kilometer apart the cosine of the angle between them is 0.9999999877. That's seven nines in a row, and the difference between that number and 1 compared to 1 is less than the precision of a 32-bit float. The GPS can give you measurements that are more precise than what you can calculate using great-circle methods.

I suspect you would get more useful results pretending that your little patch of the earth is flat, calculating the length of a second of latitude and a second of longitude at your latitude, constructing a right triangle with height equal to the difference in seconds of latitude and width equal to the difference in seconds of longitude, and then calculating the length of the hypontenuse of that triangle using the Pythagorean theorem.

This Pythagorean method is what the haversine formula simplifies to if you assume the same latitude for the starting and ending points. The advantage of the Pythagorean method is that you don't do any trigonometric calculations on tiny, tiny angles. You do multiplication, addition, square root and cosine on large angles (latitude), but your precision is preserved throughout.

Good discussion though. It has really helped focus my thinking for a project I'm working on.