Kalman Filtering

The Kalman Filter is a very awesome tool used in robotics and many other control applications. I am writing this post to see if I can write about something technical and make it interesting, which is much harder than writing about something not technical and making it interesting. It’d be really cool if you all could bear with me and try to understand it.

The Motivation

Before I explain exactly what a Kalman Filter is and does, let me explain why it exists. Imagine this scenario:

• You are a robot trying to figure out exactly where you are.
• Ideally, you know where you are because you have some sort of GPS system, or any other location sensing device, but your devices are error prone.
• Ideally, you know exactly how far you travel because you can record how many times your wheels spin. However, wheels slip, and you don’t actually know exactly how far you’ve traveled.

Ideally, the GPS and wheel errors are small. But lots of small errors can add up over a long period of time. And since robots recompute their location very often, you will accumulate a lot of small errors.

So how do we figure out exactly where we are when our sensing equipment is faulty? The Kalman Filter is a mathematical formula that allows us to make a very good guess.

How it Works

Logically speaking, the GPS and wheel errors are not the same value every time. For example, the GPS will read 1 meter too far north on one measurement and 0.5 meters too far east on another. Otherwise, the errors could easily be corrected in the machine and wouldn’t actually be errors. Therefore, the errors have an average and a standard deviation, just like the test scores in any class. The smaller the standard deviation, the more “correct”, or definite, the average is. So in a class, if 10 people score the average, the standard deviation will be smaller than if only 3 people score the average. The Kalman Filter assumes that the average is 0 and that the standard deviation is a positive number, which are both reasonable assumptions.

Before using the Kalman Filter, we need to measure the standard deviations of the GPS and the wheels. Usually the people who make the wheels and the GPS do this themselves by testing it and seeing how often and by how much it is wrong.

While the robot is running, the robot will compute where it is using two readings: where the wheels say it is and where the GPS says it is. Often times, the two readings will be different. Then, knowing the standard deviations of the wheels and the GPS, the Kalman Filter is a mathematical formula that will compute where the robot most likely is. If the GPS has a smaller standard deviation than the wheels, the position that the filter outputs will be closer to where the GPS says the robot is than where the wheels say the robot is.

For those of you who are mathematically inclined

I will state the mathematics that go into the filter without proof or derivation, because I don’t think that I can explain the proof well. If you want to see the proof, here’s a link to Kalman’s original paper, and a link to a book that does a fairly good job of explaining things.

I’ll also point you to the Wikipedia article, which I think is quite accurate.

Final Remarks

And that, my readers, is a simple explanation of one of the coolest concepts that I’ve learned in class this year.

I hope it all made sense. I really do. I’m not the best at explaining things, so I’m allowing comments for this post to clear up any confusion.