Particle Filter Sampling Step

Question

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?

Answer 1

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

Answer 2

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
    sample.heading += turn
    return sample