4 ms·

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 visuali

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. 1. https://jsfiddle.net/bendykst/tfcub3tj/ https://jsfiddle.net/bendykst/tfcub3tj/

brianwawok 10y ago
That is a cool demo!
xchip 10y ago
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
- tgb 10y ago
  It looks like a particle filter to me. https://en.wikipedia.org/wiki/Particle_filter https://en.wikipedia.org/wiki/Particle_filter
- bendykstra 10y ago
  Oh, you are right. That is actually a particle filter. I'm sorry, I studied both on the same day and misremembered which one I had implemented.
Bromskloss 10y ago
Never mind it not being a Kálmán filter; it's cool anyway. What is the cloud of small dots? Edit: Oh, they are samples from the hypothesis space, I suppose.
- nitrogen 10y ago
  They are probably the "particles", a bunch of different guesses made by the filter process.
- tgb 10y ago
  I agree it's still fun. 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.

brianwawok 10y ago

That is a cool demo!

xchip 10y ago

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

tgb 10y ago
It looks like a particle filter to me. https://en.wikipedia.org/wiki/Particle_filter https://en.wikipedia.org/wiki/Particle_filter
bendykstra 10y ago
Oh, you are right. That is actually a particle filter. I'm sorry, I studied both on the same day and misremembered which one I had implemented.

Bromskloss 10y ago

Never mind it not being a Kálmán filter; it's cool anyway. What is the cloud of small dots? Edit: Oh, they are samples from the hypothesis space, I suppose.

nitrogen 10y ago
They are probably the "particles", a bunch of different guesses made by the filter process.
tgb 10y ago
I agree it's still fun. 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.