Monday 3 June 2013

DEMYSTIFYING THE KALMAN FILTER - PART 1

THE ESOTERIC KALMAN FILTER


SLAM is a corner stone element of current day mobile robotics. The way to develop a map incrementally with increasing iterations is an essential part of mobile robots applications in surveys and in search & rescue efforts. At the very heart of SLAM is estimation theory which establishes an incrementally near correct map, often depending on the data fusion from two sensors. In the simplest scenarios it is (1) laser or sonar reading and (2) odometry.

Though SLAM is very commonly used in mobile robotics, however the mathematics of it does come across as cumbersome. The concept of Kalman filter, at the heart of this estimation is often seen as a jargon [1].

WHAT IS THE KALMAN FILTER ? -- A SIMPLE ILLUSTRATIVE EXAMPLE

Firstly, Kalman filter is not really a filter in the sense of chemical filtration  electronic signal filters or optical filters; it is a tool for estimation.

This is a simple example[2] to illustrate the Kalman filter, this is an one dimension system and has no element of dynamics or noise to it. In this example, consider that we have a bucketful of 100 ohm resistors, accurate to 1% RMS (1 ohm per 100 ohm) and we have an ohm meter with an accuracy of 3 ohm RMS random error on each reading. Selecting a resistor from that bucket, how can we estimate its resistance ?


There are 2 independent estimates, 


In order to get a good estimate, it is imperative to consider both these independent estimates. Hence a linear weighted fit, 


where the sum of the weights must total to unity. It can be shown[3] that for minimum variance, the optimal value is,


and the minimal variance for the system is ,


which can be conveniently written as;


Right now, this doesn't make much sense. However plugging in values will clarify the result. For the current example, 


For an initial estimate without any measurement, 100 ohm is the best estimate value for the resistance. 

For the first reading, 

hence if the ohm meter reading shows 95 ohms (which is rather unlikely), the best estimate will result in, 


99.5 ohms is a rather much more likely than 95 ohms.

For the second reading, the variance will change,


and,

the Kalman estimate is recursively related to the last estimate, 


The third recursion in a similar spirit will give,


With increasing number of recursions the variance reduces and tends to zero for a very large number of observations.

Thus, in a recursive notation,
 





in practice, the Kalman filter always consists of 3 recursive equations. However, for a 3 dimensional systems they take more complicated form.

REFERENCES
[1] Kalman's original paper, available online - http://www.cs.unc.edu/~welch/kalman/kalmanPaper.html
[2] du Plessis explaination of the Kalman filter, available online - http://digi.physic.ut.ee/mw/images/d/d5/Poormankalman.pdf
[3] Dudek and Jenkins, 'Computational Principles of Mobile Robotics'Cambridge University Press, 2012

No comments: