Particle Filter
leimao.github.io
Particle Filter
1–10 of 20 posts
Re: Particle Filter
#2Here's a short little video I found helpful in understanding the Particle Filter algorithm: https://www.youtube.com/watch?v=aUkBa1zMKv4
Re: Particle Filter
#3This is a pointer that's a bit buried. For all the fanciness of different particle filtering algorithms, you are likely not using enough particles. Unless you having troubles related to running out of memory consider using more particles. Even doing fancier things like rejuvenation and stratified sampling benefit from more particles.
Re: Particle Filter
#4Ive never found a practical implementation of particle filters that was deployed on a real system. PF are a poor choice for tracking a solution that does not have wildly divergent measurements that can cause "lost robot" types of situations. Even then, PF is a fine temporary and high cost stopgap to converge to a "filterable" solution with only one predominant mode / a tight cluster of oarticles. At that point, a closed form approximate filter makes better sense in terms of cpu cost, memory, etc. Save the memory for feature maps and the CPU cost for iterations or at worst a few extra hypotheses on your primary filter.
Re: Particle Filter
#5I can't quite understand from this post what a particle filter is or what the project is. Is this a simulation of a robot using sensor readings to estimate its position in a maze? How are particles emitted, and how does the sensor measure them? What does the "probability" of a particle mean? Does it combine any information about its previous position estimate? And how would this be applied in the real world without a perfect model of the environment?
Re: Particle Filter
#6Ive never found a practical implementation of particle filters that was deployed on a real system. PF are a poor choice for tracking a solution that does not have wildly divergent measurements that can cause "lost robot" types of situations. Even then, PF is a fine temporary and high cost stopgap to converge to a "filterable" solution with only one predominant mode / a tight cluster of oarticles. At that point, a clo…
As you say, measurements with multimodal error, but also measurements with horribly non linear observation or time models. It has to be pretty bad though, otherwise a UKF would be better.
Re: Particle Filter
#7Ive never found a practical implementation of particle filters that was deployed on a real system. PF are a poor choice for tracking a solution that does not have wildly divergent measurements that can cause "lost robot" types of situations. Even then, PF is a fine temporary and high cost stopgap to converge to a "filterable" solution with only one predominant mode / a tight cluster of oarticles. At that point, a clo…
As you say, measurements with multimodal error, but also measurements with horribly non linear observation or time models. It has to be pretty bad though, otherwise a UKF would be better.
For those not familiar, UKF = unscented Kalman filter. And by the way, there is no such thing as "scented" KF. The inventor of the UKF, whose name was Jeff Uhlmann, didn't want this method to be called after his name, so he picked a random word in the dictionary.
Re: Particle Filter
#8Ive never found a practical implementation of particle filters that was deployed on a real system. PF are a poor choice for tracking a solution that does not have wildly divergent measurements that can cause "lost robot" types of situations. Even then, PF is a fine temporary and high cost stopgap to converge to a "filterable" solution with only one predominant mode / a tight cluster of oarticles. At that point, a clo…
They work pretty well if you've got a robot navigating indoors via lidar versus a map. We used one for the QC Bot which made it to production.
Also, an economist I dated for a bit used particle filter in her research.
Re: Particle Filter
#9I can't quite understand from this post what a particle filter is or what the project is. Is this a simulation of a robot using sensor readings to estimate its position in a maze? How are particles emitted, and how does the sensor measure them? What does the "probability" of a particle mean? Does it combine any information about its previous position estimate? And how would this be applied in the real world without a…
> Is this a simulation of a robot using sensor readings to estimate its position in a maze?
Yes.
> How are particles emitted, and how does the sensor measure them?
I think I understand your question, and there might be a misunderstanding here. The "particles" are not emitted in traditional sense. They are merely records in an internal data structure inside the robot's head.
The problem: Your robot has a map of the scene, but doesn't know where it is. You have distance measuring sensors on four sides of the robot, but they can't see enough details to say where you are on the map.
What the "particle filter" aproach suggest is that you keep a list of hypothesises of where the robot might be. Each hypothesis is a full parameterisation (x, y, heading in 2d), and for historical reasons we call them "particles".
At the beginning you initialise a bunch of these "particles" with random x, y, h values. Then in a loop you take measurements with the sensors and calculate how plausible each hypothesis is.
Maybe all your sensors can tell you is that there are walls a meter away at the rear and to the sided but there is 3m free space forward. This would make the "particles" which are in the middle of a big room very unlikely while any particle which puts you in a cull-the-sack heading out would be more likely.
Next you would like to keep the more likely hypothesises while rejecting the least likely ones. What the "particle filter" approach suggest is that you re-sample your particles such a way that the probability of keeping a particle equals with their calculated "plausibility".
In the next step you move with your robot using your motors. Usually you don't have perfect actuation, but you have a probabilistic idea of how much you might have traveled. You then update each particle by some movement sampled from that probabilistic motion model. After that repeat from the sensing step.
What usually happens is that after a few iterations all the particles collapse to a few well localised spots on the map. Very frequently to a single spot and that means that the "kidnapped" robot has localised itself. This happens because given enough data all the implausible theories can be eliminated and what remains is where you are.
> What does the "probability" of a particle mean?
It gives a measure of how well the location represented by the particle (a particular theory) fits with the last sensor measurements.
> Does it combine any information about its previous position estimate?
Indirectly. The re-sampling step guarantees that the particle is there because it was at least somewhat plausible in the past, but you don't have to keep an ever growing history explicitly.
> And how would this be applied in the real world without a perfect model of the environment?
You need some model of the environment (an occupancy map for example) but it doesn't need to be perfect. Since everything is already probabilistic, you can have a probabilistic map. Changes of how you calculate the plausibility (probability) of a given hypothesis (particle) but doesn't change the whole algorithm.
About how it is applied in the real world... well I will be frank with you I have seen many robots localise in different ways and neither of them used particle filters. Maybe we were all missing out on something cool. :) Thrun et al. describe in Probabilistic Robotics as something which were useful for them in the past. So you have that.
Re: Particle Filter
#10The term "monte carlo methods" in statistics/probability bothers me, since it literally just means trying out, or simulating. I can't help but think someone started using it to just sound smart. Such shenanigans seem make science harder to grasp especially for newcomers, so I think it would be better to keep naming simple and obvious where possible. There are enough topics that are too abstract, so it can't be done there.