47 Particle Filters for Localization

47.2 Particle Filters Track States

A particle filter is a sequential Monte Carlo estimator. Instead of forcing the state belief into one Gaussian mean and covariance, it carries many particles. Each particle is a possible state, such as a device location, robot pose, or user trajectory, with a weight that says how well that hypothesis explains recent sensor evidence.

This matters when an IoT state is nonlinear, constrained, or non-Gaussian. A person may be equally likely to be near two corridors until a new BLE beacon reading arrives. A robot cannot pass through a wall even if the motion model says the straight-line path is short. A noisy radio fingerprint can create several plausible positions instead of one symmetric uncertainty ellipse.

When one Gaussian estimate cannot represent the plausible states, inspect Figure 47.1 to see how a population of hypotheses carries uncertainty.

Read Figure 47.1 as a repeating cycle. Prediction moves every particle under the motion model, measurement assigns greater weight to hypotheses that agree with the observation, and resampling concentrates computation on the better-supported regions while retaining diversity. The cloud of particles, not one dot, is the state belief. That progression advances the chapter's narrative: particle filters earn their cost when ambiguity or non-linearity matters, and their claim remains reviewable only with model, likelihood, particle-count, and degeneracy evidence.

Overview Knowledge Check

47.3 Predict, Weight, Resample

The common bootstrap particle filter has four operating steps. Predict each particle forward with the motion model and process noise. Weight each predicted particle using the sensor likelihood model. Normalize the weights so they sum to one. Resample when the particle set has collapsed too far onto a few hypotheses.

The likelihood model is the engineering contract. For a range sensor it may be a Gaussian error model around distance. For BLE localization it may compare observed RSSI against a fingerprint map. For a map-aware robot it may assign near-zero likelihood to poses that imply the robot crossed a wall. Those choices should be versioned and tested, because they decide which particles survive.

A shoe-mounted pedestrian dead-reckoning system shows why that map-aware weighting matters in practice. Step events from a foot-mounted IMU predict each particle's next position and heading; the map likelihood then sets a particle's weight to zero the instant its predicted step would cross a wall, so illegal paths are pruned rather than merely discounted. Because the starting position is unknown, the filter begins in a localisation phase with a large particle population spread across every open room and corridor; as wall rejections and step evidence rule out most of that spread, the belief collapses onto the true corridor and the filter can shift into a tracking phase with far fewer particles, since forming the cumulative weight for resampling is a sequential bottleneck that a smaller population makes cheaper. A reported deployment of this pattern reached about 0.75 m accuracy at the 95th percentile with the inertial sensor mounted on the shoe. Publish which phase the filter believes it is in, because the accuracy claim and the compute budget are different in each.

Worked example: one-dimensional location update
measurement z: 10.0 m
sensor sigma: 1.0 m
predicted particles x_i: 8.8, 9.5, 10.2, 11.0, 12.0 m
relative likelihood: exp(-0.5 * error^2 / sigma^2)

particle  error  likelihood  normalized weight
8.8 m     -1.2   0.487       0.158
9.5 m     -0.5   0.882       0.285
10.2 m     0.2   0.980       0.317
11.0 m     1.0   0.607       0.196
12.0 m     2.0   0.135       0.044

sum of likelihoods = 3.091
weighted estimate =
8.8*0.158 + 9.5*0.285 + 10.2*0.317 + 11.0*0.196 + 12.0*0.044
= about 10.02 m

Interpretation:
The particles near the 10.0 m measurement dominate the estimate.
The 12.0 m particle is not impossible, but it contributes little evidence.

Practitioner Knowledge Check

47.4 Degeneracy and Compute Limits

A particle filter usually fails in one of two ways. Degeneracy happens when nearly all probability mass sits on a few particles, so most compute is wasted. Particle impoverishment happens after repeated resampling when the surviving particles become too similar, so the filter stops representing uncertainty. Both problems are operational, not just mathematical.

Effective sample size is a practical monitor for degeneracy: ESS = 1 / sum(w_i^2). If all particles have equal weight, ESS is close to the particle count. If one particle dominates, ESS approaches one. Many systems resample only when ESS falls below a threshold, then inject process noise so the population can keep exploring plausible states.

Worked example: resampling trigger
particle count N: 5
normalized weights: 0.62, 0.18, 0.10, 0.06, 0.04

ESS = 1 / (0.62^2 + 0.18^2 + 0.10^2 + 0.06^2 + 0.04^2)
ESS = 1 / 0.432
ESS = 2.31 particles

example threshold: 0.5 * N = 2.5
decision: ESS is below threshold, so resample.

Operational note:
After resampling, copy high-weight particles more often, drop weak particles,
then add realistic motion noise. Without noise, the copied particles can become
identical and the filter may not recover when the next measurement contradicts them.

The resampling step itself has a standard, concrete mechanic worth naming: build a cumulative-weight table from the normalized weights, then map a stream of independent random draws in [0, 1) onto that table to pick which particle each new copy comes from. Continuing the resampling-trigger example above, the cumulative weights are 0.62, 0.80, 0.90, 0.96, and 1.00 for particles P0 through P4. A random draw of 0.30 lands before 0.62, so it selects P0; a draw of 0.75 lands between 0.62 and 0.80, so it selects P1; draws of 0.85, 0.95, and 0.99 select P2, P3, and P4 in turn. Because P0's weight spans 62 percent of the [0, 1) range, most random draws land there and P0 is copied several times, while P4's narrow 0.04 span means it is rarely picked and often drops out of the population entirely.

Under-the-Hood Knowledge Check

Track belief rather than a single coordinate through the diagram Figure 47.2.

In the diagram Figure 47.2, start with weighted hypotheses, then Predict through noisy motion before using Correct with an anchor. The P2 = 0.42 label is a changed probability, not a teleported pose, so proposal coverage still bounds what the filter can recover.

Inspect the full reject-to-copy mechanism in Figure 47.3.

In the diagram Figure 47.3, p3 receives 0.00 when it crosses the Corridor wall, then Normalize valid mass gives it no cumulative interval. Random u maps three example draws to particles, and Copy and re-noise explains why high-weight hypotheses multiply without becoming identical forever.

Match particle budget to uncertainty rather than choosing one permanent count in the diagram Figure 47.4.

In the diagram Figure 47.4, lOCALIZE searches broadly with 5,000 particles while TRACK follows one mode with 600 particles and a 0.75 m median error. Predict/correct remains parallel-friendly in both, but cumulative resampling remains the sequential pressure point.