Rudolf Kálmán Has Died
hungarytoday.hu
hungarytoday.hu
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...
https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
It uses Jupyter Notebooks to run code in the browser. Check out the book, or run online using Binder.
Although I guess I should have been calling it a "Kálmán filter" this whole time.
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.)?
Here's some ancient code from those days: https://github.com/Qworg/Robot-Sensor-Fusion
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.
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.
EDIT: Forgot to finish my sentence...
It's much more fundamental than any of its applications, which are all around us.
https://news.ycombinator.com/item?id=11561770
I also like this interactive tutorial: http://home.wlu.edu/~levys/kalman_tutorial/
What a giant of his field! Here he is receiving the National medal of Science from Barack Obama[1]
http://www.ethlife.ethz.ch/archive_articles/091008_kalman_pe...
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.
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
In the back of my head I remembered one word: Kalman. This line of code fixed it right up:
static float display_temp = 0;
display_temp += 0.04 * (adc_temp - display_temp);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.
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.
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
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.
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.
https://en.wikipedia.org/wiki/Moving_average#Exponential_mov...
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.
Then: xhat(t+1|t) = xhat(t|t-1) + 0.04 * (y(t) - x(t|t-1) <=> display_temp += 0.04 * (adc_temp - display_temp)
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.
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.
What is the cloud of small dots?
Edit: Oh, they are samples from the hypothesis space, I suppose.
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.