10 ms·

Quick explanation of how a Kalman filter works

334 points by xchip 9y ago

f1notformula1 9y ago
This is the most intuitive introduction to Kalman filtering that I've ever seen. Even just reading that part was the most enlightening 2-minutes of my entire month. Kudos to the author!
- xchip 9y ago
  Much appreciated! :)
YSFEJ4SWJUVU6 9y ago
The page breaks back button.
- knolan 9y ago
  Seems fine for me on MacOS Safari.
  - ly 9y ago
    It's broken for me on MacOS Firefox
piracykills 9y ago
Interesting - I don't have the strongest math background so I'm usually somewhat intimidated by topics like this, but this makes it seem like a fairly simple weighted average based on squared error values like in standard deviation? I assume this would also only work on a normal distribution too? Makes it seem a lot more approachable than many people have made it sound to me, but I may be horribly misunderstanding still.
- dbcurtis 9y ago
  I struggled a long time trying to get past all the matrix math that the usual Kalman filter tutorial starts out with. KF's make a lot more sense if you start from an example. By the end of the example, you realize that matrix math simplifies the notation hugely. But without the intuition about what it is doing for you, it doesn't help much -- at least it doesn't help me much. So... my over-simplified touch-stones for KF's: 1. Everything is a Baysian quantity -- a mean (best guess) and a std. dev. (confidence). 2. You have a model of the system state. 3. You have some sensors, and you have some model for the accuracy & precision (noise) in the measurements. Now, two rules: 1. The model runs open loop and at a regular cadence: "Tick tock, tick tock, the model updates on the clock." Of course, since you are running open loop, your confidence in every value of the model gets worse with each iteration (std. dev. grows). How much you adjust (reduce) the confidence is based on the precision of the system and the control inputs. 2. Sensors readings are applied as they come in: "Use'em if you got'em." So.... now the moving average part... if you are twice as confident in your current estimate as you are in the reliability of the new measurement, do a weighted average of 2/3 of the current estimate and 1/3 of the sensor. This is why the confidence is carried along for all state values and sensor readings. Of course compute the weights of the moving average according to the current confidence values with every update. And that is about 103% of what I know about Kalman filters :)
- deleted 9y ago
  [deleted]
- ramzyo 9y ago
  That’s exactly right - new measurements (observations) or state predictions (estimates based on the assumed system model) are weighted based on the ratio of the standard deviation (uncertainty) of that observation/measurement to the historical standard deviation of the model to that point in time. For the closed form equations of the KF to work, you have to assume a) all measurements and parameters in the state model can be approximated by normal distributions with known standard deviations and means b) the underlying system model is linear. If you can’t assume b), then as the author mentions you can approximate the non-linear model with a linear one by taking the Jacobian and evaluating it at each step, and use the slightly modified EKF algorithm to bring everything together into an estimate of the system’s underlying state. As an aside a nice property of particle filtering (a different approach for localization and SLAM) is that there’s no linearity assumption. A nice property of both particle filtering and the KF/EKF is that the Markov assumption holds. This simplifies the underlying mathematics, as well as benefits the implementation on a computer by reducing time and space complexity required to evaluate the algorithms at each step.
fermienrico 9y ago
I remember struggling with understanding Kalman filters (and Particle filters). I found [1] to be an amazingly clear explanation: [1] http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/ http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures...
- mlevental 9y ago
  ya this is a very good one.
- blt 9y ago
  Additionally, this video made particle filters crystal clear to me: https://www.youtube.com/watch?v=aUkBa1zMKv4 https://www.youtube.com/watch?v=aUkBa1zMKv4
- jshprentz 9y ago
  Yes, that was discussed here. https://news.ycombinator.com/item?id=10042050 https://news.ycombinator.com/item?id=10042050
signa11 9y ago
actually, iirc, there is a very cool document by ramsey (i guess) which attempts to provides a simple and intuitive derivation of the Kalman filter without going too deep into mathematics...
ssivark 9y ago
Nice summary. I think of the concept at a slightly higher level of abstraction: It's just Bayesian inference to update the posterior. A theoretical model gives an estimate of what the state of the system should be (call that the "prior"). A sensor measurement gives an independent estimate of the state (call that the "likelihood"). Composing (multiplying) the two gives the posterior. Further, in this formulation it doesn't really matter what you call the prior or the posterior. You can easily combine estimates from many different sources/sensors. Kalman filters are just the special case where the likelihood and prior are both Gaussian -- the distributions can be specified with a couple of numbers, and there is a simple closed-form expression for composing them. More generally, one can use all the tools available for Bayesian inference.
- civility 9y ago
  > It's just Bayesian inference to update the posterior. I've had this discussion with a number of smart people (math PhDs and so on) over the years, and I've never gotten a good explanation. I understand in the very abstract sense how Kalman filters (and particle filters and so on) can be seen as Bayesian, but when it gets to actually applying Bayes' theorem it really gets complicated very fast. For instance, if you're estimating a 3D position (that will be A) and your measurements are some 2D subspace (these will be B), the least squares approach works nicely (normalized products of Normal PDFs). However, I'm not sure I understand a single component of the expression P(A|B) = P(B|A) P(A) / P(B) in this context. What does A|B or B|A even mean when A is a 3D Gaussian and B is 2D? What are the dimensionalities of these operations? What does it mean to divide a product of pdfs? I don't expect an answer, but I always wince a bit when I see Bayes in this context. For Normal distributions, I prefer thinking of it as least squares.
  - ssivark 9y ago
    It's Bayesian because we are estimating a (posterior) distribution for the state of the system, rather than just a "point" estimate. Restricting to only the Gaussian distribution (while a nice example) is losing the forest for the trees. > However, I'm not sure I understand a single component of the expression P(A|B) = P(B|A) P(A) / P(B) in this context. What does A|B or B|A even mean when A is a 3D Gaussian and B is 2D? What are the dimensionalities of these operations? What does it mean to divide a product of pdfs? I'm not able to understand why any of that is bothersome. Suppose A is the system's state (x,y,z) and B is the sensor reading (measures just the projection along the x-axis, such as a depth measurement). Since the sensor is not perfect, it could generate a range of readings for any given position of the object, specified by p(B[x]|A[x,y,z]) -- suppose you're give one value of B which is sampled from that distribution (say that was a Gaussian with standard deviation sigma). Given that value, you need to estimate the likelihood p(A|B). Alternatively, you can imagine performing variational inference for p(A|B) in the family of Gaussian distributions (which happens to contain the true distribution in this case). Whichever way we go about it, p(A|B) is a Gaussian with the same standard deviation sigma, centered at the measured B. (Intuitively, we can see that a measurement B will constrain the "x" component of A but not the other two coordinates) p(A) is the "prior" you get as an extrapolation from your knowledge of the system's past state. However complicated/nonlinear the system's evolution function, you can find p(A, t) either as a closed form expression, or by doing simulations, etc. (typically from p(A,t-1) but note, for example, that this general formulation can be used even if your system's dynamics does not satisfy the Markov property). If you have both p(A|B) and p(A) manifestly in the form of probability density functions, multiplying them is easy. At the end of this process, it is good enough to have an un-normalized posterior for A, which specifies the relative probability of different states. Dividing by p(B) is equivalent to normalizing the candidate posterior distribution. More generally, if the prior and the likelihood are specified by moments, or by some variational parameters, or by simulations, we can think of other ways to combine them.
ramzyo 9y ago
This is a very nice breakdown of Kalman Filtering. One slight correction - Kalman Filtering is one approach to solving the SLAM problem, but SLAM doesn’t require a KF. A particle filter, for example, can be used to solve the SLAM problem. For anyone interested in further resources to better understand the intuition behind KFs, I’ve found this resource incredibly valuable (although a little pricey): https://www.amazon.com/Kalman-Filter-Beginners-MATLAB-Examples/dp/1463648359/ref=br_lf_m_zuvo8fyr45xsoyk_ttl?_encoding=UTF8&s=books https://www.amazon.com/Kalman-Filter-Beginners-MATLAB-Exampl...
- bcaine 9y ago
  Another absolutely fantastic resource is this Jupyter Notebook based textbook on Kalman Filters and related topics: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... An addition to your correction: there are many other ways to solve the SLAM problem beyond (kalman/information/particle) filters. Optimization based approaches are very popular (search terms: Graph SLAM, Factor Graphs, Pose Graphs).
  - ramzyo 9y ago
    True! I don’t find too many people out there who know about this stuff. Any interest in trading battle stories through DM? Would be interested to know what you’re working on and where you’ve been!
- xchip 9y ago
  Good point, I'll update the article to reflect that Kalman is not the only approach to solve SLAM.
albertTJames 9y ago
Very cool way of introducing kalman filters
IshKebab 9y ago
> those readings represent gaussians and combining them means multiplying them I don't think he means multiplying surely? That part is unclear.
- mlevental 9y ago
  how else would you combine PDFs?
  - IshKebab 9y ago
    Ah I realised he meant the product of the two PDF's but it sounded like he meant the PDF of a the product of two normally distributed random variables. Which would make no sense.
  - vinchuco 9y ago
    with Adobe Acrobat ;D specifically, it's referring to the multiplication rule of probability (or counting).
- haskellandchill 9y ago
  Why does combining mean multiplying? I got lost there. I get that you want to average/weight the two values.
eggie5 9y ago
also useful for incorporating noisy GPS sensor readings! I tried to do this in an undergrad autonomous vehicle but failed at the time :(
rsp1984 9y ago
We also do the opposite, and we use our IMU to better estimate the position of those features/clues. This is exactly what SLAM does, at its core it is just a Kalman filter with the twist that each time it finds a reliable visual clue it treats it as a sensor and makes it part of its state, a thing that allow us to tell our position much better and build a map. Some nitpicking here: There are some SLAM systems and flavors that use a Kalman filter as the main estimator under the hood but most are either hybrids or separate the tracking and map optimization (using batch / bundle adjustment methods). Digging a little deeper here I think it's important to mention that a Kalman filter is just a recursive least squares estimator, and is in fact equivalent to an Information Filter (which, IMO, is much easier to understand if you're already familiar with linear regression / LS systems). In fact a Kalman filter is just a fancy mathematical reformulation of an Information Filter that allows you to save quite a bit of computation time in case each observations is low-dimensional compared to your state.
deleted 9y ago
[deleted]
ianstallings 9y ago
I wish I had this summary quite a few years ago. I ended up buying aeronautical software textbooks and trying to glean the information from those to figure out how to integrate multiple IMU inputs. I learned that real world IMU use in navigation is pretty ugly and has to be supplemented due to constant errors. This can be particularly difficult when flying. In my case I used other sensors, such as a GPS. But a strictly IMU-only approach to lengthy navigation is, AFAIK, impossible. Either way, good write up.
- colechristensen 9y ago
  There are good IMUs that can be used for dead reckoning (and, if an old professor is to believed, watching the thermal expansion of a building over the course of a day) but they're hard to come by and extraordinarily expensive.
- tnecniv 9y ago
  > I learned that real world IMU use in navigation is pretty ugly and has to be supplemented due to constant errors. This can be particularly difficult when flying. In my case I used other sensors, such as a GPS. But a strictly IMU-only approach to lengthy navigation is, AFAIK, impossible. Yeah IMU error can be annoying unless you shell out $$$, but this issue occurs with many other kinds of sensors as well. One common trick is to treat the IMU error as another state variable that is evolving over time. It won't eradicate the compounding error, but it will reduce the amount of calibration necessary.
- xchip 9y ago
  I'm glad it helped, this encourages me to write more explanations of tricky subjects :)
- caf 9y ago
  The used to use IMU-only navigation to steer submarines and lob ballistic missiles across the world during the early Cold War.
- ramzyo 9y ago
  Depends on the quality of the IMU. With a MEMS IMU (what’s in your smart phone and what’s cost effective for most consumer or industrial products today) yes, it’s impossible. Too much drift as a result of process variance in MEMS manufacturing and the “runtime” noise of the IMU itself. With a precision machined IMU, like something you’d find in a submarine or pre-GPS aircraft, totally possible. There’s a YouTube video (would have to dig for the link) showing a military plane in the 1950s flying transcon NYC to LA solely on IMU dead reckoning and arriving with 1/8 mile drift or something ridiculous. The IMU probably weighed a few hundred pounds and cost many hundreds of thousands, if not millions of dollars, though.
theoh 9y ago
Another intuitive intro, previously: https://news.ycombinator.com/item?id=12648035 https://news.ycombinator.com/item?id=12648035
gnachman 9y ago
How do you know the variance of your sensors? Do you have to experiment in a controlled environment?
- xchip 9y ago
  Good question, yes, you measure it when the rocket is on the ground.
RosanaAnaDana 9y ago
Hmm. Could probably hammer this into a form applicable for a raster, where the previous 'instance' is a linear interpolation via Roberts cross or some such.
laythea 9y ago
I used to work at a company that did Dynamic Positioning systems for vessels and oil rigs and I worked on the periphery software systems running with a Kalman-based algorithm there. Didn't work on the Kalman stuff then, but I do think its cool what they can achieve and have always been interested. I will add this to my reading TODO. Thank you.
SatvikBeri 9y ago
Great explanation! If you want a very detailed deep dive into Kalman Filters, I found this sequence of videos really helpful: https://www.youtube.com/watch?v=CaCcOwJPytQ https://www.youtube.com/watch?v=CaCcOwJPytQ It's 55 short videos, each one going over a specific topic or example.
AceJohnny2 9y ago
I love this. I've idly tried to understand the Kalman filter forever (ever=10yr+), and always encountered explanations that threw you straight at the linear algebra[1]. (yeah, even "quick" or "simple" explanation). This explanation starting from the conceptual is great, and finally provides the needed foundation for me to understand the rest. [1] huff not that I couldn't understand the linear algebra, just that I, uh, didn't have time for that... >_>
- xchip 9y ago
  Thanks, I wrote this because I had been in stuck in that same situation for a ages too
randyrand 9y ago
More gain 'k' explanation. 'K' determines how much you weight you give sensor A and sensor B. A gain of 1.0 means B is weighted 100% and A is 0%. Gain of 0.5 means each gets 50/50 weight. Look at the maths and notice how when the gain is 1.0, the mean just becomes the mean of B.
- xchip 9y ago
  yeah, calling it 'gain' is confusing since that keyword is mainly used for amplifiers.
- caf 9y ago
  Notice also that if you replace k with (1-k) then you get the same results, but with a and b swapped.
rweba 9y ago
Here is another "simple" explanation: https://rweba.livejournal.com/446326.html https://rweba.livejournal.com/446326.html It's definitely WAAAY oversimplified, but it gives the first idea: The "filter" just cleverly averages the noisy real data at time T with the Kalman estimate from time (T-1).
xchip 9y ago
Kalman experienced people, just wondering, what did you use the filter for? And, what are you guys working on nowadays?
- bit1 9y ago
  An aircraft's Flight Management Computer uses a Kalman filter to combine the data from all available sensors (GPS, IMU, altimeter, ADC, VOR, DME, etc.) to compute the position of the aircraft.
  - caf 9y ago
    A GPS itself uses a Kalman filter to combine the position estimates from many satellites as well.
- ramzyo 9y ago
  Robot localization and related sensor fusion problems
loxias 9y ago
This is a positively fantastic explanation. One of the best I've seen despite being so short. Minor nitpick: It might be a bit more clear if the terms "F", "s", "v" were explicitly defined, as well as a sentence explaining the matrix M inversion. It's really great, but when I read "our prediction formula F could be as simple as s = v*t_dot" I immediately think "F? was F defined earlier? Did I miss it? Also what is s?". [overall, really great explanation, bookmarked]
dennisgorelik 9y ago
The inventor of Kalman Filter: https://en.wikipedia.org/wiki/Rudolf_E._K%C3%A1lm%C3%A1n https://en.wikipedia.org/wiki/Rudolf_E._K%C3%A1lm%C3%A1n Born: Rudolf Emil Kálmán May 19, 1930 Budapest, Hungary Died: July 2, 2016 (aged 86) Gainesville, Florida
nerfhammer 9y ago
This seems to use measurement and average interchangeably? a measurement is an instantaneous "average"? if you figure out a decayed moving average as an "average"... why not just use that smoothed value directly? what do you even need variance for?
shaklee3 9y ago
I posted this a few days ago, but I think it's the best intro to Kalman filters I've ever seen: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
jquast 9y ago
much like a baby bird learns to fly

334 points by xchip 9y ago

This is the most intuitive introduction to Kalman filtering that I've ever seen. Even just reading that part was the most enlightening 2-minutes of my entire month. Kudos to the author!

xchip 9y ago
Much appreciated! :)

YSFEJ4SWJUVU6 9y ago

The page breaks back button.

knolan 9y ago
Seems fine for me on MacOS Safari.
- ly 9y ago
  It's broken for me on MacOS Firefox

piracykills 9y ago

Interesting - I don't have the strongest math background so I'm usually somewhat intimidated by topics like this, but this makes it seem like a fairly simple weighted average based on squared error values like in standard deviation? I assume this would also only work on a normal distribution too? Makes it seem a lot more approachable than many people have made it sound to me, but I may be horribly misunderstanding still.

dbcurtis 9y ago
I struggled a long time trying to get past all the matrix math that the usual Kalman filter tutorial starts out with. KF's make a lot more sense if you start from an example. By the end of the example, you realize that matrix math simplifies the notation hugely. But without the intuition about what it is doing for you, it doesn't help much -- at least it doesn't help me much. So... my over-simplified touch-stones for KF's: 1. Everything is a Baysian quantity -- a mean (best guess) and a std. dev. (confidence). 2. You have a model of the system state. 3. You have some sensors, and you have some model for the accuracy & precision (noise) in the measurements. Now, two rules: 1. The model runs open loop and at a regular cadence: "Tick tock, tick tock, the model updates on the clock." Of course, since you are running open loop, your confidence in every value of the model gets worse with each iteration (std. dev. grows). How much you adjust (reduce) the confidence is based on the precision of the system and the control inputs. 2. Sensors readings are applied as they come in: "Use'em if you got'em." So.... now the moving average part... if you are twice as confident in your current estimate as you are in the reliability of the new measurement, do a weighted average of 2/3 of the current estimate and 1/3 of the sensor. This is why the confidence is carried along for all state values and sensor readings. Of course compute the weights of the moving average according to the current confidence values with every update. And that is about 103% of what I know about Kalman filters :)
deleted 9y ago
[deleted]
ramzyo 9y ago
That’s exactly right - new measurements (observations) or state predictions (estimates based on the assumed system model) are weighted based on the ratio of the standard deviation (uncertainty) of that observation/measurement to the historical standard deviation of the model to that point in time. For the closed form equations of the KF to work, you have to assume a) all measurements and parameters in the state model can be approximated by normal distributions with known standard deviations and means b) the underlying system model is linear. If you can’t assume b), then as the author mentions you can approximate the non-linear model with a linear one by taking the Jacobian and evaluating it at each step, and use the slightly modified EKF algorithm to bring everything together into an estimate of the system’s underlying state. As an aside a nice property of particle filtering (a different approach for localization and SLAM) is that there’s no linearity assumption. A nice property of both particle filtering and the KF/EKF is that the Markov assumption holds. This simplifies the underlying mathematics, as well as benefits the implementation on a computer by reducing time and space complexity required to evaluate the algorithms at each step.

fermienrico 9y ago

I remember struggling with understanding Kalman filters (and Particle filters). I found [1] to be an amazingly clear explanation: [1] http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/ http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures...

mlevental 9y ago
ya this is a very good one.
blt 9y ago
Additionally, this video made particle filters crystal clear to me: https://www.youtube.com/watch?v=aUkBa1zMKv4 https://www.youtube.com/watch?v=aUkBa1zMKv4
jshprentz 9y ago
Yes, that was discussed here. https://news.ycombinator.com/item?id=10042050 https://news.ycombinator.com/item?id=10042050

signa11 9y ago

actually, iirc, there is a very cool document by ramsey (i guess) which attempts to provides a simple and intuitive derivation of the Kalman filter without going too deep into mathematics...

ssivark 9y ago

Nice summary. I think of the concept at a slightly higher level of abstraction: It's just Bayesian inference to update the posterior. A theoretical model gives an estimate of what the state of the system should be (call that the "prior"). A sensor measurement gives an independent estimate of the state (call that the "likelihood"). Composing (multiplying) the two gives the posterior. Further, in this formulation it doesn't really matter what you call the prior or the posterior. You can easily combine estimates from many different sources/sensors. Kalman filters are just the special case where the likelihood and prior are both Gaussian -- the distributions can be specified with a couple of numbers, and there is a simple closed-form expression for composing them. More generally, one can use all the tools available for Bayesian inference.

civility 9y ago
> It's just Bayesian inference to update the posterior. I've had this discussion with a number of smart people (math PhDs and so on) over the years, and I've never gotten a good explanation. I understand in the very abstract sense how Kalman filters (and particle filters and so on) can be seen as Bayesian, but when it gets to actually applying Bayes' theorem it really gets complicated very fast. For instance, if you're estimating a 3D position (that will be A) and your measurements are some 2D subspace (these will be B), the least squares approach works nicely (normalized products of Normal PDFs). However, I'm not sure I understand a single component of the expression P(A|B) = P(B|A) P(A) / P(B) in this context. What does A|B or B|A even mean when A is a 3D Gaussian and B is 2D? What are the dimensionalities of these operations? What does it mean to divide a product of pdfs? I don't expect an answer, but I always wince a bit when I see Bayes in this context. For Normal distributions, I prefer thinking of it as least squares.
- ssivark 9y ago
  It's Bayesian because we are estimating a (posterior) distribution for the state of the system, rather than just a "point" estimate. Restricting to only the Gaussian distribution (while a nice example) is losing the forest for the trees. > However, I'm not sure I understand a single component of the expression P(A|B) = P(B|A) P(A) / P(B) in this context. What does A|B or B|A even mean when A is a 3D Gaussian and B is 2D? What are the dimensionalities of these operations? What does it mean to divide a product of pdfs? I'm not able to understand why any of that is bothersome. Suppose A is the system's state (x,y,z) and B is the sensor reading (measures just the projection along the x-axis, such as a depth measurement). Since the sensor is not perfect, it could generate a range of readings for any given position of the object, specified by p(B[x]|A[x,y,z]) -- suppose you're give one value of B which is sampled from that distribution (say that was a Gaussian with standard deviation sigma). Given that value, you need to estimate the likelihood p(A|B). Alternatively, you can imagine performing variational inference for p(A|B) in the family of Gaussian distributions (which happens to contain the true distribution in this case). Whichever way we go about it, p(A|B) is a Gaussian with the same standard deviation sigma, centered at the measured B. (Intuitively, we can see that a measurement B will constrain the "x" component of A but not the other two coordinates) p(A) is the "prior" you get as an extrapolation from your knowledge of the system's past state. However complicated/nonlinear the system's evolution function, you can find p(A, t) either as a closed form expression, or by doing simulations, etc. (typically from p(A,t-1) but note, for example, that this general formulation can be used even if your system's dynamics does not satisfy the Markov property). If you have both p(A|B) and p(A) manifestly in the form of probability density functions, multiplying them is easy. At the end of this process, it is good enough to have an un-normalized posterior for A, which specifies the relative probability of different states. Dividing by p(B) is equivalent to normalizing the candidate posterior distribution. More generally, if the prior and the likelihood are specified by moments, or by some variational parameters, or by simulations, we can think of other ways to combine them.

ramzyo 9y ago

This is a very nice breakdown of Kalman Filtering. One slight correction - Kalman Filtering is one approach to solving the SLAM problem, but SLAM doesn’t require a KF. A particle filter, for example, can be used to solve the SLAM problem. For anyone interested in further resources to better understand the intuition behind KFs, I’ve found this resource incredibly valuable (although a little pricey): https://www.amazon.com/Kalman-Filter-Beginners-MATLAB-Examples/dp/1463648359/ref=br_lf_m_zuvo8fyr45xsoyk_ttl?_encoding=UTF8&s=books https://www.amazon.com/Kalman-Filter-Beginners-MATLAB-Exampl...

bcaine 9y ago
Another absolutely fantastic resource is this Jupyter Notebook based textbook on Kalman Filters and related topics: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... An addition to your correction: there are many other ways to solve the SLAM problem beyond (kalman/information/particle) filters. Optimization based approaches are very popular (search terms: Graph SLAM, Factor Graphs, Pose Graphs).
- ramzyo 9y ago
  True! I don’t find too many people out there who know about this stuff. Any interest in trading battle stories through DM? Would be interested to know what you’re working on and where you’ve been!
xchip 9y ago
Good point, I'll update the article to reflect that Kalman is not the only approach to solve SLAM.

albertTJames 9y ago

Very cool way of introducing kalman filters

IshKebab 9y ago

> those readings represent gaussians and combining them means multiplying them I don't think he means multiplying surely? That part is unclear.

mlevental 9y ago
how else would you combine PDFs?
- IshKebab 9y ago
  Ah I realised he meant the product of the two PDF's but it sounded like he meant the PDF of a the product of two normally distributed random variables. Which would make no sense.
- vinchuco 9y ago
  with Adobe Acrobat ;D specifically, it's referring to the multiplication rule of probability (or counting).
haskellandchill 9y ago
Why does combining mean multiplying? I got lost there. I get that you want to average/weight the two values.

eggie5 9y ago

also useful for incorporating noisy GPS sensor readings! I tried to do this in an undergrad autonomous vehicle but failed at the time :(

rsp1984 9y ago

We also do the opposite, and we use our IMU to better estimate the position of those features/clues. This is exactly what SLAM does, at its core it is just a Kalman filter with the twist that each time it finds a reliable visual clue it treats it as a sensor and makes it part of its state, a thing that allow us to tell our position much better and build a map. Some nitpicking here: There are some SLAM systems and flavors that use a Kalman filter as the main estimator under the hood but most are either hybrids or separate the tracking and map optimization (using batch / bundle adjustment methods). Digging a little deeper here I think it's important to mention that a Kalman filter is just a recursive least squares estimator, and is in fact equivalent to an Information Filter (which, IMO, is much easier to understand if you're already familiar with linear regression / LS systems). In fact a Kalman filter is just a fancy mathematical reformulation of an Information Filter that allows you to save quite a bit of computation time in case each observations is low-dimensional compared to your state.

deleted 9y ago

[deleted]

ianstallings 9y ago

I wish I had this summary quite a few years ago. I ended up buying aeronautical software textbooks and trying to glean the information from those to figure out how to integrate multiple IMU inputs. I learned that real world IMU use in navigation is pretty ugly and has to be supplemented due to constant errors. This can be particularly difficult when flying. In my case I used other sensors, such as a GPS. But a strictly IMU-only approach to lengthy navigation is, AFAIK, impossible. Either way, good write up.

colechristensen 9y ago
There are good IMUs that can be used for dead reckoning (and, if an old professor is to believed, watching the thermal expansion of a building over the course of a day) but they're hard to come by and extraordinarily expensive.
tnecniv 9y ago
> I learned that real world IMU use in navigation is pretty ugly and has to be supplemented due to constant errors. This can be particularly difficult when flying. In my case I used other sensors, such as a GPS. But a strictly IMU-only approach to lengthy navigation is, AFAIK, impossible. Yeah IMU error can be annoying unless you shell out $$$, but this issue occurs with many other kinds of sensors as well. One common trick is to treat the IMU error as another state variable that is evolving over time. It won't eradicate the compounding error, but it will reduce the amount of calibration necessary.
xchip 9y ago
I'm glad it helped, this encourages me to write more explanations of tricky subjects :)
caf 9y ago
The used to use IMU-only navigation to steer submarines and lob ballistic missiles across the world during the early Cold War.
ramzyo 9y ago
Depends on the quality of the IMU. With a MEMS IMU (what’s in your smart phone and what’s cost effective for most consumer or industrial products today) yes, it’s impossible. Too much drift as a result of process variance in MEMS manufacturing and the “runtime” noise of the IMU itself. With a precision machined IMU, like something you’d find in a submarine or pre-GPS aircraft, totally possible. There’s a YouTube video (would have to dig for the link) showing a military plane in the 1950s flying transcon NYC to LA solely on IMU dead reckoning and arriving with 1/8 mile drift or something ridiculous. The IMU probably weighed a few hundred pounds and cost many hundreds of thousands, if not millions of dollars, though.

theoh 9y ago

Another intuitive intro, previously: https://news.ycombinator.com/item?id=12648035 https://news.ycombinator.com/item?id=12648035

gnachman 9y ago

How do you know the variance of your sensors? Do you have to experiment in a controlled environment?

xchip 9y ago
Good question, yes, you measure it when the rocket is on the ground.

RosanaAnaDana 9y ago

Hmm. Could probably hammer this into a form applicable for a raster, where the previous 'instance' is a linear interpolation via Roberts cross or some such.

laythea 9y ago

I used to work at a company that did Dynamic Positioning systems for vessels and oil rigs and I worked on the periphery software systems running with a Kalman-based algorithm there. Didn't work on the Kalman stuff then, but I do think its cool what they can achieve and have always been interested. I will add this to my reading TODO. Thank you.

SatvikBeri 9y ago

Great explanation! If you want a very detailed deep dive into Kalman Filters, I found this sequence of videos really helpful: https://www.youtube.com/watch?v=CaCcOwJPytQ https://www.youtube.com/watch?v=CaCcOwJPytQ It's 55 short videos, each one going over a specific topic or example.

AceJohnny2 9y ago

I love this. I've idly tried to understand the Kalman filter forever (ever=10yr+), and always encountered explanations that threw you straight at the linear algebra[1]. (yeah, even "quick" or "simple" explanation). This explanation starting from the conceptual is great, and finally provides the needed foundation for me to understand the rest. [1] huff not that I couldn't understand the linear algebra, just that I, uh, didn't have time for that... >_>

xchip 9y ago
Thanks, I wrote this because I had been in stuck in that same situation for a ages too

randyrand 9y ago

More gain 'k' explanation. 'K' determines how much you weight you give sensor A and sensor B. A gain of 1.0 means B is weighted 100% and A is 0%. Gain of 0.5 means each gets 50/50 weight. Look at the maths and notice how when the gain is 1.0, the mean just becomes the mean of B.

xchip 9y ago
yeah, calling it 'gain' is confusing since that keyword is mainly used for amplifiers.
caf 9y ago
Notice also that if you replace k with (1-k) then you get the same results, but with a and b swapped.

rweba 9y ago

Here is another "simple" explanation: https://rweba.livejournal.com/446326.html https://rweba.livejournal.com/446326.html It's definitely WAAAY oversimplified, but it gives the first idea: The "filter" just cleverly averages the noisy real data at time T with the Kalman estimate from time (T-1).

xchip 9y ago

Kalman experienced people, just wondering, what did you use the filter for? And, what are you guys working on nowadays?

bit1 9y ago
An aircraft's Flight Management Computer uses a Kalman filter to combine the data from all available sensors (GPS, IMU, altimeter, ADC, VOR, DME, etc.) to compute the position of the aircraft.
- caf 9y ago
  A GPS itself uses a Kalman filter to combine the position estimates from many satellites as well.
ramzyo 9y ago
Robot localization and related sensor fusion problems

loxias 9y ago

This is a positively fantastic explanation. One of the best I've seen despite being so short. Minor nitpick: It might be a bit more clear if the terms "F", "s", "v" were explicitly defined, as well as a sentence explaining the matrix M inversion. It's really great, but when I read "our prediction formula F could be as simple as s = v*t_dot" I immediately think "F? was F defined earlier? Did I miss it? Also what is s?". [overall, really great explanation, bookmarked]

dennisgorelik 9y ago

The inventor of Kalman Filter: https://en.wikipedia.org/wiki/Rudolf_E._K%C3%A1lm%C3%A1n https://en.wikipedia.org/wiki/Rudolf_E._K%C3%A1lm%C3%A1n Born: Rudolf Emil Kálmán May 19, 1930 Budapest, Hungary Died: July 2, 2016 (aged 86) Gainesville, Florida

nerfhammer 9y ago

This seems to use measurement and average interchangeably? a measurement is an instantaneous "average"? if you figure out a decayed moving average as an "average"... why not just use that smoothed value directly? what do you even need variance for?

shaklee3 9y ago

I posted this a few days ago, but I think it's the best intro to Kalman filters I've ever seen: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...

jquast 9y ago

much like a baby bird learns to fly