Home > Sensors, Software > GPS and Dead Reckoning

GPS and Dead Reckoning

Dead: Having lost life; no longer alive
Reckoning: The act of counting or calculating

The practice of dead reckoning is common among accountants in a world filled with zombies. Many corporations want to know how many zombies are around and how they can best manage them. Considering zombies eating others result in more zombies, a position as a dead reckoning accountant can be quite lucrative. Strange isn’t it?

Actually, the term is likely from naval origins when external input was not available. Wikipedia has a good description:

Dead reckoning is the process of estimating one’s current position based upon a previously determined position, or fix, and advancing that position based upon known or estimated speeds over elapsed time, and course. While traditional methods of dead reckoning are no longer considered primary means of navigation, modern inertial navigation systems, which also depend upon dead reckoning, are very widely used.

Early naval navigators used the system to determine the position of the ship based on a previous position and course along with estimates of speed and changes in heading when readings could not be taken due to cloud cover or other factors. Essentially, they were making an educated guess about the new position.

Good thing we have GPS. Except, no, not so much. GPS isn’t a very reliable source of information. First off, its slow at 1 Hz updates. Secondly, its easily jammed or blocked by line of sight obstructions. Certainly, there are many new GPS units that have much faster update rates at 5, 10 or faster update rates. Sadly, many of them are not actually providing new satellite fixes….they are dead reckoning based the previous input. Not all but question those at higher rates, they are often only doing something you can do better locally.

GPS is based on a set of satellites to estimate a position on the ground. Each and every one of them are flying about the earth in a designated pattern with errors in the orbit. A few of them, 3 minimum, give you a fix on the ground to a certain degree of accuracy. Check your data sheets for the Circular Error Probable (CEP). It’s likely 2.5 meters or more.

Now, if you are SparkFun contestant, how wide are the roads around the building? If you are directly positioned in the center of the road with a 2.5 meter estimate and the fix is wrong, are you in the pond or trying to mate with the building? Put an X on the ground near your test site and see how the position changes if you check again in an hour, later in the day, tomorrow, etc. It’ll vary somewhat even throughout the day.

Unfortunately, it gets worse. Today’s GPS receivers are much better at getting fixes from satellites in suboptimal conditions. Like indoors and with marginal line of sight to the satellites. Excellent, right? Yes, and no. It’s great when you are looking for a rough position when you are in the woods and turned around. It is far from precise. When you are lost, a few hundred meters doesn’t matter a great deal.

If you are a robot relying on it to accurately position you in the world, it becomes rather critical. The GPS gives you some notional feedback in the form of the horizontal dilution of precision (HDOP). It can be utilized as an estimate for the accuracy of the position. Once again, the GPS unit is giving its best guess for the current situation.

Can it get worse? Yep. If you are reading in GPS data, grab it on one side of a large building, then run around to the other side. Obviously, the position will change but what else? The satellites in view will. Don’t believe me? Record that GPS sentence. Why is that important? The precision of the fix shifts as you change satellites. Worse, it causes “pops” in the position if you rapidly change from one set of satellites to a different set. With buildings and other occlusions, that happens a lot.

Guess what? The faster you change satellites, the worse that position estimate becomes. If you’ve tested a lot with raw GPS as a sensor, you’ve likely seen it happen. Will it screw you for the contest? Maybe, maybe not. It all depends on the set of satellites of view, which is constantly changing.

How does Dead Reckoning play into the equation? Well, that’s why our vehicles have an encoder to give us an accurate estimate of speed. Couple that with a change of heading based on the steering angle, and the vehicle can predict where it believes it should be. Errors creep into dead reckoning quickly as well.

If we can detect a major pop in position, smart decisions can be made to wait for the position to settle or to rely on the DR solution. Smarter people than me would feed it into a Kalman Filter and run off the results. Lack of precision makes robotics a lot of fun.

Categories: Sensors, Software
  1. March 6, 2010 at 1:00 am

    We were thinking of using the GPS but for the same reasons you mentioned + possible indoor issues we discareded it. We are going to use the compass on the phone and a wheel encoder. For this competition we think this will be enought.

  2. March 8, 2010 at 10:03 am

    I’ve observed the errors possible with a GPS, too — I once saw a 400m jump in position with my Garmin receiver on a clear day and no buildings for at least 2000m.

    For simplicity, I was hoping to get by with a GPS and, perhaps, a magnetic compass for my AVC entry. I can deal with bouncing off the curb a few times in exchange for a bit of simplicity. But, I cannot get my GPS (a LS20031 like yours) to reliably hold a fix. So, I suspect that your assessment is accurate … time to heat up the soldering iron again and add wheel encoders.

    Thanks for putting up this build log. I’m rather disappointed that SparkFun chose not to require build logs. I sent them mine (http://www.bluerwhite.org/tag/sparkfun/), but they did not publish the link.

    • March 8, 2010 at 3:58 pm

      I wish they would have required build logs as well. Ah well, I guess they decided it wasn’t necessary. Its always nice to share the suffering and joy during the process. I’ve added your site to our links page. Good luck, Peter.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: