The Kalman Filter was used the in the Apollo 11 Guidance Computer [0] (discussed in the past on HN [1]).
As someone linked previously, here is a historical perspective [2], and a link to the actual state vector update computations [3].
The AGC maintained the state vectors for the KF. Ground control would run batch mode least squares solutions, and pass it on to the LM, where the updates to the state vector would be applied by hand. The variables of the state vector were a 6x6 matrix of position and velocity in X, Y, and Z or a 9x9 matrix when including radar/landmark bias.
I have great admiration for Mr. Kalman. Controls engineering has greatly benefited from his work.
Kalman filters are really neat. I wrote one when learning C a while ago and it is just cool what some matrix math can do with practical data. https://github.com/lacker/ikalman
Although I guess I should have been calling it a "Kálmán filter" this whole time.
Interesting. I don't see generic Kalman filter implementations too often. Thanks for sharing.
I've always found that determining where to put outputs from disparate sensors as opposed to just filtering a single observation like the GPS output in your example is challenging. Have you tried extending this to include input from other sensors (e.g. accelerometer, gyroscope, magnetometer, etc.)?
I actually found it to be such a pain in the ass to tune, it didn't even seem that great on iPhones with plain old GPS compared to a hacky bundle of heuristics. I left the code on github because why not, and it turned out over the years people have used it for various things.
GPS already use a Kalman filter to create a filtered output. You cannot apply a second filter to the output of the first and expect better results.
Specifically, the Kalman filter depends on the data having the Markov property, and that the noise is Gaussian. The output of the filter has neither property, so you are not going to get better data. You may "smooth" the data, but all you are really doing is 1) discarding useful information, and/or 2) introducing a lag into the signal.
I was waiting for this headline. Someone edited his wikipedia article last week, but provided no source and no articles were published yet.
The Kalman filter is a fantastic tool. I use it and the particle filter regularly. Both are ubiquitous in robotics and cyber-physical systems and incredibly powerful tools.
Interestingly, Kalman wasn't able to publish it in a prestigious journal at the time and had to settle for a lesser known one.
I'm always surprised when people talk about Kalman filters without mentioning the killer app, which is weather prediction. Quite a few weather prediction organisations are at least experimenting with Kalman filters, and some are running whole ensemble forecasts using the method. It may sound strange, but the Kalman filter can be a less CPU-intensive (or at least more parallelisable) way of calculating atmospheric state than the current variational data assimilation methods.
With the massive resurgence in Neural Networks, it may interest you to know that DEKFs ( decoupled extended Kalman Filter ) are a very fast sequential weight update procedure while training large neural nets. For instance: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=614185
It's always sad hearing about great minds who fled Europe shortly before or during World War II. It's a reminder of all the great minds whom we lost in the last war, and of how destructive war is to technological and human progress.
I read a few articles on that website specified by the post and I was very happy not to be a contemporary Hungarian, both from a current problem, and political philosophy point of view.
There were only a few times in history when it was good/safe to be hungarian - and this meme has a long tradition in hungarian thinking. Just read the national anthem. (It is written in 1823 but it could be easily extended with events from the last 190 years...) http://lyricstranslate.com/hu/himnusz-national-anthem-hungar...
Technology is gained but so much intellectual capital is destroyed. And there's no good A/B test with war to see how much technological progress would have been gained from the intellectual capital if it hadn't been destroyed.
I wrote my thesis on mathematical filters for robot localization. A true great has passed. =/
If folks are interested, here's some ancient (and likely awful) code I wrote for it. It has a MH set, a Fuzzy set, a PF and a SPKF as well: https://github.com/Qworg/Robot-Sensor-Fusion
there's an unobserved state that changes over time according to relatively simple rules, and you get indirect information about that state every so often. In Kalman filters, you assume the unobserved state is Gaussian-ish and it moves continuously according to linear-ish dynamics (depending on which flavor of Kalman filter is being used)
Just last week I needed to smooth out a display reading on an oven controller. The RTD was being read way too fast so I'd get a lot of flicker between values due to ADC resolution.
In the back of my head I remembered one word: Kalman. This line of code fixed it right up:
Despite some saying this is not a Kalman filter I'd argue that it is, although a quite simple stationary Kalman filter. I'm not saying calling it a low-pass filter or IIR is wrong, but that there is not a clear distinction in this case. Hear me out:
The general model for a linear system is:
x(t+1) = A * x(t) + B * u(t) + v1(t)
y(t) = C * x(t) + D * u(t) + v2(t)
Generally, x (state), y (measurement) and u (input) are vectors, A,B,C,D matrices and v1, v2 noise.
The optimal Kalman estimate for this system is:
xhat(t+1|t) = A * xhat(t|t-1) + B * u(t) + K(y(t) - C * x(t|t-1)
where K is the Kalman gain which might be calculated for each update step or in the case of a stationary Kalman filter will be calculated to a fix value. The idea behind using a fix value is that generally, K(t) will converge as the filter runs.
Now say the state x is scalar, the model is that x is always the same and unaffected by input (A = 1, B = 0) and that we measure the state directly and that also the measurement is unaffected by input (C = 1, D = 0). Let's also say K = 0.04, it might well be.
Thus for the model that
1) the oven temperature is constant and
2) unaffected (at least not quickly affected) by the temperature control and
3) that we measure temperature directly and
4) the assumption that the stationary Kalman gain is 0.04,
this is a (stationary) Kalman filter.
You can do better by having the 0.04 parameter follow an exponential decay as well. Start at 1.0 and have it decay to 0.04 or even 0.01 over time. That would make it more like a real Kalman filter for such a simple measurement. You'll get fast convergence to an initial value and then very smooth response after that.
A classic example is a fuel gauge where you want to reject low frequency sloshing but have a rapid startup without knowing in advance what the level really is.
How about a mechanical low-pass filter?: A vertical tube connected to the tank via a tiny hole would not be affected much by sloshing, but would slowly drift towards having the same level of fuel as the tank has on average.
Indeed; it's a discrete approximation to the infinite impulse response exhibited by all sorts of physical systems leading to the characteristic exponential decay.
That's just a linear interpolation between two values: take 96% of the current display value plus 4% of the new value from the ADC, which is the same as finding 4% of the way between the two values. It's a simple generalization of the arithmetic mean, which is the special case of 50%.
I'm skeptical that anyone sane would credit this obvious idea should to one particular person, which is why it can't be the Kalman filter.
If you're really trying to find a cooler name than the obvious low-pass IIR filter, you could call it an "alpha filter", which is equivalent to a position only (no derivatives) Kalman filter in steady-state, using a precomputed gain (called alpha, here equal to 0.04).
The alpha-beta filter is the position/velocity version, and is commonly seen in settings where less is known about the system dynamics, or there's not enough CPU for matrix math. See https://en.wikipedia.org/wiki/Alpha_beta_filter
Are alpha-beta (or alpha) filters a subset of Kalman Filters?
I ask because I don't know enough about the Kalman Filter. But it seems that the parent post could also be accurate.
I imagine many implementations of the Kalman Filter take advantage of the local use case, and don't necessarily have to carry a fully generalised Kalman filter.
One of the defining characteristics of the Kalman filter is that it computes a gain (called the Kalman gain) that is a function of the state covariance and the measurement covariance. Alpha-beta filters use constants, so I'd say no, they are not a subset.
You can define alpha/beta in terms of the covariance of the Kalman filter. See my book (linked above) for the derivation (I call it a g-h filter, some literature uses alpha-beta, some g-h, they are the same thing). Eli Brookner in "Tracking and Kalman Filters Made Easy" uses a different but mathematically equivalent derivation to show the relationship.
There are at least a couple dozen of commonly used filters that can be understood as form of the alpha-beta filter. Some use constants for g/h, some vary them over time. The Kalman filter varies them on each epoch based on the covariance of the state and measurements. There are other schemes. The KF is optimal in the least squares sense when the noise is Gaussian and and the system obeys the Markov property.
Another way to look at these is to derive them from Bayes' theorem. You can derive both the alpha-beta filter and Kalman filter from Bayes' theorem. It's all the same family, just with different assumptions/knowledge about your process and measurement noise.
I'd agree that the alpha-beta filter is a special case of the Kalman filter (which isn't what I'd call a subset, but maybe we're just arguing semantics). All the filters you mention are certainly related, but claiming that the alpha-beta filter is a Kalman filter is either naive or obstinate.
Edit: This is wrong. This is a particle filter, another type of Bayesian filter. I can't delete now, so please downvote to hide.
I made a Kalman Filter visualization[1] last year to learn more about them. It's amazing to see how good a result you can get from very poor sensor data.
In the visualization, a lawnmower (green dot) is tracked (blue circle) using triangulation. The distance sensors have very low accuracy (grey regions). When the mower reaches the edge of the yard, its position and velocity are randomized, but the filter is not told, so it has to reacquire.
That is not a Kalman filter :) A Kalman filter uses matrices, a physical model of the system its trying to filter data and lots of stuff I haven't found in that code
Kalman filters work by the assumption that everything is distributed by a gaussian. However the given example shows a case where we have very non-gaussian distributions, namely the input to the system is estimates of the distance of the lawn mower to the towers, which means it's a sort of annular distribution with a big whole in the middle (these are shown in the visualization). Contrast this to a gaussian which is a solid blob: a gaussian would be a poor approximation to the information provided by a distance to a point.
But without the assumption that the distribution is gaussian, the math is intractable, in particular how do you even represent an arbitrary probability distribution over possible positions? One option is to discretize space and give a 'heat map' of probabilities. This works but limits spatial resolution and grows to be a huge amount of work and memory for higher dimensional state spaces(1). The small dots are the alternative approach and are the eponymous 'particles'. Here we estimate the probability distribution by a collection of possible states, each being one point, and each state is weighted by how probable it is. Then a new piece of information applied (another round of distance data from the three points) to each of those points. This updates the probability of each point being 'correct'. Then a new batch of points is randomly selected by adding some noise to the current batch and preferentially choosing the higher probability points. This is why they jump around at each time step.
The advantage here is that most possible states are ridiculously unlikely but particles tend to group around the likely points, so we spend our time looking near the likely places and not around the unlikely places. If you discretized space, the vast bulk of the space will just be epsilon probability and doing you no good. And the particles have arbitrary precision without needing to increase the amount of points used. Plus we can work with non gaussian distributions. Otherwise it's 'just' another way of approximating a Bayesian update but under different assumptions and tradeoffs compared to a kalman filter. If you've got nearly gaussian distributions kalman filters are simpler and faster and more memory efficient, so they're very popular for embedded systems.
(1) Actually we're probably dealing with a 4 dimensional state space already making a discretized approach essentially already impossible. There are two space dimensions plus two for the velocity of the mower.
As someone linked previously, here is a historical perspective [2], and a link to the actual state vector update computations [3].
The AGC maintained the state vectors for the KF. Ground control would run batch mode least squares solutions, and pass it on to the LM, where the updates to the state vector would be applied by hand. The variables of the state vector were a 6x6 matrix of position and velocity in X, Y, and Z or a 9x9 matrix when including radar/landmark bias.
I have great admiration for Mr. Kalman. Controls engineering has greatly benefited from his work.
[0] http://en.wikipedia.org/wiki/Apollo_Guidance_Computer
[1] https://news.ycombinator.com/item?id=8063192
[2] http://www.ieeecss.org/CSM/library/2010/june10/11-Historical...
[3] http://www.ibiblio.org/apollo/listings/Comanche055/MEASUREME...