Location, Location, Location (Accelerometer)
By roger on Nov 10, 2008
I'd like to take this opportunity to talk through some issues that arise when new users come to Sun SPOTs. One of the first ones is that many of them assume that a Sun SPOT, with all its sensors, must know its location. There are few very reasonable thought processes that lead one to think this. One is that you should be able to infer relative position by dead reckoning using the accelerometer readings, and another is that several Sun SPOTs should be able to triangulate using radio signal strength. It certainly seems reasonable. In this post we'll focus on the accelerometer.
Unfortunately, dead reckoning is much more difficult that it might appear at first. Good, reliable location continues to be a difficult thing for these types of small devices. I've found myself responding to questions about this on the forums and in person often, so I thought I would collect my thoughts together here and just point people here when they have questions. Lets take the accelerometer case first and then we'll talk about radio signal strength next time around.
In physics terms, the accelerometer measures acceleration or change in speed. Speed is in turn change in position. Therefore, in calculus terms, the integral of acceleration is speed, and the integral of speed is position (or location). Generally, you can get the integral of the Sun SPOT accelerometer measurements by simply adding up the samples. For example, if you begin from standing still and accelerate at a constant 1 meter/second\^2, that means that after one second you will be traveling at 1 meter/second. After two seconds, you'll be traveling at 2 meters/second and so on. During that first second you accelerate from 0 to 1 m/s. If you assume constant acceleration you will travel .5 meter. In the 2nd second you will accelerate from 1 m/s to 2 m/s and so you will travel 1.5 more meters. So in the first 2 seconds you will travel 2 meters... and so on. It is pretty straight forward to calculate this. The graph shows an example of constant acceleration and the effect on speed and position over time.
That is all well and good, but here are the things that make this a bit more tricky. First is gravity. It is always trying to accelerate you toward the center of the earth at 1G = 9.8 m/s\^2. Fortunately for all of us, the earth gets in the way and stops us from just falling endlessly. The Sun SPOT accelerometer will measure the gravitational force while the Sun SPOT is at rest. Conversely, if you drop a Sun SPOT off a cliff, aside from the air resistance slowing it and the effects of spinning (I'll talk about this below), the Sun SPOT will experience no apparent acceleration (weightlessness) as it falls and is accelerated at 9.8 m/s\^2. How can this be? While it is sitting still the accelerometer will measure acceleration and while it is changing speed as it falls through the air it will measure nothing? This goes against the idea that the accelerometer measures a change in speed. So its accelerometer will measure 0 acceleration, but surely the speed and position will be changing as it speeds up toward the ground. (To understand what the accelerometer is measuring, check out the description at 45 minutes into this video) Well, it turns out that it is fairly easy to adjust for this mathematically. You simply subtract out the effects of gravity. If the Sun SPOT is on earth and the accelerometer reads 0Gs, you can assume it is accelerating at 9.8 m/s\^2. Similarly, if it reads 9.8 m/s\^2 down you can assume it is stationary with gravity pulling it down. So we just need to subtract 1G (9.8 m/s\^2) out of the acceleration reading. This works fine.
OK, now for the tricky parts. Of course, the big problem with subtracting gravity is knowing which way is down. It's easy for the Sun SPOT to calculate tilt when it is not accelerating, however, when other forces of motion are thrown into the accelerometer readings, the tilt calculations become more difficult.
A stationary Sun SPOT can use the 3D accelerometer to tell you quite accurately which way is down. If you accelerate that Sun SPOT laterally, that acceleration will confound the tilt calculation and make the Sun SPOT "think" it is tilted when it isn't.
Lets talk about centrifugal force http://en.wikipedia.org/wiki/Centrifugal. If you put the Sun SPOT on the end of a string and swing it around your head in a circle, the accelerometer will measure acceleration of 1G down, and many Gs outward away from you. The force the string exerts to turn the Sun SPOT in a circle around your head shows up in the accelerometer. This is centrifugal force that is essentially fighting the Sun SPOT's natural tendency to want to continue in a straight line (bodies in motion tend to stay in motion...). From the accelerometer readings, the Sun SPOT is unable to tell the difference between this spinning "fictitious force" (as centrifugal force is described) and true acceleration in a straight line. Now imagine that Sun SPOT that we dropped off a cliff. It should be happily reading 0Gs (you can read more about free falling Sun SPOTs and accelerometers here), but if it is tumbling on the way down, it won't. As the Sun SPOT tumbles and turns, it will induce centrifugal forces that will affect accelerometer reading. The accelerometer is not exactly at the center of mass of the Sun SPOT, so as the Sun SPOT spins in the air (rotating about the center of mass), the accelerometer will experience centrifugal force. A great example of this can be seen when my son and I threw Sun SPOTs around our backyard with a trebuchet (http://blogs.sun.com/roger/entry/sun_spots_and_trebuchets) where you can see the rotations of the Sun SPOT in the air. The Sun SPOT has no way to tell this type acceleration from the type that causes its position to change. You would need gyros (rotational sensors) to properly sense out this effect so that it can be subtracted from your calculations.
Additionally, to get from acceleration to position, as I mentioned before, you have to integrate twice. This means that errors you encounter compound. If you are off even slightly in the acceleration, the speed you calculate will be off and that will make your position even further off for that estimate and all future estimates. The next reading you take may also be off a little and get you a slightly incorrect speed which you will then use to calculate a distance which you apply to your already incorrect position to get a new position that will now be even further off. The Sun SPOT analog to digital converter that reads the accelerometer is reading instantaneous values from the accelerometer. The software then must interpolate between these readings by assuming a relatively smooth change from one reading to the next. Unless you can sample the accelerometer infinitely fast, (which Sun SPOTs can't) you'll miss some acceleration and your reading will be off. Furthermore, if there is vibration or noise in your readings, they can affect the accuracy of your results. Remember all these errors are additive. Thus it wont take long for your position calculations to be way off.
Thus accurately calculating distance from the accelerometer is almost impossible. I say almost because I can imagine a scenario where you could calculate position. If the Sun SPOT were constrained in some way so that its orientation never changed, for example, if we could assume that it was ALWAYS facing north, then we would not have the problem of rotational forces or tilt changes confusing our readings. Additionally, if the Sun SPOT were connected to a massive enough object to guarantee that the changes in acceleration were fairly smooth, then we shouldn't run into too much sampling error. Thirdly, if it would regularly get an absolute reading of some sort to adjust for the cumulative errors... then and only then can a Sun SPOT calculate its position using just the accelerometer.
So, if you want to calculate position, what you want is a SunSPOT based Inertial Measurement Unit (IMU) http://en.wikipedia.org/wiki/Inertial_measurement_unit. I don't know of anyone who has built such a device from a SunSPOT... yet! I've played with gyros from SparcFun (http://www.sparkfun.com/commerce/product_info.php?products_id=698) and they can be made to work (although I haven't tried to make an IMU. I connected that device through the A/D on the eDemoBoard, which was pretty straight forward. Getting it to deduce position is another matter. I'm sure there is a thesis in there for someone. IMUs generally have the drift problem unless they use some global positional information such as GPS. It's useful to have an application where there are some constraints to help counter the drift. We've been working with a group from Edinburgh that is building such devices in order to be able to track body movements. (BTW, they are not using Sun SPOTs for this) Because they know that the devices are connected to a person, they can apply the readings to a rigid body model of a person. They can be pretty sure that the person's upper arm is connected to their shoulder and thus constrain the motions appropriately. Its all about the constraints. After all, if they can deduce a car's position from an iPhone's accelerometer (http://dynolicious.com/index.html), there is hope. Certainly you should be able to do that with a Sun SPOT.
We don't have a gyro board planned at the moment, but it is certainly something that we talk about. We also have shown how to connect a GPS to a Sun SPOT for applications that need to get an outdoor position. Finding the constraints that help make your application work is the key here. Where there is a will, there is a way, so get out your bag of potatoes and teach your Sun SPOT to navigate.
In a future post I'll talk a little about the issues around using radios to infer location.