Go Down

Topic: How does Ardupilot do it?? GPS accuracy issues !!! Distance Calculations (Read 5728 times) previous topic - next topic

afclewis

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.

wkuace

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

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.

UnaClocker

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?
Brian from Tacoma, WA
Arduino evangelist - since Dec, 2010.

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?

ccfreak2k


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

rocketgeek


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

Higgy

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.

DCContrarian

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:
Code: [Select]

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.

afclewis

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

BenF


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




afclewis

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

DCContrarian



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.

BenF

Quote

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.

Quote from: 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).

Quote from: 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.

Quote from: 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.

Quote from: 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.

Quote from: 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.

DCContrarian


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:
Quote

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.

Go Up