Active questions tagged particle-filter - Robotics Stack Exchange most recent 30 from robotics.stackexchange.com 2019-12-15T21:08:27Z https://robotics.stackexchange.com/feeds/tag/particle-filter https://creativecommons.org/licenses/by-sa/4.0/rdf https://robotics.stackexchange.com/q/16234 3 How should I understand sequential importance resampling in a particle filter? michael zafford https://robotics.stackexchange.com/users/21008 2018-08-15T20:41:10Z 2019-12-09T23:01:05Z <p>Suppose I implement a particle filter with $n$ particles. This is a brief description of my understanding of a particle filter.</p> <p>For the first step, I throw out $n$ particles some distance from my vehicle. I weight the particles according to some Gaussian distribution:</p> <p>$$w_{j,t} = \frac{e^{-X_{j,t}^{2}/2\sigma^{2}}}{\sum_{j=1}^n{e^-{X_{j,t}^{2}/2\sigma^{2}}}}$$</p> <p>where $X_{j,t}$ is some (noisy) difference between a measurement taken at the vehicle and at the particle taken at time t. I then translate these particles with my vehicle (with some uncertainty) and do the same thing again, and the weights of these particles (the same particle pool) is</p> <p>$$w_{j,t+1} = \frac{e^{-X_{j,t+1}^{2}/2\sigma^{2}}}{\sum_{j=1}^n{e^{-X_{j,t+1}^{2}/2\sigma^{2}}}} w_{j,t}$$</p> <p>We resample if, according to wikipedia, $K = 1/\sum_j{w_{j,t}^2} &lt; thresh$, where thresh is some threshold we pick. Resampling is done according to each particles weight (the probability of being chosen is given by that particle's weight).</p> <p>My question is thus: if $K&lt;thresh$, that means that some particles are highly weighted. So won't resampling give us a very degenerate list of the highest weighted particles, on average? Suppose this new, resampled population is composed of only n/2 different particles, 2 times each. How do you get n particles back?</p> https://robotics.stackexchange.com/q/19797 0 Robot localization in a known map without knowing its initial position in that map Joe Samir https://robotics.stackexchange.com/users/24250 2019-11-25T16:26:20Z 2019-11-25T17:07:34Z <p>Firstly I would like to say that I'm no expert in Bayesian Filters such as Kalman Filter and Particle Filter, but I've used the EKF before in a robot that has both wheel encoders and an IMU to localize itself in a map such that it knows its initial position in the map and it worked like a charm. Now I want to build a robot that uses the same sensors as above in addition to a vision sensor (be it a kinect or some kind of a 2d Lidar) that localizes itself in a known map but has no idea of its whereabouts when it starts; I heard that the Particle Filter is used for that kind of work so I have 2 questions:</p> <p><strong>1- Can I achieve the same thing using just the Kalman Filter?</strong></p> <p><strong>2- Can I use both of them so that the particle filters will be used until the robot has the highest certainty of a location then "turn it off due to its high computational cost" and feed that location into an EKF as an initial estimate?</strong></p> https://robotics.stackexchange.com/q/19019 2 How to calculate the mean of an unsymmetric distribution (Particle Filter) duggi https://robotics.stackexchange.com/users/10386 2019-07-03T19:56:32Z 2019-07-07T19:53:13Z <p>I'm attempting to implement a variant of Monte Carlo localization in a 2D space with obstacles. While the object is moving around the obstacles the particles flow around the obstacle like in images below. But the weighted mean (arithmetic) of all particles falls outside the distribution on the obstacle. What are other ways of calculating the mean such that the estimate is actually in the distribution outside the obstacle?</p> <p><a href="https://i.stack.imgur.com/wnUGx.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/wnUGx.png" alt="enter image description here"></a> <a href="https://i.stack.imgur.com/rjKuH.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/rjKuH.png" alt="enter image description here"></a></p> <p>(shaded area is non-free space)</p> https://robotics.stackexchange.com/q/18905 2 Particle filter with error states Help me https://robotics.stackexchange.com/users/23171 2019-06-08T05:37:50Z 2019-06-08T05:37:50Z <p>I am new to particle filters and I have a particle filter based on this:</p> <p><span class="math-container">$$x_{k+1} = f_{k}(x_{k},\omega_{k})$$</span> <span class="math-container">$$y_{k+1} = h_{k}(x_{k},v_{k})$$</span> <span class="math-container">$$x = [\delta \phi, \delta \theta, \delta \psi, \delta v_n, \delta v_e, \delta v_d, \delta L, \delta \lambda, \delta h, \delta b_{ax}, \delta b_{ay}, \delta b_{az}, \delta b_{gx}, \delta b_{gy},\delta b_{gz}]$$</span> <span class="math-container">$$\tilde x = [\tilde \phi, \tilde \theta, \tilde \psi, \tilde v_n, \tilde v_e, \tilde v_d, \tilde L, \tilde \lambda, \tilde h, \tilde f_{x}, \tilde f_{y}, \tilde f_{z},\tilde w_{x}, \tilde w_{y}, \tilde w_{z}]$$</span> <span class="math-container">$$\delta x = \tilde x - x$$</span> Where:</p> <p><span class="math-container">$\tilde x$</span> is the indicated parameter and <span class="math-container">$x$</span> is the true parameter. </p> <p><span class="math-container">$x$</span> = the state being from left to right, the errors in roll, pitch, yaw, velocity north, velocity east, velocity down, latitude, longitude, altitude, accelerometer bias body frame x y z, gyro bias body frame x y z. </p> <p><span class="math-container">$\tilde x$</span> = the parameters, from left to right, the roll, pitch, yaw, velocity north, velocity east, velocity down, latitude, longitude, altitude, accelerometer reading of specific force in body frame x y z, gyroscope reading of angular velocity in body frame x y z. </p> <p><span class="math-container">$k$</span> = the time index</p> <p><span class="math-container">$\omega_{k}$</span> is the process noise (zero mean, white noise with known pdf) </p> <p><span class="math-container">$y_k$</span> is the measurement</p> <p><span class="math-container">$v_k$</span> is the measurement noise (zero mean, white noise with known pdf). </p> <p>The functions <span class="math-container">$f_k(.)$</span> and <span class="math-container">$h_k ( . )$</span> are time-varying nonlinear system and measurement equations. The noise sequences <span class="math-container">$\omega_k$</span> and <span class="math-container">$v_k$</span> are assumed to be independent and white with known pdf’s.</p> <p>For example, take the latitude error model: <span class="math-container">$$\dot \delta L = \frac {\delta V_n} {(\tilde R_e + \tilde h)} - \frac { \tilde V_n} {(\tilde R_e + \tilde h)}^2 \delta h$$</span> and the height parameter: <span class="math-container">$$\tilde h_{k} = \tilde h_{k-1} - \frac {t}{2}(\tilde v_{d(k)}+ \tilde v_{d(k-1)})$$</span> Where <span class="math-container">$t$</span> is the discrete time interval between predictions and <span class="math-container">$\tilde R_e$</span> is a function of <span class="math-container">$\tilde L$</span> and <span class="math-container">$\tilde h$</span>.</p> <p>Questions: </p> <ol> <li>How do the steps of the particle filter change when the state is an error state?</li> <li>Do the particles change the parameters and if so how and when?</li> <li>Do I have a set of parameters for each particle or one set of parameters which are separate to the particles?</li> <li>Should I predict my parameters forwards or my parameters minus particles forwards?</li> <li>Do I ever minus the weighted mean of the particles from the particles for each state except bias?</li> <li>When predicting the velocity parameter forwards, this requires the use of the accelerometer's specific force. it is a good idea to minus the bias first? If so, do I use the weighted mean of the accelerometer bias state of the particles?</li> <li>Do I use the model to predict the parameters and then the particles or the other way around?</li> <li>Is this the latitude error model in discrete: <span class="math-container">$$\delta L_k = \delta L_{k-1} + (\frac {\delta V_n} {(\tilde R_e + \tilde h)} - \frac { \tilde V_n} {(\tilde R_e + \tilde h)}^2 \delta h)t$$</span></li> </ol> https://robotics.stackexchange.com/q/18371 1 Sensor model and Inverse sensor model using occupancy grid mapping with lidar for particle filter oswinso https://robotics.stackexchange.com/users/22072 2019-03-08T15:37:36Z 2019-03-08T15:37:36Z <p>I'm a bit confused about how one goes about calculating the sensor model <span class="math-container">$p(z_t|x_t, m)$</span> and inverse sensor model for position <span class="math-container">$p(x_t |z_t,m_{t-1})$</span>.</p> <p>From this <a href="https://robotics.stackexchange.com/questions/18325/slam-scan-matching-scan-vs-previous-scan-or-scan-vs-previous-map">answer</a>, it seems like one way for calculating the inverse sensor model would be to compare the current lidar scan with the raycasted lidar scan, and then comparing them by using ICP for example.</p> <p>For the sensor model <span class="math-container">$p(z_t|x_t, m)$</span>, I've just been taking a product of the probabilities from the map, but I know that this is an incorrect method.</p> <p>What are the standard ways of computing <span class="math-container">$p(z_t|x_t, m)$</span> and <span class="math-container">$p(x_t|z_t, m_{t-1})$</span> when using a lidar with an occupancy grid for a particle filter?</p> https://robotics.stackexchange.com/q/18351 2 Help with Probabilistic Robotics Equation 13.22 detailed derivation drerD https://robotics.stackexchange.com/users/9972 2019-03-06T22:05:15Z 2019-03-07T00:50:56Z <p>Equation 13.22 from Probabilistic Robotics below: <a href="https://i.stack.imgur.com/X3xC1.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/X3xC1.png" alt="enter image description here"></a></p> <p>Here's how I get from first line to second line:</p> <p><span class="math-container">$$p(x_{1:t}^{[k]} | z_{1:t},u_{1:t}, c_{1:t}) = \frac{p(x_{1:t}^{[k]}, z_{1:t},u_{1:t}c_{1:t}) }{ p(z_{1:t},u_{1:t}, c_{1:t})} \\ p(x_{1:t}^{[k]}, z_{1:t},u_{1:t}c_{1:t}) = p(z_t|x_{1:t}^{[k]} ,z_{1:t-1},u_{1:t}, c_{1:t})p(x_{1:t}^{[k]} ,z_{1:t-1},u_{1:t}, c_{1:t}) \\ p(x_{1:t}^{[k]} ,z_{1:t-1},u_{1:t}, c_{1:t}) = p(x_{1:t}^{[k]} | z_{1:t-1},u_{1:t}, c_{1:t}) p(z_{1:t-1},u_{1:t}, c_{1:t})$$</span> Just setting up conditional probabilities above, then I'm subbing back to the first equation:</p> <p><span class="math-container">$$\\ p(x_{1:t}^{[k]} | z_{1:t},u_{1:t}, c_{1:t}) = \frac{p(x_{1:t}^{[k]}, z_{1:t},u_{1:t}c_{1:t}) }{ p(z_{1:t},u_{1:t}, c_{1:t})} = \frac{p(z_t|x_{1:t}^{[k]} ,z_{1:t-1},u_{1:t}, c_{1:t})p(x_{1:t}^{[k]} ,z_{1:t-1},u_{1:t}, c_{1:t})}{p(z_{1:t},u_{1:t}, c_{1:t})} = \frac{p(z_t|x_{1:t}^{[k]} ,z_{1:t-1},u_{1:t}, c_{1:t})p(x_{1:t}^{[k]} | z_{1:t-1},u_{1:t}, c_{1:t}) p(z_{1:t-1},u_{1:t}, c_{1:t})}{p(z_{1:t},u_{1:t}, c_{1:t})} = \frac{p(z_{1:t-1},u_{1:t}, c_{1:t})}{p(z_{1:t},u_{1:t}, c_{1:t})} p(z_t|x_{1:t}^{[k]} ,z_{1:t-1},u_{1:t}, c_{1:t})p(x_{1:t}^{[k]} | z_{1:t-1},u_{1:t}, c_{1:t}) = \eta \ p(z_t|x_{1:t}^{[k]} ,z_{1:t-1},u_{1:t}, c_{1:t})p(x_{1:t}^{[k]} | z_{1:t-1},u_{1:t}, c_{1:t})$$</span></p> <p>how do I get to the third line from here? </p> https://robotics.stackexchange.com/q/18292 3 Likelihood Field Matching umuryasinalper https://robotics.stackexchange.com/users/22405 2019-02-26T07:51:10Z 2019-03-01T11:03:02Z <p>I have LIDAR data of an environment in my hand and I want to apply likelihood field matching to this data. I found a source. But I don't understand what the variables of the algorithm mean and how it works. Can you help with that?</p> <p>Note : We're trying to apply the particle filter to a mobile robot. And we will use this algorithm for this.</p> <p>the algorithm that I found and suggested by my teacher : <a href="https://i.stack.imgur.com/l2YRl.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/l2YRl.png" alt="enter image description here"></a></p> <p>And the desired result : <a href="https://i.stack.imgur.com/ugPEh.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ugPEh.png" alt="enter image description here"></a></p> <p>Thank you for help.</p> https://robotics.stackexchange.com/q/18287 1 Fusing absolute robot localization from markers sararht https://robotics.stackexchange.com/users/22394 2019-02-25T10:16:01Z 2019-02-25T22:36:41Z <p>I have a system which is composed of a rig of 8 cameras which are used for detecting markers in the environment and which outputs 8 estimates of the absolute robot's position and orientation.</p> <p>Now, I need to fuse these estimations. I don't know if the best way is using a Kalman Filter or something like that.</p> <p>On the other hand, I do not know if it would be convenient to track the position of each camera through a particle filter before fusing.</p> https://robotics.stackexchange.com/q/10941 1 How does fast slam creates grid maps? Ricardo Achilles https://robotics.stackexchange.com/users/15119 2016-10-28T19:51:43Z 2019-02-05T06:52:09Z <p>I've implemented fast slam using landmark detection and the map stored is a feature map, made of landmarks positions. I would like to create a grid map, and my questions are about how does the robot create a grid map in slam:</p> <ol> <li><p>Another landmark class is used, or the occupancy grid is the landmark itself? In other words, the grid map generation is made separatly of the feature map?</p></li> <li><p>About the alignment of the map with the previous maps measures, this is similar to the fast slam 2.0 due to the fast that considers the robot pose and the measurement of t-1?</p></li> </ol> <p>Thanks in advance</p> https://robotics.stackexchange.com/q/16093 3 Why does the low variance resampling algorithm for particle filters work? skr_robo https://robotics.stackexchange.com/users/10959 2018-07-25T10:10:26Z 2018-12-03T17:01:58Z <p>I am studying and coding particle filters and I am using the Low variance sampling algorithm suggested in the Probabilistic Robotics book. I understand the procedure for the algorithm. A random number <code>r</code> is picked from the interval <code>(0, 1 / M)</code> and a variable <code>U</code>, calculated based on <code>r</code> is used to navigate the sample space systematically. A variable <code>c</code>(cumulative sum) is initialized with the first weight, and incremented by adding weights until it is higher than <code>U</code>. Once the cumulative sum is higher than <code>U</code>, it picks the sample corresponding to the weight last added. </p> <p>The problem that I have is that I don't see how this picks up a good sample set for the next iteration. This seems very random or at least favorable to lower valued weights. If the initial value of <code>r</code> is very low, <code>U</code> is also low initially and it may pick a sample whose weight is low, unless weight vector is sorted from high to low (Is it sorted?). However, this <a href="https://youtu.be/eAqAFSrTGGY" rel="nofollow noreferrer">video</a> suggests that particles with higher weight have a better chance of getting picked. The algorithm doesn't convey this idea to me. Please help if you have an explanation.</p> https://robotics.stackexchange.com/q/16086 1 How to generate Particle in Particle Filter Saswati https://robotics.stackexchange.com/users/20569 2018-07-23T14:42:20Z 2018-08-25T19:25:07Z <p>I try to implement FastSlam 1.0. To implement this I need to create particles. Now my confusion is that How to create Particles?I have some odometry and Measurement data. Using those data values how could I generate the Particles? </p> https://robotics.stackexchange.com/q/14932 0 Laser Scanner for localization in particle filter jack87 https://robotics.stackexchange.com/users/19226 2018-01-07T15:12:02Z 2018-06-08T08:06:29Z <p>I'm working on a particle filter implementation in Matlab and I found one very good in the Robotics Toolbox (available here <a href="https://github.com/petercorke/robotics-toolbox-matlab" rel="nofollow noreferrer">https://github.com/petercorke/robotics-toolbox-matlab</a>). My problem is that I really don't know how to modify it in order to use it with a Laser scanner, I know that with a know map the laser beam will give the distance and angle (kind o like RangeAndBearing) but I haven't understood well how the likelihood field of the map fits into this.</p> <p>In the end my question is how can I get the RangeAndBearing Measurement from a Laser scanner in order to use it in the particle filter?</p> <p>Thanks in advance</p> https://robotics.stackexchange.com/q/15158 3 Why does a Bayesian Filter require random controls? Peter Mitrano https://robotics.stackexchange.com/users/9155 2018-02-09T03:27:25Z 2018-04-11T07:02:08Z <p>As stated in Probabalistic Robotics, the proof for correctness of a Bayesian Filter relies on the fact that </p> <p>$$p(x_{t-1}|z_{1:t-1},\ u_{1:t}) = p(x_{t-1}|z_{1:t-1},\ u_{1:t-1})$$</p> <p>In order to justify this, they say</p> <blockquote> <p>$u_t$ can be safely omitted ... for randomly chosen controls</p> </blockquote> <p>Why is that required? Isn't that true because the control input at time step t cannot possibly effect the state at time t-1?</p> https://robotics.stackexchange.com/q/14748 1 how does a clustered particle filter work? user2651062 https://robotics.stackexchange.com/users/6976 2017-12-05T23:16:59Z 2017-12-06T14:14:42Z <p>Suppose we want to track multiple objects (robots, roads, people...) using clustered particle filtering (because we don't have an idea about how many objects there'll be, and the number of these may change over time). In the literature, there's a great deal of complicated formulas that explain how the weights of the clusters are calculated and involved in the calculation of the weights of the particles... Could someone explain (in very simple terms) :<br/> 1- the main idea of clustered particle filtering<br/> 2- how particules are grouped into clusters<br> 3- how weights are calculated (for particles and clusters)</p> https://robotics.stackexchange.com/q/14482 1 Why to stop a particle filter if the robot does not move? Javi V https://robotics.stackexchange.com/users/11478 2017-10-20T17:17:04Z 2017-10-20T17:17:04Z <p>It is clear it is not a good idea to do resampling in a particle filter if the robot is not moving (there is no action), as the particles will converge towards a simple particle.</p> <p>However, Probabilistic Robotics book quickly mentions "It is usually a good idea to stop measurement integration if the robot does not move". However, I am not able to fully understand why.</p> <p>My only guess is that, if robot does not move the sampling (which not resampling) will give the same particles. Therefore, is there any other negative effect other than wasting computational power? Because in a world with lots of noise I think it might be helpful to keep the sampling running to have move proper weights over time.</p> https://robotics.stackexchange.com/q/479 24 Particle filters: How to do resampling? Daniel Eberts https://robotics.stackexchange.com/users/422 2012-11-21T15:36:22Z 2017-10-08T12:24:19Z <p>I understand the basic principle of a particle filter and tried to implement one. However, I got hung up on the resampling part. </p> <p>Theoretically speaking, it is quite simple: From the old (and weighted) set of particles, draw a new set of particles with replacement. While doing so, favor those particles that have high weights. Particles with high weights get drawn more often and particles with low weights less often. Perhaps only once or not at all. After resampling, all weights get assigned the same weight.</p> <p>My first idea on how to implement this was essentially this:</p> <ol> <li>Normalize the weights</li> <li>Multiply each weight by the total number of particles</li> <li>Round those scaled weights to the nearest integer (e.g. with <code>int()</code> in Python)</li> </ol> <p>Now I should know how often to draw each particle, <em>but</em> due to the roundoff errors, I end up having <em>less particles</em> than before the resampling step. </p> <p>The Question: How do I "fill up" the missing particles in order to get to the same number of particles as before the resampling step? Or, in case I am completely off track here, how do I resample correctly?</p> https://robotics.stackexchange.com/q/13902 1 Resampling step for MC variation reduction George https://robotics.stackexchange.com/users/17669 2017-07-26T10:12:04Z 2017-07-26T10:25:06Z <p>I am reading particle filtering for robot localisation and specifically the resampling step to avoid particle degeneracy. Can anyone explain me what MC (Monte Carlo) variation means? I saw it couple of times as a benefit of some resampling techniques against others.</p> <p>For example, "Systematic resampling is the scheme preferred by the authors [since it is simple to implement, takes O(N) time, and minimizes the MC variation]" (Arulampalam et al., 2002).</p> https://robotics.stackexchange.com/q/12298 1 How to track multiple robots with particle filter Rocketmagnet https://robotics.stackexchange.com/users/40 2017-05-05T19:28:36Z 2017-05-07T19:12:53Z <p>I am using an IR camera to track N mobile robots driving about on the floor. Each robot has a few IR LEDs on its head in known locations, all at the same height above the floor. Each robot has 5 degrees of freedom, X, Y, theta, rotation rate, and velocity. All the camera sees is a bunch of blobs. I have a working blob detector, and can calculate the coordinates of visible blobs in world space. Now I would like to implement a particle filter.</p> <p>I have two options:</p> <ol> <li>Implement a single particle filter with a state space of 5xN dimensions.</li> <li>Implement N particle filters with 5 dimensional state spaces.</li> </ol> <p>My feeling is that 1. is the correct way to approach the problem, because otherwise each particle filter could easily get confused about which particle belongs to which robot. But, on the other hand, it seems like a lot of dimensions, and could be slow.</p> https://robotics.stackexchange.com/q/2251 12 Difference between Rao-Blackwellized particle filters and regular ones Ash https://robotics.stackexchange.com/users/2541 2014-01-06T22:15:12Z 2017-04-27T05:44:08Z <p>From what I've read so far, it seems that a <em>Rao-Blackwellized</em> particle filter is just a normal particle filter used after marginalizing a variable from:</p> <p>$$p(r_t,s_t | y^t)$$</p> <p>I'm not really sure about that conclusion, so I would like to know the precise differences between these two types of filters. Thanks in advance.</p> https://robotics.stackexchange.com/q/11835 0 How to make a particle filter evaluation function with LIDAR sensing? EngelOfChipolata https://robotics.stackexchange.com/users/14524 2017-03-10T12:50:37Z 2017-03-25T05:45:40Z <p>I am currently trying to implement a particle filter an a robot in a view to localize it on a 2D plane (i.e. to determine <code>x</code>, <code>y</code> and its orientation <code>theta</code> ). I am using a LIDAR which give me <code>(alpha, d)</code> with alpha the angle of measurement and d the distance measured at this angle. For now, I can compute the theoretical measures for each of my particle. But I am struggling with the evaluation function (the function that will give me the probability (or weight) of a particle considering the real measures).</p> <p>Suppose my LIDAR give me 5 values per rotation (0°, 72°, 144°, 216°, 288°), thus I store one rotation in an array (5000mm is my maximum value) :</p> <ul> <li>Real LIDAR value : <code>[5000, 5000, 350, 5000, 5000]</code></li> <li>Particle 1 : <code>[5000, 5000, 5000, 350, 5000]</code></li> <li>Particle 2 : <code>[5000, 5000, 5000, 5000, 350]</code></li> </ul> <p>In this example, I want the function to return a higher probability (or weight) for Particle 1 than for Particle 2 (72° error vs 144°). </p> <p>For now I am just doing the invert of the sum of the absolute difference between the two value at the same place in the array (e.g. for Particle 1 : <code>1 / (5000-5000 + 5000-5000 + 5000-350 + 5000-350 + 5000-5000)</code>). The problem with this method is that, in this example, Particle 1 and 2 have the same probability.</p> <p>So, what kind of function should I use to have the probability of a particle to be the right one with those kind of measurements ?</p> <p>PS : I am trying to adapt what is in this course : <a href="https://classroom.udacity.com/courses/cs373/lessons/48704330/concepts/487500080923#" rel="nofollow noreferrer">https://classroom.udacity.com/courses/cs373/lessons/48704330/concepts/487500080923#</a> to my problem.</p> https://robotics.stackexchange.com/q/10404 4 Addressing the sample impoverishment in particle filter ZincFur https://robotics.stackexchange.com/users/14385 2016-08-03T15:11:42Z 2016-12-09T15:05:49Z <p>I have implemented a particle filter algorithm for the state estimation of a mobile robot.</p> <p>There are several external range sensors(transmitters) in the environment which gives information on the distance (radius) of the robot based on the time taken for the receiver on the robot to send back its acknowledgement. So, using three or more such transmitters it will be possible to triangulate the position of the robot.</p> <p>The particle filter is initialized with 15000 particles and the sensor noise is relatively low (0.02m).</p> <p>Update Phase: At each iteration a range information from an external sensor is received. This assigns higher weights to the particles along the radius of the external sensor. Not all the particles are equally weighted since the process noise is low. Hence in most of the cases, the particle relatively closer to the robot gets lower weight than an incorrect one that happens to be along the radius. The weight is a pdf.</p> <p>Resampling Phase: At this stage, the lower weighted particle(the correct one) that has negligible weight gets lost because the higher weighted particle gets picked up.</p> <p>All this happens at the first iteration and so when the range information from another sensor arrives, the robot is already kidnapped.</p> <p>Googling around, said that this problem is called as sample impoverishment and the most common approach is to resample only when the particle variance is low. (Effective Sample Size &lt; number of particles / 2)</p> <p>But, when the particles are assigned negligible weights and there are relatively very few particles with higher weights, the diversity of the particles are lost at resampling phase. So, when the variance is higher resampling is done which removes the lower weighted particle and hence the diversity of the particles is lost. Isnt this completely the opposite of the above idea of ESS?</p> <p>Is my understanding of sample impoverishment correct? Is there a way this issue can be fixed?</p> <p>Any pointers or help would be highly appreciated.</p> https://robotics.stackexchange.com/q/11003 0 How to implement a particle filter when sensors can't identify landmarks? kmm https://robotics.stackexchange.com/users/15223 2016-11-06T16:39:57Z 2016-11-21T10:40:31Z <p>I'm attempting to build a robot that leverages a particle filter to identify where it is relative to a map that is known. The robot only has IR sensors, so while it is able to determine its distance from landmarks, it does not know what landmark it is "looking" at.</p> <p>I'm following <a href="http://nbviewer.jupyter.org/github/rlabbe/Kalman-and-Bayesian-Filters-in-Python/blob/master/12-Particle-Filters.ipynb#Update-Step" rel="nofollow noreferrer">this very helpful book</a> to build my particle filter. In incorporating the sensor measurements, it is assumed that you know both the distance to a landmark and which specific landmark you are looking at. What would need to be done if you know the map and distance measurements, but not the specific landmark that you're observing? Would this require SLAM? Or could you simply increase the probability for particles that are about that distance from a landmark?</p> https://robotics.stackexchange.com/q/10408 2 Localization of a Robot to find it Coordinates according to the Known Map Rabia Khalid https://robotics.stackexchange.com/users/14394 2016-08-04T13:37:33Z 2016-10-13T00:32:25Z <p>I am a third-year electrical engineering student and am working on an intelligent autonomous robot in my summer vacations.</p> <p>The robot I am trying to make is supposed to be used in rescue operations. The information I would know is the position of the person (the coordinates of the person in a JSON file that can be changed anytime except during the challenge) to be rescued from a building on fire. I would also know the rooms of the building from a map, but I don't know where the robot may be placed inside the building to start the rescue operation.</p> <p>That means I have to localise the robot placed at an unknown position in a known environment, and then the robot can plan its path to the person who has to be rescued. I can use gyroscope, accelerometer, magnetometer and ultrasonic sensors to do the localising job. I cannot use a GPS module or a camera for this purpose.</p> <p>The object to be rescued (whose location is known in terms of coordinates &amp; can be changed anytime) is surrounded by walls from 3 sides. Hence, adding more walls in this map.</p> <p>According to my research particle filter is the best method used for localization of robot. But how can I deal with the landmarks (walls) that are <em>fixed</em> as shown in the map image and <em>that are variable</em> depending on the location of the object to be rescued being provided in the JSON file?</p> <p>I can do the path planning from a known position to the target position, but I'm not sure how to determine the starting position.</p> <p>More about JSON file: (1) json file containing the coordinates of the object to be rescued can change. (2) it won't change during the challenge. (3) json file will be provided to me in an SD card that my robot has to read. I have successfully written the code that will allow the robot to read the json file and hence the coordinates of the object to be rescued.</p> <p>Here is the map of the building which is known to me.</p> <p><a href="https://i.stack.imgur.com/6EIgO.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/6EIgO.png" alt="enter image description here"></a></p> https://robotics.stackexchange.com/q/10679 2 Introducing new particles in particle filters for localization Josip https://robotics.stackexchange.com/users/14768 2016-09-18T18:00:44Z 2016-09-18T18:00:44Z <p>Standard particle filters can produce bad localization result if the initial particle generation step produces no particle that is close to location (and bearing) of tracked object. The accuracy depends on large number of particles to create at least one particle that's very close to state of tracking object.</p> <p>Could we introduce in resampling stage a small number of completely random new particles? For example, 99% of particles are randomly selected with weighted probability, while 1% are new particles with random state.</p> <p>My reasoning is that new particles that are bad guesses would quickly disappear, while good guesses would improve accuracy beyond what was possible with fixed particle pool. Does this improvement to particle filters make sense?</p> https://robotics.stackexchange.com/q/1525 1 How to implement Bounded Angle Vision in Particle Filter? M Faisal Hameed https://robotics.stackexchange.com/users/1573 2013-07-02T13:03:24Z 2015-10-12T09:54:54Z <p>I have built a <a href="http://sourceforge.net/projects/r-localization/" rel="nofollow">Particles Filter simulator</a> and I wanted to add the following functionalities.</p> <ol> <li>Limited Range Vision (Robot can see up to 50 meters)</li> <li>Limited Angle Vision (Robot can see within a certain angle w.r.t its current orientation. <em>e.g.</em> If the current orientation is 30 degree then it can see in the range from 0 to 60 degree.)</li> </ol> <p>I have managed to add the Limited Range Vision functionality but unable to add Limited Angle Vision.</p> <p><em>Method to Sense the landmarks distance within the range</em></p> <pre><code>public double[] sense(boolean addNoise) { double[] z = new double[World.getLandmark().getLandmarks().size()]; for (int i = 0; i &lt; z.length; i++) { Point lm = World.getLandmark().getLandmarks().get(i); double dx = x - lm.getX(); double dy = y - lm.getY(); double dist = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2)); if (addNoise) { dist += Util.nextGaussian(0, sense_noise); } if (isBoundedVision()) { // TODO Limited angle vision // if robot can see within 60 degree angle w.r.t its orientation if (dist &lt;= laserRange) { z[i] = dist; } } else { z[i] = dist; } } return z; } </code></pre> <p><em>Method to calculate the probability of this particle</em></p> <pre><code>@Override public double measurement_prob(double[] measurements) { double prob = 1.0; int c = 0; double[] myMeasurements = sense(false); for (int j = 0; j &lt; measurements.length; j++) { if (measurements[j] != 0) { prob *= Util.gaussian(myMeasurements[j], sense_noise, measurements[j]); c++; } } if (isBoundedVision()) { if (c &gt; 0) { // increase the probability if this particle can see more landmarks prob = Math.pow(prob, 1.0 / c); } else { prob = 0.0; } } return prob; } </code></pre> <p>Coordinates are relative to the robot and for distance calculation I am using the Euclidean Distance method and my Robot gets localized correctly. </p> https://robotics.stackexchange.com/q/6423 2 Particle filter weight function Khali Abd https://robotics.stackexchange.com/users/8931 2015-01-22T22:18:30Z 2015-10-05T14:13:01Z <p>I am trying to implement a particle filter in MATLAB to filter a robot's movement in 2D but I'm stuck at the weight function. My robot is detected by a camera via two points, so a single measure is a quadruple (<code>xp1</code>, <code>yp1</code>, <code>xp2</code>, <code>yp2</code>) and states are the usual (<code>x</code>,<code>y</code>,<code>alpha</code>) to detect its pose in 2D. As far as my understanding goes I should assign a weight to each particle based on its likelihood to be in that particle position with regards to the current measurement.</p> <p>I also have the measure function to calculate an expected measurement for a particle, so basically I have, for each instant, the actual measurement and the measurement that a single particle would have generated if it were at the actual state. </p> <p>Assuming all noises are Gaussian, how can I implement the weight function? I kind of noticed the <code>mvnpdf</code> function in MATLAB, but I can't actually find a way to apply it to my problem.</p> https://robotics.stackexchange.com/q/7644 4 How to use a POMDP-based planner on top of a probabilistic filter ziggystar https://robotics.stackexchange.com/users/10091 2015-07-07T07:19:56Z 2015-09-17T19:34:16Z <p>POMDPs extend MDPs by conceiling state and adding an observation model. A POMDP controller processes either</p> <ul> <li>action/observation histories or</li> <li>a bayesian belief state, computed from the observations (<em>belief-MDP</em> transformation)</li> </ul> <p>In a complex, real-world system like a robot, one usually preprocesses sensory readings using filters (Kalmann, HMM, whatever). The result of which is a belief-state.</p> <p>I am looking for publications that discuss the problem of fitting a (probably more abstract) POMDP model on top of an existing filter-bank. </p> <ol> <li>Do you have to stick to the belief-MDP, and hand over the filtered belief-state to the controller?</li> <li>Is there any way of using history-based POMDP controllers, like MCTS?</li> <li>How do you construct/find the abstract observations you need to formulate the POMDP model?</li> </ol> https://robotics.stackexchange.com/q/7705 2 Low variance resampling algorithm for particle filter Kelly https://robotics.stackexchange.com/users/10166 2015-07-18T00:32:52Z 2015-07-20T20:11:33Z <p>For my particle filter, I decided to try using the low variance resampling algorithm as suggested in Probabilistic Robotics. The algorithm implements systematic resampling while still considering relative particle weights. I implemented the algorithm in Matlab, almost word-for-word from the text:</p> <pre><code>function [state] = lowVarianceRS(prev_state, weight, state_size) state = zeros(1,state_size); % Initialize empty final state r = rand; % Select random number between 0-1 w = weight(1); % Initial weight i = 1; j = 1; for m = 1:state_size U = r + (m - 1)/state_size; % Index of original sample + size^-1 while U &gt; w % I'm not sure what this loop is doing i = i + 1; w = w + weight(i); end state(j) = prev_state(i); % Add selected sample to resampled array j = j + 1; end end </code></pre> <p>As would be expected given the while loop structure, I am getting an error for accessing weight(i), where i exceeds the array dimensions.</p> <p>To solve this, I was considering circularly shifting my weight array (putting the first index used as the first value in weight, so that I never exceed matrix dimensions). However, I wasn't sure if this would negatively impact the rest of the algorithm, seeing as I'm having trouble understanding the purpose of the U calculation and while loop.</p> <p>Could anyone help clarify the purpose of U and the while loop, and whether or not a circular shift is an acceptable fix?</p> https://robotics.stackexchange.com/q/2382 6 Motion Model for Holonomic Robot Johnny Mudcrab https://robotics.stackexchange.com/users/2450 2014-01-27T18:07:05Z 2015-07-19T01:00:34Z <p>We are working with an holonomic robot equipped with three (120 degree shifted) omnidirectional wheels. The relative movement is estimated by dead reckoning using wheel encoders. To improve this estimation we installed an gyroscope to measure the change in orientation. Furthermore the robot has a 270 degree laser range finder. </p> <p>In order to solve the kidnapped robot problem we implemented a particle filter. In every step each particle is updated according to the odometry and gyroscope readings. Since these readings are distorted by noise we need a motion model to include these errors. As described in Probabilistic Robotics by Thrun (Page 118 - 143) there are two commonly used motion models (velocity motion model and odometry motion model). However these models seem to describe the behavior of differential drive robots not omnidirectional robots. I base this thesis on the fact that the error in relative y-direction is proportional to the error in orientation as far as the motion models by Thrun are concerned. This is appropriate for differential drive robots as the orientation and the heading of the robot are identical. For omnidirectional robots this assumption can not be made since the heading and the orientation are completely independent. Even if we assume perfect information about the robots orientation we can still obtain error in relative y-direction.</p> <p>I would like to discuss if my assumption - that the velocity/odometry motion model fails for omnididrectional robots - is correct or not as i am not sure about that. Furthermore i am curious if there are any other motion models for omnidirectional robots that might fit better.</p> https://robotics.stackexchange.com/q/6810 4 Particle Filter Sampling Step Paul https://robotics.stackexchange.com/users/2295 2015-03-16T14:23:02Z 2015-03-18T13:41:34Z <p>I emphasize that my question is about <strong><em>sampling</em></strong>, not <em>resampling</em>. </p> <p>I'm reading the Probabilistic Robotics book by Thrun et al, Chapter 4 on Non-Parametric Filters. The section on Particle filters has an algorithm which states that for each particle index $m$ (see line 4): </p> <p>sample $x_t^{[m]} \sim p(x_t|u_t,x_{t-1}^{[m]})$</p> <p>The text's explanation of this step is quoted as:</p> <blockquote> <p>Line 4. generates a hypothetical state $x_t^{[m]}$ for time t based on the particle $x_{t-1}$ and the control $u_t$. The resulting sample is index by $m$, indicating that it is generated from the $m$-th particle in $\chi_{t-1}$. This step involves sampling from the state transition distribution $p(x_t|u_t,x_{t-1})$. To implement this step, one needs to be able to sample from this distribution. The set of particles obtained after $M$ iterations is the filter's representation of $\bar{bel}(x_t)$.</p> </blockquote> <p>If I understand correctly, this step says that the m-th <strong><em>sampled</em></strong> particle $x_t^{[m]}$ is obtained by advancing the previous m-th particle with control command $u_t$. I assume that the motion is not deterministic, so the result of this motion is a conditional probability, based on the particle's previous position $u_t$. </p> <p>However, I'm confused over how exactly to construct this conditional probability $p(x_t|u_t,x_{t-1}^{[m]})$. Is this information usually given? Or is it constructed from the distribution of the other particles? </p>