Embedded Files
After adding the navigation code described in "Getting from Point A to Point B" we decided to take the car out for some more extensive test runs. Overall, the car functioned as we expected and managed to drive from one point to another. But, we noticed that it was hard to get the car to drive in a repeatable way from one test run to another. Further, there seemed to be no obvious pattern that might point to a root cause. Instead, there was an assortment of symptoms that would appear in one test run, then mysteriously vanish in the next, only to return a few runs later. Here's a short list of the kind of odd behavior we observed:
After setting a waypoint using what appeared to be a very good GPS signal, the car would insist on driving to a point several feet away
The car would run reasonably straight when driving North, or South, but would swerve back and forth wildly, or steer off into the weeds when driving from East to West
After setting a set of waypoints, the car would steer as if the location of one, or more of these waypoints had shifted by several feet in one direction
My first assumption (which, as I'll explain more about later, turned out to not to be the primary issue) was that my GPS receiver was either defective, or not sensitive enough to get a reliable position reading. A few years back, Sparkfun did a comparative test of several of the GPS modules they sold at the time. Looking at their summary results gave me both some hope and some concern. First, it was clear that one or two of the modules they sold, such as the EM-406A and the LS20031 (actually, identified as a LS23060 in Sparkfun's article), seemed to do a reasonable job, even in the "Urban Canyon" section of the course. However, as I was already using the LS20031 in our car, I was puzzled why my results with it seemed to be so much worse than results reported in Sparkfun's article. I came up with several theories:
Some external factor, such as multi path reception, or improper placement of the module's antenna was degrading performance
A stupid and, as yet, undiscovered programming error was affecting the proper use of the GPS data (memories of the SoftSerial buffering issue)
I needed to add some sort of filtering process to the GPS data to weed out, or average bad readings
I needed to fiddle with some of the options I could select on the GPS module to improve it's performance in this application
At the time, I figured the best way to get to the bottom of the issue was to try out several different GPS modules. So, instead of engaging my brain to dig deeper into the mystery, I threw cash at the problem and ordered several different GPS modules to try out. The ones I bought are:
LS20031 (the original module I started with)
I'd previously discovered was that $GPGGA sentences also provided three additional fields of of information (Fix Quality, Number of Satellites, and "Horizontal Dilution of Precision", or HDOP) that could be used to discern the quality of the position fix used to generate the lat/lon values in each sentence spit out by the module. So, my plan was to compare these values from one GPS receiver to another and decide which seemed to provide the best data in conditions similar to what the car would experience in the race at Sparkfun. Midway through working on this, I discovered that the TinyGPS library had been updated to include new functions to get access to two of these values, Number of Satellites and HDOP. Here's an updated version of the loop() code from "Navigating with GPS" that reads and displays these values:
void loop() {
while (mySerial.available()) {
unsigned char cc = mySerial.read();
if (gps.encode(cc)) {
float flat, flon;
unsigned long age;
gps.f_get_position(&flat, &flon, &age);
Serial.print("Lat: ");
Serial.print(flat);
Serial.print(", Long: ");
Serial.println(flon);
Serial.print(", Sats: ");
Serial.print(gps.satellites(), DEC);
Serial.print(", HDOP: ");
Serial.print((float) gps.hdop() / 100.0);
}
}
}
The other value, Fix Quality, is not currently available from TinyGPS, but is used by the code to determine if a valid position fix is available. However, it's fairly easy to modify TinyGPS to export this value and I'll describe how to do this in a later section. However, before we get into that, let's look at the HDOP and number of satellites values to see what they can tell us about the quality of a GPS position fix. The number of satellites values should be self explanatory, as the more satellites the GPS receiver is locked onto, the more information the GPS receiver has to work with. But, if you read a bit more about how GPS works, you'll discover that the position of the satellites relative to the GPS receiver is also important. A GPS receiver using triangulation to compute its position relative to the reference points provided by the satellites it sees in the sky. However, when several satellites are directly overhead, instead of lower on the horizon, the geometry is less favorable and the accuracy of the position fix becomes less reliable. The HDOP value tries to boil this down into a convenient metric, as follows:
Values of 1, or less indicate an ideal satellite configuration
Values of 1-2 are not ideal, but still excellent for most uses
Values of 2-5 may be good enough to use for navigation, but this may depend on other factors
Values above 5 are not really good enough for our purposes
One of the first things I noticed when began using the HDOP and number of satellites values to evaluate the various GPS modules I'd bought was that nearly all the modules needed a decent warmup time before they would settle down on a stable position fix. Part of this is due to the fact that not all of my modules came equipped with a battery to preserve the module's memory when powered off. When switched on cold, a GPS module needs to obtain Almanac and Ephemeris that it uses to calculate the position of each satellite is located in the sky. This data becomes useless over time, buy having a backup battery can greatly shorten the time it takes to get up and running. However, even with a battery, most of the receivers would still take a minute, or so to settle on a solid position fix.
Using the code above, I was able to observe the HDOP and satellites values reported by the different GPS modules while I used them in different conditions and I was rather surprised by the results. First, several of the modules, such as the LS20031 and Adafruit were easily able to obtain a very good GPS lock in my downstairs apartment. That was especially surprising given that, in addition to having a second apartment unit above me, my unit is also slightly recessed below the local terrain and has other adjacent apartments that block signals from the South and West, and a sloped hillside to the North. Both modules are based on MediaTek chip sets, so perhaps that accounts for their ability to get a position lock in these conditions. Most of the time, these modules reported being locked on 6, more more satellites and frequently reported seeing 8, or 9, which is quite impressive, IMO.
The second thing I noticed was that, after a warmup/ settle in period, nearly all the modules reported HDOP values less than 1, which indicated they could see enough satellites in positions in the sky to enable the module to compute an ideal position fix. Only the SkyTraq ST22 and the Venus638FLPx seemed to have trouble obtaining a decent signal inside my apartment building. However, both modules reported equally good HDOP and number of satellites values when used under clear sky conditions. So, this left me scratching my head for an explanation to the erratic performance of our car.
Understanding WAAS
The one position quality indicator I hadn't yet investigated was the Fix Quality value that I could not access through TinyGPS. However, it's quite easy to read this value in the raw $GPGGA message. Looking at a typical sentence, such as:
$GPGGA,024255.000,3255.3559,N,11706.5162,W,0,3,,185.4,M,-35.4,M,,*7B
The '0' value shown in the enlarged font is the Fix Quality value. According to the NMEA 0183 Standard, this value is interpreted, as follows:
0 = invalid
1 = GPS fix (SPS)
2 = DGPS fix
3 = PPS fix
4 = Real Time Kinematic
5 = Float RTK
6 = estimated (dead reckoning) (2.3 feature)
7 = Manual input mode
8 = Simulation mode
Of these, only the first 3 values (0-2) seem to be possible responses from consumer level GPS modules (a value of 3, for example, is only possible with a military grade receiver.) A value of 0 indicates the receiver cannot report a position fix, a value of 1 indicates the receiver can report a position fix using the Standard Position Service (SPS.) A value of 2 indicates a Differential GPS fix, which means that the receiver is able to offer an improved position fix by comparing it to a the fix obtained by a stationary GPS receiver. The term Differential GPS actually covers a variety of methods that can used to make this correction, but method used by consumer receivers is given the acronym WAAS, which stands for Wide Area Augmentation System. WAAS was developed and promoted by the FAA as a way to improve aircraft navigation, which needed greater position accuracy for things like automated landing approaches.
FAA's WAAS Logo
WAAS works by transmitting a signal from a geostationary satellite that is completely separate from the signals broadcast by the GPS satellites, but in the same frequency band. This WAAS system collects reference data from a network of fixed ground receivers and then computes correction information which is relayed to to a GPS receiver via one of the a geostationary satellites that broadcast the WAAS data. Using this data, the receiver is supposed to be able to correct the accuracy of its position fix to within 0.9 to 1.3 meters. Without WAAS, the accuracy of standard SPS signal is said to be in the range of 2.5 to 4.7 meters, so clearly it would be advantages to know if our car's GPS receiver was able to get a WAAS lock, or not.
After investigating this, I found that many GPS receivers "seemed" to require a special command(s) to enable reception of WAAS data. I say "seemed" because I was never quite able to determine whether this feature was enabled by default, or not, as the specifications for some receivers did not address this issue. So, I decided that the safest course of action was to assume it was not enabled and always send the command(s) to enable WAAS at the same time I set the other GPS module parameters, such as the update rate (see "Navigating with GPS" for more details on sending commands to the receiver.) For the MediaTek-based recivers, the code you need to add to the init() section of your code is, as follows:
mySerial.print("$PMTK313,1*2E\r\n"); // Enable to search a SBAS satellite
mySerial.print("$PMTK301,2*2E\r\n"); // Enable WAAS as DGPS Source
The first command tells the receiver to search for a satellite that supports the Satellite-Based Augmentation System (SBAS), which is the overall system on whichi WAAS is based (it's bit more complex han that, but I'm skipping a lot of technical details to stay focused on the important points.) Then, the second command enables the receiver to use this information to correct the GPS fix into a DGPS fix. Note: there are some fine points here, too:
Some receivers, such as those based on the MediaTek chip set can only make use of the WAAS correction information if the receiver is set to an update rate of 5 Hz, or less. I found this tidbit buried inside a spec sheet after spending countless hours trying to figure out why I could not get a DGPS lock at the 10 Hz rate one of my receivers is capable of working at.
Some receivers, such as ones based on the SkyTraq Venus chip set require that commands be send in a binary format rather than a text-based format.
Therefore, I strongly recommend that you spend some time getting familiar with the specifications and features available for your GPS module and that you experiment with, and test your receiver before you dismiss it as defective, as I did initially. Hopefully, much of what I explaining in this section will be applicable to you, but your mileage may still vary.
It Still Drives Erratically
I wish that I could report that, after all that research into GPS and WAAS, and after all the testing I did that I could report that I was able to solve all our car's navigation problems. Sadly, this was not the case. In fact, even though I expect to get better accuracy from WAAS, the car still seemed to veer off in unexpected directions even after I was careful to make sure I had a WAAS lock and HDOP values less than 1 before recording waypoints and running navigation tests. I began to suspect that perhaps I was expecting too much from the GPS receiver. Perhaps I need to use some local correction capability, such as odometry, as a crosscheck on the GPS position. Or, perhaps there was still some error in the code that hours of analysis and debugging had failed to find. As it turns out, this was not far from the truth...
A chance observation proved to be a clue that set me on the path to finding a possible culprit. In order to try to visualize the problem, I started using an excellent GPS mapping service called the GPS Visualizer. Using this tool, I was inputting coordinates I'd gathered from my tests in the field to try and see if the positions shown on the map lined up with where I'd taken the same reading using one of the GPS receivers. At one point I happened to mistype the last digit of the longitude value, as derived from the floating point value I had recorded in the EEPROM memory in the car. When I correct this digit, which was only off by 1, I happened to notice that the position shown on the map jump by what appeared to be a very large distance. This was a completely unexpected result but, after a few minutes experimenting with other vaules, I was able to confirm this observation. The strange thing was, I did not see a similar jump when changing the last digit of the latitude value. It, too, seemed jump by greater distance than I expect, but only by a matter of inches rather than several feet in the case of longitude. What could explain this?
Curse You Floating Point Math
But, when I looked again at the values I was working with a few days later, the sudden flash of insight that hit me. Being in San Diego, the integer portion of my latitude value was 32 and for longitude the value was -117. Because TinyGPS returns latitude and longitude as 32 bit float values, I had lost an entire digit of precision in the fractional portion of the longitude value. I can't really blame TinyGPS for this, as 32 bit floating point arithmetic is all that the Ardunio platform supports. And, in truth, I had considered this issue before, but had discarded it as a concern based on faulty reasoning. Having considered fractional precision, my mistake had been in failing to realize that the integer portion of the number, of necessity, steal bits of precision from the fractional portion as the integer portion grows larger.
Having depended on TinyGPS to handle the conversion of $GPGGA sentence values into decimal degree values, I now went back and looked at the raw GPS data format a bit more closely. In the NMEA format, latitude and longitude values are really output as an integer portion, which indicates degrees, and a second portion which subdivides each degree into minutes. So, a value such as 3723.2475, is actually two values, 37 degrees and 23.2475 minutes, concatenated together. So, in theory, GPS latitude and longitude values can indicate a position down to .0001 minutes of arc which, at the equator, is down to an accuracy of about about 7 inches. At my location in San Diego, the accuracy improves to about 6.2 inches per .0001 minutes of arc.
In contrast, when converted into a floating point value, as the diagram above shows, there are only 23 bits available to contains the entire value. Using the floating point math convertor tool, I incremented the LSB of the binary representation of -117.0 degrees and this produced a stepwise difference of .00000763 degrees. Multiplying this by the distance covered by one degree of arc at latitude 32 degrees (3,720,210 inches) produces a distance step size of 28.4 inches. That's over 2 feet and a value that's 4.6 times less precise than that conveyed by the data in the $GPGGA message parsed by TinyGPS. Is this loss of precision enough to explain our car's erratic behavior? Perhaps, but I figured I first needed to work out a fix for this precision problem and then retest the car before I could reach any firm conclusions.
I considered writing my own math routines, or a double precision version of TinyGPS but, in the end, the simple solution seemed to be to just adjust the input values in a way that would preserve the most fractional precision in the float values for latitude and longitude. If, for example, I pretended that my longitude was the Prime Meridian (0.0), but kept my actual latitude, the result of all my computations, such determining the compass heading to steer to, would work the same as before, but have more digits of precision available in the fractional portion. So, I set about investigating how to modify TinyGPS to support this.
Precision Loss in TinyGPS
As I started examining TinyGPS in detail, I discovered that it did not maintain it its internal latitude and longitude values in float format. Instead, it converts the raw GPS value into a base 10, fixed point format that it stores in a 32 bit long value. Then, when needed, it converts this fixed point value into a float value by dividing it by 100,000. However, when I looked into how TinyGPS converted the raw GPS value into fixed point, I spotted a problem. Here's the C code for TinyGPS' parse_degrees() function (reformatted slightly), which is where this conversion takes place:
unsigned long TinyGPS::parse_degrees() {
char *p;
unsigned long left = gpsatol(_term);
unsigned long tenk_minutes = (left % 100UL) * 10000UL;
for (p = _term; gpsisdigit(*p); ++p)
;
if (*p == '.') {
unsigned long mult = 1000;
while (gpsisdigit(*++p)) {
tenk_minutes += mult * (*p - '0');
mult /= 10;
}
}
return (left / 100) * 100000 + tenk_minutes / 6;
}
The important part is the last line of code where it takes the value "tenk_minutes" and divides it by 6. This code is trying to convert minutes of arc into degrees, but it does so at the cost of truncating the value into a modulo 6 value. What this means is that, as the last digit of the raw GPS value increases by one, the computed value will only change every 6th step. Here's a way to see this numerically as a table that shows the raw GPS value, and the net result when converted into a decimal number (assuming no precision loss due to the float issue described above):
Notice how, for raw GPS values 11705.8170-11705.8175, the converted result from TinyGPS is always 117.09695. In effect, this means that the result output from this conversion step has 1/6th the resolution of the raw GPS data. Scaled up to real world coordinates, this comes out to a distance step size of about 37.2 inches at latitude 32, which is worse than the problem created by the loss to precision from conversion to a float value. So, it became clear that I needed to fix this problem before trying to deal with the float conversion issue. But I found that, by making a few simple adjustments to TinyGPS' parse_degrees() function, I could greatly improve the accuracy of the conversion. Here's my modified version, with the changes I made highlighted in red:
unsigned long TinyGPS::parse_degrees() {
char *p;
unsigned long left = gpsatol(_term);
unsigned long tenk_minutes = (left % 100UL) * 100000UL;
for (p = _term; gpsisdigit(*p); ++p)
;
if (*p == '.') {
unsigned long mult = 10000;
while (gpsisdigit(*++p)) {
tenk_minutes += mult * (*p - '0');
mult /= 10;
}
}
return (left / 100) * 1000000 + (tenk_minutes + 5) / 6;
}
The original code was failing to take advantage of the full precision available in a long value. So, by moving the fixed decimal point one place to the left, it now has room to keep one more digit of precision in the tenk_minutes value, as well as round it properly before dividing by 6 to convert minutes into degrees. Of course, since we've now changed the fixed point format, we also have to make an offsetting change to the function TinyGPS uses to convert this fixed point format into a float value. This function, named f_get_position(), which is also found in the TinyGPS.cpp file. The adjusted version of this code looks like this:
void TinyGPS::f_get_position(float *latitude, float *longitude, unsigned long *fix_age) {
long lat, lon;
get_position(&lat, &lon, fix_age);
*latitude = lat == GPS_INVALID_ANGLE ? GPS_INVALID_F_ANGLE : (lat / 1000000.0);
*longitude = lat == GPS_INVALID_ANGLE ? GPS_INVALID_F_ANGLE : (lon / 1000000.0);
}
The changes (shown in red) consist of simply increasing the constant 100000.0 to 1000000.0 in order to move the fixed decimal point one digit to the left so that it matches the new fixed point format returned by the improved parse_degrees() function.
Fixing the float Conversion Step
<coming soon>
Page updated
Google Sites
Report abuse