4 ms·

I like particle filtering because it's easy to understand and implement - https://en.wikipedia.org/wiki/Monte_Carlo_localization https://en.wikipedia.org/wiki/M

I like particle filtering because it's easy to understand and implement - https://en.wikipedia.org/wiki/Monte_Carlo_localization https://en.wikipedia.org/wiki/Monte_Carlo_localization - and it's correct even for non-gaussian uncertainty. Is Kalman filtering computationally more efficient (obviously particle filtering is stochastic and so trades off accuracy for compute) or does it have some other advantage?

thetwiceler 11y ago
Firstly, Kalman filtering is optimal, that is, it produces exactly the correct posterior distribution. As you mention, particle filters cannot achieve this. It's a rough heuristic that to achieve a certain accuracy for a linear/Gaussian system with a particle filter, you need a number of particles exponential in the number of dimensions of the system. I feel like this could probably be stated more formally and shown, but I don't think I've seen anything in that vein. The Kalman filter, being simply matrix operations, should scale as the number of dimensions cubed. So yes, Kalman filtering is computationally more efficient, and (obviously) more accurate. I also wouldn't discount the fact that the Kalman filter is, in a sense, simpler than the particle filter for a linear/Gaussian system; you don't need to worry about resampling or setting a good number of particles, and you don't need to compute estimates of the mean/covariance statistics (which are sufficient since the posterior should be a Gaussian).
- RogerL 11y ago
  Under the same conditions of linearity and Gaussian noise you can get essentially optimal performance. Of course, why would you when the KF is so much more efficient.
  - papaf 11y ago
    This is true but the assumption of Gaussian noise carries with it the assumption that the model is correct. Most models are not correct which is why particle filters perform much better than people expect.
- donquichotte 11y ago
  Particle filters can be an option if the noise is not additive (e.g. scales with signal amplitude) and Gaussian.
robotresearcher 11y ago
The KF is very efficient. It's optimal for linear Gaussian systems and computation is polynomial in measurement dimensionality k and state dimensionality n:   O(k^2.376 + n^2) (Yes I had to look that up.)
CHY872 11y ago
Kalman Filters are super efficient to calculate - they're what kept the Apollo program on track (60s compute!). Another post gives the asymptotic complexity - but as a rule of thumb if you can do any practical computation at all you can run a Kalman Filter. Basically they're both implementations of a recursive Bayesian filter, but the Kalman filter requires very strong assumptions about the distribution (all Gaussian) and the particle filter requires none. The Kalman filter is optimal for the Gaussian case (and is very efficient to calculate), whilst the particle filter can use more accurate distributions but is far less efficient to calculate. You kinda use them in different places - a Kalman filter is useless for pedestrian dead reckoning (step made + estimate of direction), whilst a particle filter would be similarly dumb on submarines.
Symmetry 11y ago
True. Our robot uses a particle filter since we're mostly localization by odometry and lidar returns. But if we had an outdoors robot using GPS like the one in the article then our uncertainty would be a lot more Gaussian and I think we'd switch. Also, for determining the position of your own robot the efficiency isn't a big deal. But if you're tracking a lot of objects in your environment then it becomes more important. And since you're looking at the objects and are tracking relative position the distribution is uni-modal too.

thetwiceler 11y ago

Firstly, Kalman filtering is optimal, that is, it produces exactly the correct posterior distribution. As you mention, particle filters cannot achieve this. It's a rough heuristic that to achieve a certain accuracy for a linear/Gaussian system with a particle filter, you need a number of particles exponential in the number of dimensions of the system. I feel like this could probably be stated more formally and shown, but I don't think I've seen anything in that vein. The Kalman filter, being simply matrix operations, should scale as the number of dimensions cubed. So yes, Kalman filtering is computationally more efficient, and (obviously) more accurate. I also wouldn't discount the fact that the Kalman filter is, in a sense, simpler than the particle filter for a linear/Gaussian system; you don't need to worry about resampling or setting a good number of particles, and you don't need to compute estimates of the mean/covariance statistics (which are sufficient since the posterior should be a Gaussian).

RogerL 11y ago
Under the same conditions of linearity and Gaussian noise you can get essentially optimal performance. Of course, why would you when the KF is so much more efficient.
- papaf 11y ago
  This is true but the assumption of Gaussian noise carries with it the assumption that the model is correct. Most models are not correct which is why particle filters perform much better than people expect.
donquichotte 11y ago
Particle filters can be an option if the noise is not additive (e.g. scales with signal amplitude) and Gaussian.

robotresearcher 11y ago

The KF is very efficient. It's optimal for linear Gaussian systems and computation is polynomial in measurement dimensionality k and state dimensionality n:   O(k^2.376 + n^2) (Yes I had to look that up.)

CHY872 11y ago

Kalman Filters are super efficient to calculate - they're what kept the Apollo program on track (60s compute!). Another post gives the asymptotic complexity - but as a rule of thumb if you can do any practical computation at all you can run a Kalman Filter. Basically they're both implementations of a recursive Bayesian filter, but the Kalman filter requires very strong assumptions about the distribution (all Gaussian) and the particle filter requires none. The Kalman filter is optimal for the Gaussian case (and is very efficient to calculate), whilst the particle filter can use more accurate distributions but is far less efficient to calculate. You kinda use them in different places - a Kalman filter is useless for pedestrian dead reckoning (step made + estimate of direction), whilst a particle filter would be similarly dumb on submarines.

Symmetry 11y ago

True. Our robot uses a particle filter since we're mostly localization by odometry and lidar returns. But if we had an outdoors robot using GPS like the one in the article then our uncertainty would be a lot more Gaussian and I think we'd switch. Also, for determining the position of your own robot the efficiency isn't a big deal. But if you're tracking a lot of objects in your environment then it becomes more important. And since you're looking at the objects and are tracking relative position the distribution is uni-modal too.