## [TUT] [THEORY] What is a Kalman Filter?

9 posts / 0 new
Author
Message

(1) Why am I bothering to write this?

Every now and again, somebody poses a problem on the forums with a reply like "Just use a Kalman Filter!"

Problem is, few people understand what a KF is, let alone how to use one, let alone how to use one effectively! This tutorial aims to be a gentle introduction as to how a KF works, without going into the maths behind it. It's equation free!

If you want to know the nitty-gritty details, wikipedia [1] has an excellent overview of the equations. If you're desperate for more theory, see Brown & Hwang [2] or various references on the web like this one [3].

If you "just want code", you're missing the point! The code bit is just some matrix equations. The hard bit is modeling it correctly.

---------------------------------------------------

(2) So what is a Kalman Filter?

First and foremost, it's not a filter! Certainly not in the sense that it is explicitly designed to block certain frequencies and pass others through. Instead, a KF is actually an estimator [4] that is designed to make a best-guess at a signal in the presence of noise from a statistical sense, rather than for a specific frequency response. It's much more related to State Space Control and Least Squares Regression than Fourier techniques.

There's two parts to the KF:
(a) An estimation of your dynamics (for this example, a vehicle's position and velocity); and
(b) A noisy measurement of your position/velocity.

A KF works out the Best Possible* compromise between guessing your motion and measurements from a noisy sensor. Yes, even GPS is noisy (about 5m is position, 5cm/s in velocity for good GPS conditions) although much less than other position sensors.

In your KF you'll have a model of your motion. Let's say, traveling at a constant velocity, which is a reasonable assumption for a car on a highway. However, it's not perfect - there will be small accelerations, movement left and right, etc - this is "noise" on your motion estimate.

-------------------------

(3) When do I use a Kalman Filter?

In short, if you don't think you need one, you probably don't! One example that comes up every so often is using a KF for attitude determination from gyros and accelerometers where a complementary filter does the trick quite nicely.

A KF comes into it's own in the following scenarios:
(a) Where the motion of the platform is reasonably well known, measured with a noisy sensor.
(b) Where there are other noise types on a sensor other than white Gaussian noise**
(c) Where there are several different sensors measuring (directly or indirectly) the same thing ***
(d) Where measurements can drop in and out ****
(e) Where you need to know how certain you are of your state (e.g. error on your position/velocity).

If one of those are true, maybe you should consider a KF.

-----------------------------------

(4) So how do you actually do the filtering?

You need to track a few things for a KF:

Now you know this, here's the process:

(1) From your current estimate of your position and velocity, guess where you're going to be at your next step from your motion model. However, because you don't precisely know your motion, your uncertainty will also grow. We're predicting your next state and next state covariance.

(2) Take a measurement (sometimes called an observation) of your position and velocity from your sensor at the time that you're predicting for. Because there is noise on the sensor, it is an estimate of your next state, and the noise forms your measurement covariance which is a description of how accurate you think your sensors are.

(3) Work out the difference between your measurement and what you predicted your next position/velocity was. This is your measurement residual (or innovation).

(4) Here's the tricky part. Work out the uncertainty on that difference between your measurement and the predicted position - your innovation covariance. We need this to work our which one we trust more - the measurement or the motion model.

(5) Calculate the Kalman Gain, which is the factor on how much we weight the motion model vs the measurements - it comes from the residual and the innovation covariance we calculated before. This is the real "magic black box" of the whole process.

(6) Correct the prediction of your next state by how much of the measurement you trust. That is, take that magic Kalman Gain, multiply that by your residual and add that to your predicted next state.

Repeat steps 1-7 forever.

The hard part of a KF is not the equations - it's just some matrix multiplications - it's in the modelling of your sensors and your platform dynamics. It can only be described by linear equations - one without sin(), cos(), x^2 or pretty much anything else. It's very rare indeed that a system is purely linear - most of the time you've got to use some tricks to make it linear, or do something funky like an Extended Kalman Filter.

------------------------

(5) I want to know more!

If you have a copy of Matlab or Octave (Octave is completely free), there are plenty of tutorials where you can see this in action - Matlab Central has about half a dozen implementations.

---------------------------

(6) Can it be done on an AVR?

Longer Answer: It's been done on (for example) the MicroNav project [5]. In general, it can handle low-sample rate implementations where there aren't too many states to estimate and aren't too many measurements to process. Matrix Inverses are pretty nasty operations!

--------------------------------

(7) Can I copy this tutorial?

-- Damien

---------------------------------

Footnotes:

* Best Possible: For a KF, it can be in the "least square error", "expectation maximisation", "Best Linear Unbiased Estimator (BLUE)" or "minimum variance unbiased (MVU)". Take your pick - they're all Googleable.

** Other types of noises exists on many sensors. For example, gyros and accelerometers have a slowly and randomly changing bias with time that can be modelled in a KF, if there is some other sensor that makes them observable (e.g. a GPS/INS implementation)

*** For example, a wheel odometer can be used at the same time as GPS, and can be used where GPS is unavailable (e.g. blocked by buildings)

**** GPS being blocked by buildings is a good example. Or, if doing a raw GPS implementation, each satellite is a different measurement. The number of satellites seen changes constantly.

---------------------------------------------------

References:

--------------------------

Edit History:
1.0 - Initial Issue
1.1 - Typos and minor cleanups
1.2 - Fixed heading numbers as per comment. Thanks!

Last Edited: Sat. Oct 10, 2009 - 04:54 AM

Damien,

Housekeeping comment only .. other than saying thanks!

Your paragraphs are mostly introduced as numbered questions, eg

(1) Why am I bothering to write this?
(3) So what is a Kalman Filter?
(4) When do I use a Kalman Filter?
etc ...

What happened to (2)?

Using this approach might cause you grief when/if you want to insert a new subtopic or revise the sequence of discussion in the future.

Just my \$0.01 ... not worth 2 cents.

Cheers,

Ross

Ross McKenzie ValuSoft Melbourne Australia

valusoft wrote:
Damien,
What happened to (2)?

Oops... fixed :) Thanks.

Quote:

Using this approach might cause you grief when/if you want to insert a new subtopic or revise the sequence of discussion in the future.

Word processor cross-referencing has spoiled me.

-- Damien

How can we use this in an accelerometer?

kumailxp wrote:
How can we use this in an accelerometer?

The first question is what do you want to estimate?

The accelerometer can potentially give you some measurements, but what are the states that you're trying to estimate?

Quote:
The first question is what do you want to estimate?

I want to estimate the acceleration in X,Y and Z-axis?

Secondly, A also want to estimate 'tilt' using gyro.

Hey Damien. I'm new into the embedded world, but am willing to learn a lot. For my final year project I was thinking of using an accelerometer mounted near the centre of gravity of a small model RC car, and thought that I could just simply 'integrate' those readings in order to obtain velocity.

Obviously further research suggested that accelerometers by themselves are little use, as they cannot tell the difference between the gravitational acceleration and any other. So I ended up reading about IMUs, that come pre-loaded with a Gyroscope and an Accelerometer, and thought that this was probably a better implementation as to what I was trying to measure. Your tutorial is really helpful as a generic understanding, and because I wanted to focus on the dynamics of a vehicle during a turn, I guess that a Kalman filter would be better suited rather than a complimentary filter.

So now whats left is for me to put pen down to paper and later start some coding on this. But do you think I'm headed in the right direction so far?

Raag90 wrote:
Hey Damien. I'm new into the embedded world, but am willing to learn a lot. For my final year project I was thinking of using an accelerometer mounted near the centre of gravity of a small model RC car, and thought that I could just simply 'integrate' those readings in order to obtain velocity.

Obviously further research suggested that accelerometers by themselves are little use, as they cannot tell the difference between the gravitational acceleration and any other. So I ended up reading about IMUs, that come pre-loaded with a Gyroscope and an Accelerometer, and thought that this was probably a better implementation as to what I was trying to measure. Your tutorial is really helpful as a generic understanding, and because I wanted to focus on the dynamics of a vehicle during a turn, I guess that a Kalman filter would be better suited rather than a complimentary filter.

In a recent thread, I have commented on creating an "Inertial Navigation System" (INS) from SparkFun grade sensors.

Short answer: You'll get mere seconds of useful navigation, even with a high-fidelity vehicle model. On a good day. If you're lucky.

Raag90 wrote:

So now whats left is for me to put pen down to paper and later start some coding on this. But do you think I'm headed in the right direction so far?

So, what should you do for a final year project if you're interested in the area?

An integrated GPS/INS system is perfectly valid with SparkFun-grade sensors. It's reasonably complex for a final year project (more a Master's thing), but if you're a good student and willing to learn quite a bit then you'll pull it off.

Hopefully, you university library will have this text which is an excellent self-contained book on GPS/INS integration, including Kalman Filtering. If not, harass the engineering librarian about getting it. You can directly code an entire GPS/INS directly using equations from the book.

So what will you need to do?
1. Buy a GPS and IMU off-the-shelf if you don't already have one. I have no idea what sort of budget you have, but http://www.sparkfun.com/products/10125 combined with http://www.sparkfun.com/products/9436 should get you started.

Or, if you have a friend that likes hardware (and a budget), tell them to design a board with this (Trimble make survey-grade GPS receivers), three gyros and an acceleromter talking to your favourite microcontroller pushing data out of a serial port. These are about as good as you'll get without spending enormous amounts of cash.

2. Get software running to talk to each of the sensors and log data on a PC.

3. Code up the Kalman Filter equations in MATLAB. In this book there are numerical values that you can unit test.

4. Write the INS mechanisation straight out of the first book I recommended. You can run it through some data you collected earlier, but expect it to shoot off yonder straight away.

5. Here's the tricky part: Code up the GPS/INS integrated Kalman Filter. It's about 50 equations or so in total. Lots of typing.

6. Hook up the GPS corrections to (4) and (5).

7. Implement all of the above on a real-time system (probably a reasonably beefy ARM or something).

Volia! High Distinction and employers hammering at your door :)

-- Damien