Particle Filter Sampling Step

I emphasize that my question is about sampling, not resampling.

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):

sample $x_t^{[m]} \sim p(x_t|u_t,x_{t-1}^{[m]})$

The text's explanation of this step is quoted as:

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)$.

If I understand correctly, this step says that the m-th sampled 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$.

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\left(x_t|u_t,x^{[m]}_{t-1}\right)$ should be created from your motion model. See chapter 5 in your book. Algorithms can be found in table 5.3 for a velocity model or table 5.6 for a odometry model.

Roughly speaking: If your robot has a speed of 1m/s and it moves straight (which may be your $u_t$) and your update rate is 1Hz, then you could move each particle 1m forward. To respect the fact that nothing is known exactly you could then disturb each position by adding some position noise.

• So, is it necessary to perturb the deterministic prediction with some noise? If I omit the noise and just use the deterministic motion model, would my particle filter fail?
– Paul
Mar 19 '15 at 4:22
• Well, if you have a deterministic way, then why use a probabilistic one? But, how can be sure that your deterministic prediction is correct? Can you be sure that there is no noise in your sensors? Mar 19 '15 at 9:42
• Also, in fact you should not use "some" noise. The values should be pertubed according to you model and your measurement errors... Mar 19 '15 at 9:50

The new particle should be created from your motion model, basically you select one random possible outcome of the data you measured. This is an example for differential drive, the random.gauss calls are resoponsible for the sampling part:

def update_sample(self, sample, left_ticks, right_ticks):
""" Returns a new sample updated according to measured movement."""
left_distance = left_ticks * self.left_resolution * random.gauss(1, self.left_sigma)
right_distance = right_ticks * self.right_resolution * random.gauss(1, self.right_sigma)
forward = (left_distance + right_distance) / 2
turn = (right_distance - left_distance) / self.wheel_base
alpha = sample.heading + turn / 2

sample = copy.copy(sample)
sample.x += math.cos(alpha) * forward
sample.y += math.sin(alpha) * forward