The Extended Kalman Filter: An Interactive Tutorial

In working with autopilot systems like OpenPilot and Pixhawk I have frequently come across references to something called an Extended Kalman Filter (EKF). Googling this term led me to several different web pages and reference papers, most of which I found too difficult to follow. So I decided to create my own tutorial for teaching and learning about the EKF from first principles. This tutorial assumes only high-school-level math and introduces concepts from more advanced areas like linear algebra as needed, rather than assuming you already know them.

The tutorial is currently about 2/3 complete.  I still need to introduce linear algebra concepts for sensor fusion, and then nonlinearity for the EKF.  But in the open-source spirit of "release early, release often", I'm posting this now, in the hope that people will try it out and provide comments.

• Thanks for the detailed comments, Tim.  I appreciate the insights from someone who knows the field so well, and I'll try to incorporate your suggestions, with credit given to you for the changes.

For what it's worth, my own experience as a teacher has shown me that a relentless focus on absolutely precise use of terms tends to lead to confusion and frustration, and eventually to create a priesthood of insiders, which is very much the sense I get from the literature on the Kalman filter: hence perhaps the flurry of DIY teaching activity you've observed from your students.  The simplicity and elegance of the ideas gets buried in the notation and sidebar/footnote "but it's really not X; it's X+(Y/N -2k) for very large values of N and small values of k" kind of thing.  Students, not having the mathematical maturity to understand this kind of comment, get freaked out and flee. I was a able, for example, to understand your valid argument without stumbling over your incorrect use of "you're" for "your".

So although I disagree that I've "added to the confusion", I will make an effort to be clearer and more precise.

• "Googling this term led me to several different web pages and reference papers, most of which I found too difficult to follow. So I decided to create my own tutorial..."

I've heard this so many times from my students... I didn't understand what I read on the internet, so I decided to make up my own explanation... and post that on the internet.

While I commend your drive to gain knowledge of recursive filters, you've used several misleading terms and descriptions in your tutorial that don't align well with accepted terms in formal literature. Thus, you're simply adding to the noise on the topic and generating more confusion. Yes, it's difficult for novices (particularly those without a formal mathematics background) to understand this topic and by all means, simplify explanations to allow the reader to develop a good mental model, but try to bring them up to a level at which they can comfortably read more advanced material on this topic (in particular, by feeding in the correct terms and descriptions where possible... or providing "extra detail" in a side bar).

For example, you describe p_k as the "prediction error". Formally, it's the covariance of the estimation process at step k. The prediction error would be the true state minus the estimate. p_k is then actually the average of the squared prediction error. So, yes, it's related to a "prediction error" and can be used as a surrogate (i.e., a larger value of p_k indicates a larger value, on average, of prediction error) but it's not the same thing... if you wanted to give it a lay name, it could be described as a confidence measure... the larger the value of p_k, the less confident we are of the estimated state value being the "true value".

Ultimately, you should keep in mind (and this is something that engineers tend to ignore frequently) that you're state is a stochastic variable/vector (an instantaneous value of a stochastic process) and it doesn't have a true value!!! The estimate is actually the maximum likelihood value for the process model describing the state, based on the observations up to that time. Given simplistic assumptions about the noise (being Gaussian), then this state estimate corresponds to the mean value of this variable/vector at a given time. Engineers tend to ignore the fact that the state estimate is a probability distribution and they just focus on a single value drawn from this distribution... and then use p_k to tell them how "flat" or spread the distribution is (since it's a measure of the average width of the distribution).

Finally, what you've described so far in your tutorial is the basic Kalman filter and not the Extended Kalman Filter... please make this distinction early in your tutorial and then, when you get to the EKF, you can highlight the difference between that and the basic filter.

• Thanks for the tutorial Simon! Kalman filters are really powerful tools and developing a GPS/INS filter is a nice, relevant way to get started. Sure they've been implemented before but some fundamental understanding is even necessary to use existing libraries. People shouldn't forget that Kalman filters are designed for general estimation problems rather than just GPS/INS fusion so they could be used to estimate anything drone related, such as platform aerodynamic parameters, but doing so would require decent understanding, which your tutorials shall provide.
• To me, understanding this stuff is too difficult in terms of time.  It also feels like I'm constantly reinventing the wheel.

This EKF stuff has been done over, and over, and over.  Everyone wants to write their own EKF and I just can't fathom why.  They always have problems, and there's always a long period of bugs, poor performance, etc..

What would be WAY more useful to me is learning the basics of how to USE existing code and libraries.  Far better to point out the important aspects of integrating these complex maths, rather than trying to understand them in detail.

Think of all the time wasted here on the EKF.  There were libraries already available, and STmicro even had a ready to go solution with their iNemo code.  All of that time could have been better spent developing new software features and hardware.  Trying to beat a large corporation staffed with an army of engineers, professional uC programmers, and PhD math experts at their own game seems downright silly.

Teaching someone how to change a tire is always going to have a better payoff than teaching them how a steel belted radial is designed and constructed.

• Moderator

Thank you very much for your excellent tutorial.  You should be awarded an honorary PhD in Dronology.  I didn't completely understand it, but I await you next release. Is there a mailing list I can subscribe to?

• @Simon D. Levy, i would be very thankful for Python example. Thanks again! :)

• Thanks for the comments, everyone -- especially @Ludovic for catching the typo!  I appreciate the problems pointed out by @Nikola and @MikeRover and am trying to strike a balance between formulas (for engineers) and code (for programmers).  In some cases I've annotated the the formulas with actual JavaScript code used to generate the plots -- will try and do this for other formulas too, maybe even have links to code (C, Python, Matlab). Also, for the final pages, I plan to show actual EKF C code, annotated with the corresponding formulas.

• i almost missed this post! Thanks man!!!!

• Great job, tanks a lot!