Dead reckoning with accelerometer & gyro. Possible?

I have a 3 axis accelerometer and a 3 axis gyroscope. I've been tasked with developing a dead reckoning system using this hardware.

Essentially what's needed is for me to develop some code to track the position in 3d space of the board in real time. So if I start with the board on a table and lift it 1m upward, I should be able to see that movement on the screen. Rotations need to be taken into account too, so if I turn the board upside down half way through the same movement, it should still show the same 1m upward result. The same should also hold for any complex movement over a period of a few seconds.

Ignoring the maths needed to do calculate and rotate vectors etc, is this even possible with such a low cost device? As far as I can tell, I won't be able to remove gravity with 100% precision, which means my angle relative to the ground will be off, which means my vector rotations will be off, which leads to an incorrect position measurement.

I also have noise from the accelerometer and gyro bias to account for.

Can this be done?

-
It can be done up to the accuracy allowed by the sensors. Position errors will accumulate over time. Whether the accuracy is enough for your project depends. – Wouter van Ooijen May 15 '14 at 11:26
The advanced maths are what are going to make the project possible. You'll need to use quaternions, a Kalman filter, and either a ZUPT or ZARU scheme. From there, yeah, you can track it accurately for several seconds. I speak from direct experience. – Samuel May 15 '14 at 11:49
I have a wonderful quote from Lord Kelvin hanging on my office wall for some decades: "Quaternions came from Hamilton...and have been an unmixed evil to those who have touched them in any way. Vector is a useless survival... and has never been of the slightest use to any creature." – Scott Seidman May 15 '14 at 12:49
@ScottSeidman Quaternions aren't so bad if you think of them in terms of rotations around unit vectors. Then you only need a bit of trigonometry to convert to/from quaternion form. – JAB May 15 '14 at 15:41
@JAB, obviously they (or some other approach) are necessary as rotations don't commute, putting some rather interesting nuances on the math. – Scott Seidman May 15 '14 at 15:44

The answers and comments you're getting are excellent of course, but I can add a little color.

For what its worth, our sensorineural system uses much the same tools, and doesn't always get the answer right! We have 3D accelerometers (the otolith organs) and 3D "gyros" (angular velocitomers, the semicircular canals), and yet we suffer from all sorts of illusions when the system is not able to get the right "answer", like the elevator illusion and the oculogravic illusion. Often these failures occur during low-frequency linear accelerations, which are difficult to distinguish from gravity. There was a time when pilots would nose-dive into the ocean during catapult takeoffs on aircraft carriers because of the strong perception of pitch resulting from the low frequency acceleration associated with the launch, until training protocols taught them to ignore those perceptions.

Granted, the physiological sensors have some different frequency cutoffs and noise floors than MEMS sensors, but we also have a huge neural net thrown at the problem -- though little in the way of evolutionary pressure to solve the problem correctly at these low frequency extremes, so long as catapult launches are fairly rare ;-).

Picture this common-sense "dead reckoning" problem that many have experienced, though, and I think you'll see how this carries over to the MEMS world. You get on a jet, take off in North America, accelerate to cruising speed, cross the ocean, decelerate and land in Europe. Even removing the tilt-translation ambiguities from the problem, and assuming zero rotation, there would be very little hope of a real implementation of a double integration of the acceleration profiles yielding a position profile anywhere nearly accurate enough to tell you you've reached Europe. Even if you had a very accurate 6 axis gyro/accelerometer package sitting in your lap during the trip, that would have its problems as well.

So that's one extreme. There's much evidence suggesting that for everyday behaviors animals use a simple assumption that low-frequency accelerations that are detected are probably caused by reorientations with respect to gravity. A combination of gyros and accelerometers that have broader frequency responses than our inner ear can solve the problem much better, of course, but will still have problems in the extreme due to noise floor, thresholds, and such.

So, for short epochs with non-trivial accelerations, dead reckoning with the right instrumentation is not so bad a problem. For long term, with small accelerations, and low-frequency accelerations, dead reckoning is a big problem. For any given situation, you need to figure out where on that spectrum your particular problem lies, and how accurate your dead reckoning needs are in order to determine whether the best you can do is good enough. We call that process engineering.

-
Thanks for that illuminating answer. However it leaves me wondering a few things: 1) what do you mean by low-frequency accelerations? 2) If the problem were reduced from 3D position to lateral displacement (ignore Z), is that easier? and 3) What about for a slow movement in seawater, where the effect of gravity is reduced? Any pointers to reading material on these calculations would be appreciated. – achennu Jun 29 at 22:23

The main issues with dead reckoning that I found while doing a senior design project similar to yours is that an accelerometer only measures acceleration. You have to integrate once to get velocity plus a constant C. Then you have to integrate again to get position + Cx + D. That means that once you calculate position from an accelerometer's data, you end up with an offset, but you also have an error that grows linearly with time. For the MEM's sensor I used, within 1 second, it calculated itself to be at least a meter away from where it actually was. In order for this to be useful, you generally have to find a way to zero out the errors very often so that you avoid the buildup of error. Some projects are able to do this, but many are not.

Accelerometers do give a nice gravity vector that doesn't rise in error over time and electronic compasses give orientation without accumulating error, but overall the dead reckoning problem hasn't been solved by tons of money spent by the navy on tons of sensors on ships. They're better than what you can do, but the last I read, they still found themselves to be off by 1km when traveling 1000km. That's actually quite good for dead reckoning, but without their equipment, you won't be able to achieve anything close to that.

-

You'll also have bias in the accelerometers and noise in the gyros to deal with as well.

And gravity shouldn't introduce errors in the angle measurements; on the contrary, the gravity vector provides an "absolute reference" that helps you zero out the accumulated bias of the "pitch" and "roll" angles.

Yes, what you want to do is possible, but the poor performance of low-cost MEMS devices means that errors will accumulate quickly — both bias changes and the "random walk" generated by the noise (in both the accelerometers and the rate gyros) will cause the results to depart from reality within seconds or minutes.

To fix this, you need to incorporate additional sensors into your system that don't suffer from these kinds of errors. As I mentioned above, using the gravity vector angle is one way to correct for some of the gyro errors, but you need to be aware of when you have an accurate gravity measurement (the systems isn't otherwise being accelerated) before you can use it.

Another way to correct for angular drift is to incorporate a magnetometer to measure the Earth's magnetic field. Magnetometers have relatively large errors, but they don't suffer from long-term drift.

Correcting the position errors created by the drift components of the accelerometer readings requires an absolute position reference of some sort. GPS is commonly used (when available), but you can use other sensors as well, such as barometers (for altitude), odometers (if you have wheels on the ground), ultrasonic or infrared range sensors, or even image sensors.

Regardless of what combination of sensors you end up using, all of this data needs to be "fused" into a self-consistent software model of the system state, which includes not only the current position and attitude, but also estimates of the current bias, scale factor and noise levels of the sensors themselves. A common approach is to use a Kalman filter, which can be shown to provide an "optimal" estimate (i.e., the best available estimate) of the system state for a given set of sensor readings.

-

The short answer is "not exactly". The long answer is that you can form statements such as "Given my gyroscope readings, I am 95% confident that the device has been rotated between 28 degrees and 32 degrees since my last reading".

The problem is that you end up collecting data about a noisy differential equation. For an angular gyroscope measuring angular velocity you have the noisy diff eq $$\frac{d\theta(t)}{dt} = r(t)$$ and in the case of an accelerometer $$\frac{d^2p(t)}{dt^2} = r(t)$$ where $r(t)$ is the value of your sensor at time $t$.

These "noisy" differential equations usually go under the name "stochastic differential equations" where the noise is assumed to be the white noise generated via a random walk. The math can be generalized to other situations where the noise is not from a random walk. In any particular case, the noise will have distribution that can be determined experimentally, the parameters of which will depend on your specific device and application. Because of noise accumulation, no matter what you do to get good estimates over relatively long time spans you will always need to periodically calibrate to a known position. Examples of fixed references are home bases, compass readings, and gravity.

If you decide to pursue this avenue, you have to decide a few things:

• What is an acceptable level of error? Do you want to be 95% confident it is within one degree after 2 seconds or do you want to be 80% confident that it is with in 5 degrees after 2 seconds?

• Take some readings from your gyroscope/accelerometer. This can be used to calculate the empirical distribution of the noise which estimates the real noise. Use this to solve your noisy differential equation and calculate your confidence intervals.

• From the above, it should be clear how the reading accuracy (variance) from the data sheet affects the solution to your noisy differential equation. It will also be clear how it affects your confidence intervals.

• Choose a device with acceptable parameters so that you get the confidence intervals you wanted in the first step. You may find the device accuracy parameters you want/need do not match what is available and/or your budget. On the other hand, you may be surprised at the results you get for cheaper devices.

-
The problem (or one problem) lies in that the accelerometer is sensitive to more than p(t). It's also sensitive to changes in theta around certain axes. – Scott Seidman May 15 '14 at 15:57
I agree. That is why it is always best to use vectors when doing any analysis of a multiparameter system. The generalization from vector-valued stochastic processes from the single variable case is trivial compared to the rest of the issues. – SomeEE May 15 '14 at 16:05