Location, Location, Location (Accelerometer)

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.

Potato-Nav

The process of calculating your new position based on your old position and some estimates of how your are moving is called dead reckoning. I learned a bit about this in my sailing navigation classes where it is important to be able to estimate your speed and direction, when your GPS goes out on a foggy day, to avoid the boat eating reefs that populate many coastlines. Techniques involve logging your speed and compass heading and using these readings along with the last known position to calculate your new position. This form of navigation is known to be difficult and inaccurate because of accumulated error and has caused many a ship to become lost. Because each estimated position is based on the previous estimated position, errors tend to accumulate. Boat captains all know that as soon as you can, you should find some absolute source of position (such as sighting a known location, using stars or the Sun, or just fixing the GPS). One of my favorite forms of navigation in the fog without a GPS is called "potato navigation" which is an ingenious (and most likely fictitious) way of getting absolute navigational input even in fog that is as thick as vichyssoises. You post someone on the bow of the boat with a bag of potatoes. They throw a potato in a forward direction and listen for the splash, then repeat. If at any time they hear a thunk instead of a splash after throwing a potato, the boat must be about to hit the shore and so it would be a good time to turn. :-) ...but I digress.

 

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.

 Users Rogermeike Library Application-Support Ecto3 Cache Affba7Fc-Ebd8-44B0-Abb4-07A0C237C917
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.

200811061500OK, 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.

200811061506

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.

Comments:

great stuff. more, more! :)

Posted by rama on November 21, 2008 at 02:27 AM PST #

Thats really great! What about the issues about radio? Cant wait for that!

Posted by Jay Mahadeokar on December 30, 2008 at 07:12 PM PST #

Roger, I'm recently new to the world of accelerometers. I'm needing to gather the actual relation between the voltage that the accelerometer outputs and the actual acceleration (ft/(s\^2) or m/(s\^2)). However, I am unable to find any documentation (even on accelerometer data sheets) that will explain this relation even in terms of capacitance.

Any help at all would be greatly appreciated.
-Nick

Posted by Nick on April 15, 2009 at 09:26 AM PDT #

Oh by the way...I think I found a bug in the Radiogram protocol of SPOT..Not exactly sure yet..Will have to explore further...University exams going on now..so no time till Friday...

Loved your blog

Posted by Sandip Dev on April 22, 2009 at 02:33 AM PDT #

What about other sensors that could be connected to the spots? Proximity sensors can determine relative distance, but not (absolute) direction. I am researching different types of sensors, but haven't found one (or a combination) that looks like it will work. I am looking for something that can be used in a swarm of nodes such that each node knows the approx. (as accurate as possible, obviously) location of the other nodes \*within a defined arena\*. I realize the limitations imposed by an unconstrained territory, but hope that restricting it down to a defined course will grant me some options!

Thanks!!

Posted by Jason on July 27, 2009 at 09:19 PM PDT #

Jason,
For an individual node to know its motion it must have sensors for every degree of freedom in its movement. Because the Sun SPOT devices can rotate, but have no rotational sensors, they cannot track their own movement. Furthermore, its good to have some absolute sensors to help minimize the effect of accumulated error. So, 3D accelerometers, 3D gyros and 3D magnetometers with a reasonable amount of computation should do well. For relative distance you could use something like an audio chirp. You could measure the difference in propagation time between the audio chirp and a radio packet and get a distance. With enough devices and relative distances you could use a relaxation algorithm to calculate relative location.
Hope this helps

Posted by Roger on July 28, 2009 at 01:45 AM PDT #

Hi!

I am a PhD student in Brazil working on a thesis about intelligent control of an AUV (Automonous Underwater Vehicle).

I am now currently seeking CPUs or MCUs to control and sense the AUV and came across the Sun Spot. After reading about the problems involved in accurately calculating the position of the AUV I am almost giving up of using it. But since it is going to swim slow and with small movements in its x axis (because of ballast) I want to know your opinion about it. Do you think it is feasible?

Because of battery the AUV won't be diving much time. I guess maybe 2 hours at most. How would the integration work?

Posted by Hildebrando on August 20, 2009 at 05:52 AM PDT #

Hildebrando,

I think the key is that you need more than just the accelerometer. You need either a magnetometer or a gyro and preferably both. Then at least you would know what directions your acceleration readings should be applied to. Without that you can't do much. Dead reckoning is hard and subject to cumulative error. The Sun SPOT is a reasonable platform and certainly flexible enough to handle quite a few sensors other than the ones that are built in to it.

Usually for AUVs, you would want some sort of vision system or some other absolute system to supplement so that you can adjust based on some landmarks etc.

Best of luck!

Posted by Roger on August 20, 2009 at 07:47 AM PDT #

Hi Meike... Thanks for your answer.

Now I have another doubt. The learning algorithm I intend to implement will be based on look-up tables or in function approximation. The amount of memory needed for both is much different. Look-up tables will depend on discretization of the states and actions of the AUV and tend to be huge. Function approximation, on the other hand, doesn't demand much memory. Since I haven't decided about the algorithm, and since the Spot has 512MB of RAM I want to know if it is possible to add more RAM to it if needed.

Posted by Hildebrando on August 27, 2009 at 04:54 AM PDT #

Hildbrando,

No you cannot add more memory to the Sun SPOT. There will be a new version out in a few months with more memory, but for now 512KB of RAM is all you get. There is 4MB of flash that you can use for some things... and you can add more with a special board (https://spot-eflash.dev.java.net/), but generally, this is an embedded platform with restricted memory.

Posted by Roger on August 31, 2009 at 12:29 AM PDT #

Really nice article!!

You mentioned that you collaborate with a research group in Edinburgh that is involved with body motion detection. Is there a link to the group or publications to read more? I am a PhD student working on body motion detection. Thank you!

Posted by Alex on September 16, 2009 at 01:04 AM PDT #

The Edinburgh project is part of the Speckled Computing project under D.K. Arvind. I don't know what they have published on the matter, but you can contact them here: http://www.specknet.org/

Posted by Roger on September 16, 2009 at 04:03 AM PDT #

For those of you who are interested, I have posted a follow-on article about determining location from radio signals here:

http://blogs.sun.com/roger/entry/location_location_location_radio

Enjoy!

Posted by Roger on September 16, 2009 at 04:05 AM PDT #

Nice :)

Thanks

Posted by Sun Location on October 13, 2009 at 07:44 AM PDT #

Great article, im in south africa working on a project that uses accelerometer to preform accident analysis , I have got my speed calculations fairly correct but i am unable to determine when im going forward and when im going backward for now ie (velocity) do you have any sugestions

Posted by Jacob George on December 05, 2009 at 07:51 PM PST #

Do u plz show the mathematical calculation for the device, or just explain the mathematical model for the device on which this device is based upon.

Posted by Saad Shaoor on February 08, 2010 at 02:34 AM PST #

That was very informative for my project. I am doing my masters and I am doing a project on designing a vehicle independent speedometer. For this I am doing research on gyros and accelerometers. I have gained enough knowledge towards achieving my goal although I would have to research more info on the accelerometer. If you could give me any sites where I could find more useful info on the gyros and accelerometer that would be helpful and of course your suggestions would be of great value to me.
Thanks Roger

Posted by Sharath on September 17, 2010 at 11:26 PM PDT #

Hi,
This is a great post, but it still doesn't answer me everything...

I've been reading about accelerometers for a day now and I still have doubts about what I want to make work. I know all the acceleration, velocity, distance stuff, but the practical (jokes:)) problems are always not so quite easy.
I am working with an acc that sends me 1 byte, 2G range. It's a tiny thing and I wanted to use one axis only and move the mouse on the screen. Since I have a lot of positive/negative acceleration values, and I try to do a running integral (take last value + time difference\*velocity and same for velocity from acceleration) the result is hectic. Not to mention the whole trying to get a proportion with pixels... I've added the compensation for unit of the byte to the m/s2..

Can this even be done, getting the right direction from just one tiny signed byte of acceleration? Is physics failing me that bad that I don't see it?

Thanks for any advice...

Posted by memememe on December 01, 2010 at 11:50 PM PST #

Gyro-free IMU project using two 3D accelerometers to distinguish between translation and rotation without gyro: http://www.ece.uci.edu/~chou/bsn10.pdf

Posted by rmic on January 04, 2011 at 02:07 AM PST #

Post a Comment:
Comments are closed for this entry.
About

Roger Meike, Senior Director of Area 51 and Director of Operations Sun Labs

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today