explainer
Particle filter localization: predict, weight, and resample
Estimate a robot's position with weighted particles. Follow motion prediction, sensor likelihoods, effective sample size, and systematic resampling, then test an initial belief that misses the robot entirely.
What you will learn
- Represent several possible robot locations with weighted particles.
- Separate motion prediction from a sensor likelihood update.
- Calculate normalized weights and effective sample size.
- Explain what systematic resampling changes and what it cannot recover.
- Recognize when a weighted mean or high ESS hides localization failure.
Before you start
A particle filter estimates a robot's location by maintaining many possible locations and a weight for each. Motion moves those hypotheses. Sensor readings change their relative weights.
Resampling assigns more of the finite particle set to hypotheses with higher weight. This process can preserve several plausible locations at once. It can also fail when the particle set misses the true location.
Represent possible locations with particles
A particle is a state hypothesis, such as “the robot is at 6.1 m.” Its normalized weight describes its contribution to an approximate probability distribution. The robot occupies one actual position; the particles express uncertainty about that position.
For N particles, write the locations as xᵢ and the weights as wᵢ:
Fox, Burgard, Dellaert, and Thrun's 1999 Monte Carlo localization paper applies this representation to mobile robot localization. Its robot state includes planar position and heading. Our teaching filter estimates only one coordinate along a straight corridor.
The map is supplied. Estimating a robot's location in a known map is localization; jointly estimating its trajectory and map is the broader SLAM problem.
Define the known map and sensor model
The corridor extends indefinitely in both directions. Only three door intervals exist in this known map: [1.5, 2.5], [5.5, 6.5], and [9.5, 10.5] m. Interval endpoints count as inside a door; the drawing's edges are not walls.
A binary detector reports Door or No door. It measures no range and gives no door identity. Its conditional probabilities are:
| Actual position | P(Door given x) | P(No door given x) |
|---|---|---|
| Inside any door interval | 0.9 | 0.1 |
| Everywhere else | 0.1 | 0.9 |
The 0.1 probability outside a door models false detections. The 0.1 probability of No door inside a door models missed detections. These are chosen teaching assumptions, with independent observations conditional on the true state.
The wide initial belief is uniform over [0, 12) m. This is an assumed starting search region, even though later motion can leave it. The other choices are a near belief over [1.5, 2.5) m and a wrong belief over [8, 9) m.
The simulated robot starts at 2 m. Every later move is a commanded +1 m plus independent uniform error from −0.2 to +0.2 m. The filter uses this same motion model; there is no hidden model mismatch or boundary clamp.
Separate prediction from measurement update
Let bₖ(x) denote the position belief after reading zₖ, and let uₖ be the preceding motion command. A Bayes filter first predicts with the transition model, then conditions that prediction on the measurement:
The factor η normalizes the posterior to integrate to one. These equations assume the current state and command summarize the motion dependence, and the current state summarizes the sensor dependence. Dellaert and Hutchinson's localization chapter develops this prediction-and-update structure.
A bootstrap particle filter samples the transition model to approximate the integral. It then multiplies each existing weight by the sensor likelihood. Because the proposal is the transition model itself, this example needs no additional proposal-density ratio.
Reading 0 is special: the sampled initial belief goes straight to the measurement update. No motion precedes that first reading.
Move each particle through the motion model
At readings 1 through 4, each particle follows:
For example, a particle at 5.8 m with sampled error −0.12 m predicts 6.68 m. That position lies outside the second door. A Door reading therefore multiplies this particle's weight by 0.1.
Each particle receives its own motion draw. Prediction retains its previous weight until the sensor update. If resampling previously copied a location several times, these independent motion draws can separate the copies on the next move.
The robot's motion and observations use separate fixed random streams. Changing the particle seed changes the filter's approximation while keeping the same robot trajectory and sensor readings. Changing resampling also changes which filter-stream draws later feed motion, so this is not a paired-motion benchmark between the two settings.
Work through one sensor update
Start with four equally weighted particles at [2, 3, 4, 8] m. This hand calculation is separate from the lab's default 80-particle set. After observing Door, multiply each prior weight by its likelihood:
| Position | Prior weight | Door likelihood | Unnormalized weight | Normalized weight |
|---|---|---|---|---|
| 2 m | 0.25 | 0.9 | 0.225 | 0.75 |
| 3 m | 0.25 | 0.1 | 0.025 | 1/12 |
| 4 m | 0.25 | 0.1 | 0.025 | 1/12 |
| 8 m | 0.25 | 0.1 | 0.025 | 1/12 |
The unnormalized weights sum to 0.3, the observation probability under this predictive particle belief. Dividing by that sum gives the posterior weights. A Door reading supports the particle at 2 m, but the false-detection model leaves the others with positive weight.
For arbitrary previous weights, the update is:
Do not discard the old weights when resampling was skipped. They carry the information accumulated from earlier measurements. The worked posterior mean is 2.75 m, which summarizes this weighted set without identifying a particular particle as the robot.
Resample when a few weights dominate
The effective sample size diagnostic measures weight concentration:
Equal weights give ESS = N; one weight equal to one gives ESS = 1. In the four-particle calculation, ESS = 1/(0.75² + 3/12²) = 12/7 ≈ 1.714286. The lab resamples when ESS is strictly below N/2, a common threshold discussed by Doucet and Johansen.
Systematic resampling uses one uniform draw R from [0, 1). Its N targets are (R + j)/N, for j = 0 through N − 1. Each target selects the first cumulative weight strictly greater than the target, then the selected location receives weight 1/N.
With R = 0.2, the four targets are [0.05, 0.30, 0.55, 0.80]. The cumulative weights are [0.75, 0.833333…, 0.916667…, 1]. The selected zero-based parent indices are [0, 0, 0, 1], producing locations [2, 2, 2, 3] m.
ESS is now 4, but there are only two distinct parent locations. Resampling has added no sensor information and no new location. Its mean is 2.25 m for this draw; the change from 2.75 m is sampling variation, not a guarantee of a better estimate.
Inspect three stages of the same reading
Keep the default wide belief, 80 particles, and seed 7. At reading 0, compare Prediction, Weighted update, and After resampling. The first chart exposes individual weights; the second sums them into half-meter bins for easier comparison.
Initially, 20 of the 80 particles lie inside door intervals. After the Door reading, each of those particles has weight 0.0375; each of the other 60 has weight 0.004166667. Their ESS is 34.285714, below the threshold of 40.
Adaptive resampling produces 80 equal weights from 40 distinct parents. The weighted mean changes from 5.854489 m before resampling to 5.924549 m afterward. Inspect both distributions: those means alone conceal how weight is divided among separate regions.
Move the reading index to 4 to replay the four motions and later updates. The fixed observation sequence is Door, No door, No door, No door, Door. Try the near belief and another seed, then disable resampling to inspect how weights accumulate.
The selected-stage mean follows the stage control. The before/after ESS and resampling decision always describe the completed update at that reading. Plot heights adapt to the displayed weights; position uses the same viewing range throughout.
Keep separate location hypotheses visible
A Door reading cannot distinguish doors at 2, 6, and 10 m. Repeated map structure can leave several separated peaks, called a multimodal belief. A particle filter can represent those peaks without forcing the belief into one Gaussian shape.
The weighted mean may sit between peaks where relatively few particles exist. The same problem can affect a mean-and-covariance summary of a multimodal distribution. Compare that representation choice with the assumptions in the Kalman filter lesson.
After the default fifth reading, truth is 5.506865 m and the weighted mean is 8.359519 m. The finite observation sequence and sampled belief have not produced a reliable single-location answer. More particles improve the resolution available to the approximation; they do not give an ambiguous sensor a door identity.
The histogram is a display summary only. Its bars are probability mass in half-meter bins, not a continuous probability density. No histogram grid enters prediction, weighting, or resampling.
Test an initial belief that excludes the robot
Choose Wrong: 8 to 9 m. At reading 0, every particle lies outside a door, so each receives the same likelihood of 0.1. The normalized weights stay equal, ESS stays at 80, and the mean is 8.520879 m, despite truth being 2 m.
The filter has no particle near the robot. Resampling can copy only existing locations, and this implementation injects no new global hypotheses. Even motion noise cannot bridge the gap within the four-move experiment.
After k moves, a wrong-prior particle is at least 8 + 0.8k m, while truth is at most 2 + 1.2k m. The gap is therefore at least 6 − 0.4k m. At k = 4, it remains at least 4.4 m, including every allowed noise realization.
This is a finite-horizon support argument, not a claim that every particle filter permanently fails after a bad prior. The original MCL paper discusses adding random hypotheses for relocalization. A recovery mechanism needs its own proposal, weighting assumptions, and evaluation; equal weights alone provide no evidence of recovery.
Real localization also depends on map accuracy, timing, motion and sensor models, and enough particles in relevant regions. This one-dimensional, matched-model simulation establishes the update mechanics. It provides no hardware accuracy result or navigation safety guarantee.
The extended Kalman filter lesson uses a nonlinear motion model and landmark sensor while retaining one local Gaussian approximation. Compare its poorly initialized estimate with the separated location hypotheses here.
Reproduce the filter in Python
This standard-library script reproduces the default and wrong-prior runs. It uses integer arithmetic for the seeded uniform generator, independent streams for truth and observations, and a cumulative-weight search for resampling. The printed means and ESS values are measured immediately before any resampling at that reading.
from bisect import bisect_right
from itertools import accumulate
def uniform(seed):
while True:
seed = (1664525 * seed + 1013904223) % (2**32)
yield seed / (2**32)
def door_probability(x):
return 0.9 if any(abs(x - c) <= 0.5 for c in (2, 6, 10)) else 0.1
def normalize(particles):
total = sum(w for x, w in particles)
return [(x, w / total) for x, w in particles]
def summary(particles):
particles = normalize(particles)
return (sum(x * w for x, w in particles),
1 / sum(w * w for x, w in particles))
def resample(particles, draw):
particles = normalize(particles)
n = len(particles)
cdf = list(accumulate(w for x, w in particles))
last = max(i for i, (_, w) in enumerate(particles) if w > 0)
parents = [min(bisect_right(cdf, (draw + j) / n), last)
for j in range(n)]
return [(particles[i][0], 1 / n) for i in parents], parents
def run(low=0, high=12):
sample, motion, sensor = uniform(7), uniform(2026), uniform(2027)
particles = [(low + (high - low) * next(sample), 1 / 80)
for _ in range(80)]
truth, rows = 2, []
for k in range(5):
if k:
truth += 1 + 0.4 * (next(motion) - 0.5)
particles = [(x + 1 + 0.4 * (next(sample) - 0.5), w)
for x, w in particles]
door = next(sensor) < door_probability(truth)
particles = normalize([
(x, w * (door_probability(x) if door else 1 - door_probability(x)))
for x, w in particles
])
mean, ess = summary(particles)
changed = ess < 40
if changed:
particles, parents = resample(particles, next(sample))
rows.append((k, truth, mean, ess, changed))
return rows
for label, rows in (("wide", run()), ("wrong", run(8, 9))):
for k, truth, mean, ess, changed in (rows[0], rows[-1]):
print(f"{label} k={k}: truth={truth:.6f}, mean={mean:.6f}, "
f"ESS={ess:.6f}, resampled={changed}")
small = normalize([(2, 0.225), (3, 0.025), (4, 0.025), (8, 0.025)])
copied, parents = resample(small, 0.2)
print(f"Four-particle ESS: {summary(small)[1]:.6f}")
print(f"Parents: {parents}; new mean: {summary(copied)[0]:.6f}")
Expected output:
wide k=0: truth=2.000000, mean=5.854489, ESS=34.285714, resampled=True
wide k=4: truth=5.506865, mean=8.359519, ESS=45.766256, resampled=False
wrong k=0: truth=2.000000, mean=8.520879, ESS=80.000000, resampled=False
wrong k=4: truth=5.506865, mean=12.521303, ESS=80.000000, resampled=False
Four-particle ESS: 1.714286
Parents: [0, 0, 0, 1]; new mean: 2.250000
The generator is s ← (1664525s + 1013904223) mod 2³², followed by s/2³². Seeds are 7 for particles, 2026 for robot motion, and 2027 for sensing. Resampling consumes one particle-stream draw only when the ESS test passes.
Check two localization claims
Exercise 1. The four particles at [2, 3, 4, 8] m again start with equal weights. This time the reading is No door. What are the normalized weights and ESS, and does the N/2 rule request resampling?
Show the weight calculation
The unnormalized weights are [0.025, 0.225, 0.225, 0.225], with sum 0.7. Normalized weights are [1/28, 9/28, 9/28, 9/28].
Their squared weights sum to 244/784 = 61/196, so ESS = 196/61 ≈ 3.213115. This exceeds the threshold of 2, so the filter keeps the unequal weights and skips resampling.
Exercise 2. A filter has 80 equally weighted particles initially in [8, 9) m, while truth starts at 2 m. Both use +1 m moves with errors bounded by ±0.2 m. Can a high ESS after four moves establish that the filter has recovered?
Show the reachability argument
No. The earliest any of those particles can be is 8 + 4(0.8) = 11.2 m. The furthest truth can be is 2 + 4(1.2) = 6.8 m, leaving a gap of at least 4.4 m.
Equal weights produce ESS = 80 wherever the particles are. Resampling only copies their positions, so it cannot bridge that gap. High ESS describes balanced weights, while recovery requires hypotheses consistent with the robot's actual location.
Sources and further study
- Fox, Burgard, Dellaert, and Thrun, “Monte Carlo Localization: Efficient Position Estimation for Mobile Robots,” AAAI 1999: weighted location hypotheses, motion and sensing updates, and recovery considerations. Its robot experiments and adaptive particle counts are separate from this fixed-count corridor example.
- Dellaert and Hutchinson, Introduction to Robotics and Perception, section 4.4: Bayes filtering and localization representations, including a one-dimensional door example. The map, probabilities, streams, and exercises here are specified independently.
- Doucet and Johansen, “A Tutorial on Particle Filtering and Smoothing: Fifteen Years Later,” sections 3.4–3.5: systematic resampling, ESS-triggered resampling, and the distinction between weight diagnostics and approximation quality.
Continue with occupancy grid mapping to change the estimation target from robot position to map cells. When applying either model to a robot, check the sensor and motion assumptions against recorded observations.