Nonparametric Filters

Chapter 1: The Histogram Filter

The simplest nonparametric filter chops the state space into a grid and maintains one probability per cell. For a discrete state space (like "which room am I in?"), this is exact. For a continuous state space (like x-y position), it's an approximation — the finer the grid, the better.

pseudocode
# Discrete Bayes Filter (Histogram Filter)
Input: {pk,t-1}, ut, zt

for all grid cells k do
  p̅k,t = Σi p(Xt=xk | ut, Xt-1=xi) · pi,t-1   # prediction
  pk,t = η · p(zt | Xt=xk) · p̅k,t              # update
endfor

return {pk,t}

This is just the Bayes filter from Chapter 2, with the integral replaced by a sum over grid cells. Each cell k stores a probability p_k,t. The prediction step sums up contributions from all cells (weighted by the motion model). The update step multiplies by the measurement likelihood.

Chapter 2: Continuous State Histograms

When the state space is continuous (like a robot's x-y-θ pose), we discretize it into a grid:

Each region x_k,t gets a single probability value. Within each region, the belief is assumed uniform. This means the posterior is a piecewise constant approximation to the true continuous density.

The conditional probabilities are approximated by evaluating at the center of each cell:

where x̂_k,t is the mean of region x_k,t.

Two strategies for managing resolution:

Fixed fine-grained grids: High accuracy, high cost. Best with pre-caching (compute expensive ray-casts once) and selective updating (only update cells with non-negligible probability).

Variable-resolution grids: Coarse where the belief is spread out, fine where it's concentrated. Tree-based structures (e.g., quad-trees) adapt resolution dynamically. This is the adaptive approach.

Chapter 3: Binary Bayes Filters

A special case worth highlighting: what if the state is binary and doesn't change over time? For example, "Is this grid cell occupied or free?" This is the foundation of occupancy grid mapping (Chapter 9).

For binary static state, the Bayes filter simplifies dramatically. Using the log-odds representation:

The update becomes a simple addition:

where l₀ is the prior log-odds. Each measurement just adds its "evidence" to the running total. This is fast, numerically stable, and avoids the probabilities-near-zero problem.

Chapter 4: The Particle Filter Idea

The particle filter takes a completely different approach to representing beliefs. Instead of dividing space into cells, it uses a collection of random samples called particles:

Each particle x_t^[m] is a concrete hypothesis: "The robot might be here, in this exact pose." Where particles cluster, probability is high. Where they're sparse, probability is low.

How many particles do we need? In practice, M = 100 to 10,000 depending on the problem. More particles give better approximation. Some implementations adapt M based on the complexity of the current belief.

The magic: as M → ∞, the particle approximation converges to the true posterior. For finite M, there's some approximation error, but in practice even a few hundred particles work remarkably well.

Chapter 5: PF Algorithm

The particle filter algorithm has three elegant steps for each time step:

pseudocode
# Particle Filter
Input: Xt-1, ut, zt

# Step 1: Predict — sample new poses from motion model
for m = 1 to M do
  xt[m] ~ p(xt | ut, xt-1[m])        # sample from motion model
  wt[m] = p(zt | xt[m])             # importance weight
endfor

# Step 2: Resample — survival of the fittest
for m = 1 to M do
  draw i with probability ∝ wt[i]
  add xt[i] to new Xt
endfor

return Xt

Step 1 — Predict: Each old particle is "moved" by sampling from the motion model. If the robot moved forward, each particle moves forward plus some random noise. This creates the predicted particle set.

Step 1b — Weight: Each predicted particle is weighted by how well the measurement matches. A particle that's consistent with the sensor reading gets a high weight; one that contradicts it gets a low weight.

Step 2 — Resample: Draw M new particles from the weighted set, with replacement. High-weight particles get duplicated; low-weight particles vanish. This is Darwinian selection — hypotheses that explain the data survive, others die.

Chapter 6: PF Demo

Let's watch a particle filter track a robot in a 1D hallway. The robot starts with global uncertainty (particles spread everywhere), then moves and senses landmarks. Watch how particles cluster around the true position after a few measurements.

Chapter 7: Importance Sampling

The theoretical foundation of particle filters is importance sampling. The idea: we want to sample from a target distribution f (the posterior), but we can't do it directly. Instead, we sample from a proposal distribution g (the motion model), then correct using weights.

In the particle filter:

• The target f is the full posterior bel(x_t) = η p(z_t|x_t) bel̅(x_t)

• The proposal g is the prediction bel̅(x_t) = p(x_t|u_t, x_t-1)

• The weight simplifies to w = f/g = p(z_t|x_t) — the measurement likelihood

Alternative proposals (beyond the motion model) can improve particle filter performance. The optimal proposal incorporates the measurement into the proposal, generating particles that are more likely to be in high-weight regions. This reduces the variance of the weights but is harder to sample from.

Chapter 8: PF Properties

Particle filters have several important properties that make them widely used:

Known limitations:

Particle depletion: In high-dimensional spaces, particles spread too thin. If no particle is near the true state, the filter cannot recover. This is the curse of dimensionality for particle filters.

Sample impoverishment: After many resamplings, the particle set may lose diversity — many particles become copies of the same few ancestors. Techniques like low-variance resampling and roughening help.

No global localization recovery: Once all particles cluster in the wrong place, the filter is stuck. Adding random particles occasionally (as in MCL, Chapter 8) helps.

Chapter 9: Comparison

Let's compare all the filter families we've seen:

Chapter 10: Summary

Nonparametric filters break free of the Gaussian assumption. They can represent arbitrary beliefs — multi-modal, skewed, heavy-tailed — at the cost of more computation.