ProjekinAja. Robotics Stage 4 · State Estimation Lesson 4.7
● Stage 4 · Lesson 4.7

Particle Filters: Non-Gaussian and Multimodal Beliefs

The particle filter is the only estimator that handles genuinely multimodal beliefs — and the kidnapped-robot problem is not a thought experiment, it happens when a person pushes the robot.

⏱ ~22 min read 🎲 Sequential Monte Carlo 🤖 FollowBot localization

🎯 By the end you'll understand

How sequential importance resampling (SIR) propagates a belief through a nonlinear, non-Gaussian filter. Why importance weights work and how resampling collapses them back to uniform. The three practical resampling strategies — naive multinomial, systematic, and residual — and when each matters. How particle deprivation kills a converged filter and how recovery augmentation (random-particle injection) defends against it. When to use a particle filter versus an EKF or UKF, and the hard ceiling imposed by the curse of dimensionality. And the kidnapped-robot failure mode: after resampling collapses to one wrong mode, the filter cannot self-recover without injecting fresh particles.

KEY INSIGHTA particle filter is Bayes on a swarm of hypotheses

Every other filter in this stage picks a shape for the belief and fits parameters to it. The particle filter makes no shape assumption — it carries the belief itself, distributed across thousands of weighted samples.

The Kalman filter, the EKF, and the UKF all share one deep assumption: the posterior belief over the robot state is reasonably well described by a Gaussian. That assumption buys tractability — a mean and covariance are all you need to store — but it collapses the moment the belief becomes multimodal. Consider a robot placed in a symmetric corridor: it knows it is in one of two identical-looking sections, but cannot yet tell which. Its belief is bimodal. A Gaussian fit to that belief would place the mean halfway between the two modes — a place where the robot definitely is not. Only a filter that can carry two separate probability masses simultaneously can represent that belief correctly. The particle filter does exactly that, by replacing the parametric distribution with a set of weighted samples drawn from the state space.

🔑 The core exchange

The particle filter trades Gaussian tractability for representational generality. It can represent any posterior — bimodal, heavy-tailed, banana-shaped, discontinuous. The price is that it requires enough particles to cover the state space adequately, and that price compounds badly as the state dimension grows. Use the particle filter when the posterior genuinely cannot be approximated as a Gaussian, not as a default because it sounds more powerful.

HOW IT WORKSSequential importance resampling: the SIR algorithm

The particle filter maintains a belief bel(xt) as a set of M particles: {xt[1], …, xt[M]}, each a concrete hypothesis about the robot's state. At every timestep the filter performs three operations: predict, weight, resample.

1

Predict — propagate each particle through the motion model

For each particle xt-1[m], draw a new particle from the motion model: xt[m] ~ p(xt | ut, xt-1[m]). In practice this means: apply the odometry command ut to the particle and add noise sampled from the known odometry error model. For a differential-drive robot, the noise model is the standard two-wheel odometry model with parameters α1…α4 governing how rotation-noise and translation-noise scale with the commanded motion. Critically, this is a sample from the motion model — you do not need it to be Gaussian. Any distribution you can sample from works here.

2

Weight — score each particle against the measurement

After prediction, each particle is at a hypothetical position. Given the current sensor measurement zt, assign each particle an importance weight w[m] = p(zt | xt[m]). This is the observation likelihood: how probable is the measurement we actually received, if the robot were at this particle's location? For a LIDAR sensor with a known map, this means ray-casting from the particle's position and comparing predicted ranges to actual ranges. Particles near the true position generate predicted ranges close to the observed ranges and receive high weights. Particles in the wrong place generate inconsistent predictions and receive low weights.

After weighting, normalize: w̃[m] = w[m] / Σj w[j]. Now the weights sum to one and form a discrete probability distribution over the particles.

3

Resample — draw a new population proportional to weights

Draw M new particles from the current weighted set, each particle x[m] selected with probability proportional to w̃[m]. This step concentrates particles in high-probability regions: good particles get duplicated, poor particles get discarded. After resampling, all M new particles are treated as equally weighted (uniform weights). The filter then iterates: predict with the next odometry command, weight with the next measurement, resample. This is sequential importance resampling (SIR), and it is the foundation of every practical particle filter in robotics.

📖 Why "importance" sampling?

The name comes from Monte Carlo importance sampling theory. We want to compute expectations under a target distribution p(x) but we can only sample from a proposal distribution q(x). The correction factor — the ratio p/q — is the importance weight. In the particle filter, the proposal is the motion model (we draw particles by predicting forward), and the target is the posterior including the measurement. The measurement likelihood p(z | x) is the importance weight. After resampling, the resampled particles approximate draws from the posterior directly, so future propagation can again use the motion model as the proposal. The entire SIR cycle is one application of sequential importance sampling with resampling.

1 · PREDICT apply motion model + noise xₑ ~ p(xₑ | uₑ, xₒ₋₁) uniform weights cloud spreads (uncertainty grows) 2 · WEIGHT score against observation wⁿ = p(zₑ | xₑⁿ) then normalize weights high-weight ≈ near true pose 3 · RESAMPLE draw M new particles ∝ normalized weights duplicates → good regions cloud concentrates iterate with next odometry + measurement
The SIR cycle. Each arrow is one filter update. The feedback arrow (bottom, dashed) shows that the resampled set becomes the prior for the next predict step — the filter runs continuously, one cycle per sensor arrival.

CORE CONCEPTImportance weights: what they mean and when they collapse

The importance weight w[m] encodes how well particle m explains the current measurement. A particle at the correct robot pose with a realistic map will generate ray-cast predictions that closely match the LIDAR scan; its likelihood is high. A particle 2 m away in an open corridor will cast rays that miss the walls the sensor actually sees; its likelihood is near zero.

Two numbers summarize the health of the weight distribution at any moment:

Metric Formula Healthy value What collapse looks like
Effective sample size (Neff) 1 / Σ(w̃[m])² ≥ M/2 (use at least half the particles) Neff ≈ 1: one particle has weight ≈ 1, rest ≈ 0
Weight variance Var(w̃) Low — weights roughly uniform after resampling Spike: one weight dominates, rest degenerate

Weight collapse — Neff approaching 1 — means the filter has effectively discarded all but one particle. If that surviving particle is at the correct pose, localization succeeds. If it is at the wrong pose, the filter has no mechanism to recover: every subsequent resample step will just duplicate that wrong particle, and the uncertainty representation collapses to a single incorrect hypothesis maintained with total confidence.

⚠ Weight collapse is the silent death of a particle filter

Unlike Kalman filter divergence, which manifests as a growing covariance that a NEES test can catch, particle filter weight collapse produces an answer that looks confident but is wrong. The estimated pose has low spread (all particles are near one location) but that location may be entirely incorrect. Monitor Neff at runtime and trigger recovery when it drops below a threshold — typically M/5 to M/2 depending on how dynamic the environment is.

CORE CONCEPTResampling strategies: multinomial, systematic, and residual

Resampling is sampling M particles from a discrete distribution defined by the weights. The naive approach — multinomial resampling — draws each new particle independently by sampling from the weight CDF. It is unbiased but introduces variance: some good particles may be drawn many times by chance, others not at all. Three strategies are commonly used:

Strategy Mechanism Variance Cost Best for
Multinomial Draw each of M particles independently from weight CDF High (variance scales linearly with M — each draw is independent) O(M log M) Simple implementations; rarely best choice
Systematic One random offset u ~ Uniform[0, 1/M]; M evenly-spaced pointers Low (variance does not scale with M — one random draw governs all) O(M) Standard choice for mobile robot localization
Residual Floor(M·w̃[m]) guaranteed draws, then resample remainder Very low O(M) Very unequal weight distributions

Systematic resampling is the practical default. The single random offset u is drawn once, then M pointers are placed at u/M, u/M + 1/M, u/M + 2/M, … The set of particles selected corresponds to walking the cumulative weight function with these evenly-spaced pointers. This eliminates the high-variance behavior of multinomial sampling: particles with weight close to 1/M are almost certain to receive exactly one copy, while particles with near-zero weight are almost certain to be discarded. The reduction in resampling variance directly translates to better filter stability with fewer particles.

💡 Adaptive resampling: only resample when needed

Resampling introduces its own variance: it throws away the continuous particle cloud and replaces it with duplicates, losing information about the tails of the distribution. A common fix is adaptive resampling: only resample when Neff drops below a threshold (e.g., M/2). When the belief is already well concentrated and all weights are nearly equal, skip resampling for that step. This prevents the filter from collapsing its diversity unnecessarily during phases of accurate localization.

SEE ITParticle filter visualizer — convergence, collapse, and recovery

This 2D arena places FollowBot (the triangle) in a room with three circular landmarks. Adjust particle count and watch the filter converge. Then teleport the robot (kidnap it) to see the filter fail to recover — and toggle adaptive augmentation to see rescue by random-particle injection. The worst decision: using a small particle count and disabling augmentation after convergence.

⚙ Interactive · Particle filter in 2D

Sliders control particle count and augmentation rate. Use the buttons to run the filter, kidnap the robot, or inject recovery particles. Observe Neff and the particle cloud response.

200
OFF
5
particle (high weight) particle (low weight) true robot landmark random (augmentation)

Press Run Filter to start.

💡 What to try

1. Convergence: Set M = 200 particles, augmentation OFF. Click Run Filter repeatedly — watch the cloud collapse onto the true pose. 2. Small-particle collapse: Set M = 10. Run filter until converged. Kidnap the robot. Notice particles cannot recover — they're all near the old (wrong) location. 3. Augmentation rescue: After kidnapping with M = 200, set augmentation rate to 0.05 or 0.10 and run filter again. Random particles (red squares) seed new hypotheses and the cloud shifts to the true location.

The key lesson from this widget: a converged particle filter that has experienced particle deprivation (or a kidnapping) is indistinguishable from a correctly-converged filter from the outside — both return a confident pose estimate. Only monitoring Neff and the weight entropy gives you early warning before the behavior degrades.

WEAKNESSParticle deprivation and recovery augmentation

Particle deprivation is the failure mode that strikes precisely when the filter seems to be working well. After convergence, nearly all M particles cluster tightly around the correct pose. This is desirable — but it eliminates diversity. If the robot is subsequently kidnapped (physically moved to a new location without any motion command being issued — e.g., a person picks it up and moves it), the entire particle cloud is in the wrong place. The predict step will spread the cloud a little (by the motion noise model), but if no motion command was issued, it spreads it not at all. The weight step will then assign near-zero weight to every particle — because every particle is far from the actual observation likelihood peak — and the resampling step will simply duplicate the least-wrong wrong particle over and over.

⚠ The kidnapped robot problem is not hypothetical

In practice, kidnapping happens every time someone picks up the robot, every time the robot software is relaunched without moving the robot from where it last was, and every time a large localization error accumulates silently and then a corridor turn makes it suddenly visible. The particle filter's failure mode is catastrophic here because after weight collapse, there is literally no signal left to recover from — all particles are wrong, the resampling step selects the least-wrong wrong particle, and the filter locks into an incorrect belief with apparent confidence.

Recovery augmentation is the standard defense. At each filter cycle, with probability αslow or when Neff drops below a threshold, inject a fraction of new particles drawn uniformly from the entire state space (or from a prior over valid robot poses). These random particles serve as scouts: most will immediately receive near-zero weights and be discarded in the next resampling step, but if any of them land near the true pose, they will receive high weights and be preferentially duplicated. The filter can then gradually shift its probability mass to the new location over successive cycles.

The tuning tension is real: a high augmentation rate (α = 0.2) keeps the filter robust to kidnapping but permanently maintains a diffuse cloud that increases the pose estimate variance during normal operation. A low rate (α = 0.01) barely perturbs the convergence behavior but may take many cycles to recover from severe kidnapping. The practical recommendation for indoor mobile robots is α ~ 0.03–0.08 with adaptive triggering: run at low α normally, spike to 0.2–0.4 when Neff drops below M/10.

COMPARISONParticle filter vs. EKF vs. UKF: when to reach for each

Having covered the EKF (Lesson 4-5), UKF (Lesson 4-6), and now the particle filter, you need a clear decision framework. The choice is not primarily about implementation complexity — it is about the shape of the posterior and the dimension of the state space.

Criterion EKF UKF Particle Filter
Posterior shape assumption Gaussian (required) Gaussian (required) None — arbitrary
Handles multimodal beliefs No No Yes — by design
Nonlinear motion model Jacobian required No Jacobian needed Just sample from it
Nonlinear observation model Jacobian required No Jacobian needed Just evaluate likelihood
State dimension Any (covariance O(n²)) Low to medium (sigma pts = 2n+1) Low only — curse of dimensionality
Computational cost O(n³) per update O(n³) per update O(M · cost_per_particle)
Memory O(n²) — covariance O(n²) — covariance O(M · n) — particle set
Kidnapping recovery Cannot recover (no diversity) Cannot recover (no diversity) Yes — with augmentation
Global localization Requires initialization Requires initialization Can initialize uniformly

The curse of dimensionality is the hard ceiling on particle filters. To cover an n-dimensional state space with K samples per dimension requires Kn total particles. A 3D pose space (x, y, θ) with 10 samples per dimension needs only 10³ = 1,000 particles — tractable. A 6D state (x, y, θ, v, ω, a) needs 10⁶ = 1,000,000 — not tractable in real time. The EKF and UKF scale as O(n³) — still polynomial, not exponential. In practice, particle filters are used for 2D–4D state spaces. For FollowBot's 5D EKF state vector [x, y, θ, v, ω], the EKF is the right choice for normal localization. The particle filter is used specifically when the robot needs to localize globally (from an unknown initial position) or recover from kidnapping, after which the EKF takes over.

🔑 The MCL–EKF handoff pattern

A common production architecture for indoor robots uses the particle filter (Monte Carlo Localization) for global localization and kidnapping recovery, and then hands off to the EKF for normal tracking once the particle filter has converged to a unimodal belief. The handoff criterion is: when the particle cloud's effective sample size exceeds 80% of M and the spread (the standard deviation of particle positions) drops below a threshold (e.g., 0.15 m), extract the weighted mean and covariance and initialize the EKF. This gives you global recovery capability with EKF efficiency during normal operation. Nav2's AMCL node implements a variant of this architecture.

FOLLOWBOTParticle filter in FollowBot's localization stack

FollowBot's Stage 4 milestone specifies: full EKF operational with state vector [x, y, θ, v, ω], fusing wheel odometry, IMU, and LIDAR scan-matching; filter consistency validated with NEES; position error below 0.1 m RMS in a known map. That milestone is achievable with the EKF alone — under the assumption that the robot is always initialized correctly and never kidnapped. In field deployment, that assumption fails regularly.

The recommended architecture for FollowBot adds a thin Monte Carlo Localization (MCL) shell around the EKF:

mcl_recovery.pyrclpy · ROS 2 Humble
import rclpy
from rclpy.node import Node
import numpy as np
from geometry_msgs.msg import PoseWithCovarianceStamped

# Simplified MCL recovery node.
# Full implementation uses robot_localization + AMCL from Nav2.
class MCLRecovery(Node):
    def __init__(self):
        super().__init__('mcl_recovery')
        self.M = 500          # particle count
        self.alpha_aug = 0.05  # augmentation rate
        self.neff_thresh = self.M / 5  # trigger recovery below this

        # particles: [x, y, theta, weight]
        self.particles = self._init_uniform()
        self.weights = np.ones(self.M) / self.M

        self.create_subscription(
            PoseWithCovarianceStamped,
            '/ekf_pose', self._ekf_cb, 10
        )
        self.pub = self.create_publisher(
            PoseWithCovarianceStamped, '/mcl_pose', 10
        )

    def _init_uniform(self):
        # draw M particles uniformly from map bounds
        rng = np.random.default_rng(42)   # deterministic seed
        x   = rng.uniform(0.0, 8.0, self.M)
        y   = rng.uniform(0.0, 6.0, self.M)
        th  = rng.uniform(-np.pi, np.pi, self.M)
        return np.stack([x, y, th], axis=1)

    def _neff(self, w):
        return 1.0 / np.sum(w ** 2)   # effective sample size

    def _systematic_resample(self, w):
        # O(M) systematic resampling
        cdf = np.cumsum(w)
        u = np.random.uniform(0, 1.0/self.M)
        pointers = u + np.arange(self.M) / self.M
        indices = np.searchsorted(cdf, pointers)
        return indices

    def _ekf_cb(self, msg):
        # Monitor EKF covariance trace as proxy for confidence
        cov_trace = (msg.pose.covariance[0] +
                     msg.pose.covariance[7] +
                     msg.pose.covariance[35])
        neff = self._neff(self.weights)

        if neff < self.neff_thresh or cov_trace > 1.0:
            # Low confidence: inject random particles
            n_aug = int(self.alpha_aug * self.M)
            aug = self._init_uniform()[:n_aug]
            aug_idx = np.random.choice(self.M, n_aug, replace=False)
            self.particles[aug_idx] = aug
            self.get_logger().warn(
                f'MCL recovery: Neff={neff:.0f}, injecting {n_aug} random particles'
            )

In Nav2's AMCL (Adaptive Monte Carlo Localization), this architecture is already built in. The relevant parameters for FollowBot's amcl.yaml:

amcl.yamlNav2 · ROS 2 Humble
amcl:
  ros__parameters:
    min_particles: 500          # minimum M (adaptive MCL lower bound)
    max_particles: 3000         # maximum M during global localization
    alpha1: 0.2                 # rot noise from rot
    alpha2: 0.2                 # rot noise from trans
    alpha3: 0.2                 # trans noise from trans
    alpha4: 0.2                 # trans noise from rot
    recovery_alpha_slow: 0.001  # slow filter for weight avg
    recovery_alpha_fast: 0.1   # fast filter — triggers injection
    resample_interval: 1        # resample every N updates
    robot_model_type: "nav2_amcl::DifferentialMotionModel"
    laser_model_type: "likelihood_field"
    laser_max_range: 12.0       # RPLIDAR A2 max range
    laser_min_range: 0.1
    max_beams: 60               # subsample scan (360 → 60 beams)
    z_hit: 0.5                  # weight of Gaussian hit model
    z_rand: 0.5                 # weight of uniform random model
    sigma_hit: 0.2              # std of Gaussian hit (meters)

The recovery_alpha_slow and recovery_alpha_fast parameters implement Thrun's KLD-sampling with recovery augmentation. When the fast average of observation likelihoods drops significantly below the slow average, the filter injects random particles proportional to (1 - w_fast/w_slow). This is the standard production defense against the kidnapped-robot problem in AMCL.

🔑 Stage 4 FollowBot milestone check

With the full EKF operational and AMCL running as a localization layer: (1) Position error below 0.1 m RMS in a known map — verified by comparing AMCL pose estimates to ground-truth marks on the floor. (2) Filter consistency validated with NEES test on recorded data (Lesson 4-4 procedure). (3) Sensor dropout behavior characterized: when the LIDAR loses all valid returns (person blocks scan), the EKF propagates on odometry alone for up to 2 seconds before covariance exceeds threshold and a warning is issued. (4) Kidnapping recovery: AMCL converges to the correct pose within 30 seconds of being placed at a random new location, with >90% reliability across 10 trials at M=2000 particles.

WEAKNESSWhere particle filters bite

⚠ Convergence is not recovery

The most dangerous misunderstanding about particle filters: people see the cloud converge to a tight cluster and conclude the filter is healthy. Convergence to a wrong mode is indistinguishable from convergence to the correct mode by looking at the particle spread alone. After the kidnapping, the filter converges confidently — to the wrong location. The robot then drives into walls with complete certainty. The fix is to never solely monitor particle spread; always also monitor observation likelihood averaged over the particle set. If the average likelihood is low even though the particles are tightly clustered, the cloud has converged to a location that does not match the sensor data.

⚠ Undersampling and the filter's silent lie about state space coverage

With M = 50 particles in a 2D room of 8 m × 6 m = 48 m², each particle represents approximately 1 m² of floor area. That means the filter may miss the true robot location entirely if it is more than about 0.5 m from the nearest particle at initialization. The filter will not tell you this: it will converge to the nearest particle's location, with apparently low uncertainty. The silence is the problem. Always run enough particles to ensure the initial distribution covers the space adequately: a minimum of one particle per 0.5 m × 0.5 m × 15° cell is a reasonable heuristic for 2D localization — which gives roughly 2,000 particles for a typical 10 m × 10 m room.

⚠ The curse of dimensionality is not a theoretical concern

It is common to see particle filter implementations used for state vectors of dimension 5, 6, or even 10 in research papers. This almost always works in simulation, where the sensor model is exact and the motion model has low noise. In real hardware, the noise is higher, the state space needs more coverage, and M must grow exponentially to maintain coverage. A 6D state space that required M = 1,000 particles in simulation may need M = 100,000 in the field to maintain the same localization quality. At that scale, the EKF — scaling polynomially with state dimension — almost always wins on both accuracy and speed. The particle filter's home is 2D–3D state spaces: (x, y, θ) for mobile robot localization, or (x, y, θ, d) where d is a discrete room label.

KEY INSIGHTHow this connects

  • 4.2 · The Bayes Filter and the Predict-Update Cycle — The particle filter is a sample-based implementation of the Bayes filter derived there. Every SIR step maps directly onto the Bayes filter's predict and update equations; the particle filter simply avoids computing the integral analytically by using Monte Carlo samples instead.
  • 4.5 · The Extended Kalman Filter: Nonlinear Systems and Jacobian Linearization — The EKF is the practical complement to the particle filter: fast, memory-efficient, and excellent when the posterior is unimodal Gaussian. The design pattern of using MCL for global localization and then handing off to EKF for steady-state tracking combines both filters' strengths.
  • Next: 4.8 · IMU Preintegration and High-Rate Sensor Fusion — With localization established via AMCL + EKF, the next question is how to fuse the 200 Hz IMU with the 10 Hz LIDAR without blocking the localization loop. IMU preintegration solves this by accumulating high-rate measurements between LIDAR updates.

The particle filter closes the loop on Stage 4's core question: what shape can a belief take, and which filter is right for that shape? Linear Gaussian → Kalman filter. Nonlinear Gaussian → EKF or UKF. Multimodal or non-Gaussian → particle filter. This taxonomy will reappear in Stage 5 when SLAM fuses localization with mapping, and the choice of landmark representation (Gaussian EKF-SLAM vs. Rao-Blackwellized particle filter for FastSLAM) is driven by exactly this tradeoff.

GLOSSARYKey terms

Sequential importance resampling (SIR)
The standard particle filter algorithm: predict particles through the motion model, weight each particle by the observation likelihood, resample proportionally to weights. Repeating these three steps implements approximate Bayesian filtering without any Gaussian assumption.
Importance weight
The ratio of the target distribution to the proposal distribution, used to correct for sampling from a different distribution than the one of interest. In SIR, the weight is the observation likelihood p(z | x): how probable is the observed measurement given that the robot is at this particle's location.
Effective sample size (Neff)
A summary statistic of weight degeneracy: Neff = 1 / Σ(w̃m)². Ranges from 1 (all weight on one particle) to M (uniform weights). Low Neff signals that resampling is needed, or that the filter is suffering from particle deprivation.
Systematic resampling
A resampling strategy using a single random offset u ~ Uniform[0, 1/M] and M evenly-spaced pointers through the cumulative weight function. Reduces resampling variance from O(M) (multinomial) to O(1), and runs in O(M) time. The standard choice for mobile robot localization.
Particle deprivation
The condition in which all M particles are clustered near one (possibly incorrect) location, leaving no particles to represent alternative hypotheses. Occurs after convergence when diversity is lost. Recovery requires injecting new particles drawn from a broad prior, not from the current particle set.
Recovery augmentation
Injecting a fraction α of particles drawn uniformly from the state space at each filter cycle (or triggered by Neff dropping below a threshold). The standard defense against the kidnapped-robot problem. Implemented in Nav2's AMCL as recovery_alpha_fast/slow.
Monte Carlo Localization (MCL)
The application of the particle filter to the mobile robot localization problem: the state is the robot's 2D pose (x, y, θ), the map is known, and the filter maintains a particle distribution over the set of possible poses. Used for global localization and kidnapping recovery.
Curse of dimensionality
The exponential growth of the particle count needed to cover a state space as the state dimension increases. A particle filter that works with M = 1,000 for a 3D pose space would need M ~ 10⁶ for a 6D state space to maintain comparable coverage. This limits practical particle filter use to low-dimensional state spaces.

ACTIVE RECALLCheck your understanding

Answer in your own words first, then reveal.

1Why does the particle filter handle multimodal beliefs when the EKF cannot, even though both implement the Bayes filter?›

Both the EKF and particle filter are implementations of Bayes filtering, but they differ in how they represent the posterior belief. The EKF constrains the posterior to be Gaussian — a single mean and covariance. A Gaussian cannot represent two separated probability masses simultaneously; the best it can do is place the mean between them, which is a location where the robot definitely is not. The particle filter makes no distributional assumption: it carries the belief as a weighted set of M samples from the state space. Multiple high-weight clusters in different locations represent a genuinely multimodal belief. After a few more measurement updates that are consistent with one mode and inconsistent with the other, the filter naturally concentrates its particles on the correct mode through the weight-and-resample mechanism, without any special multimodal bookkeeping.

2A converged particle filter is kidnapped (the robot is physically moved). Describe, step by step, why the filter cannot self-recover without augmentation.›

After convergence, all M particles are clustered near the (former) correct pose. When the robot is kidnapped to a new location, no motion command is issued, so the predict step does not move the particles — they remain at the old location. At the weight step, the observation likelihood is evaluated for each particle: every particle is far from the true new pose, so every particle gets near-zero weight. The weights are then normalized — dividing near-zero numbers by their (very small) sum — which produces numerically noisy uniform-ish weights, but concentrated on whichever particle happened to have the highest likelihood in the wrong cluster. The resample step then duplicates these wrong particles. In subsequent cycles, the predict step spreads the cloud slightly via motion noise, but since all particles are in the wrong neighborhood, the weights remain low and the filter just shuffles wrong particles around. There is no mechanism to generate particles near the true new location; the filter is trapped. Augmentation (injecting random particles from the full state space) creates that mechanism: the injected particles are sparse and most receive low weights, but any that land near the true pose receive high weights and get duplicated, gradually shifting the population to the correct location.

3What does Neff = 1 mean, and why is it dangerous even if it arises right after the filter correctly converges?›

Neff = 1 / Σ(w̃m)² = 1 means one particle has importance weight ≈ 1 and all others have weight ≈ 0. The filter's entire belief is concentrated on one sample. If that sample happens to be at the correct pose, the point estimate is accurate — but the filter has lost all diversity. The danger: the next resample step will duplicate this one particle M times, producing M identical particles. The predict step will spread them by the motion noise model, but the spread is tiny (only one step of motion noise). If any unexpected event then causes the observation likelihood at that location to drop — a new obstacle, a person walking between the robot and the landmark, or an actual kidnapping — there are no alternative particles to up-weight. The filter will stubbornly remain at the previous mode with apparent confidence. Neff should be monitored as a health metric; its drop below M/2 is a warning to trigger resampling (if using adaptive resampling) or augmentation.

4Why is systematic resampling preferred over multinomial resampling in practice, and what does "O(1) variance" mean in this context?›

Multinomial resampling draws each of M new particles independently from the weight distribution. Because each draw is independent, a particle with weight 0.3 might be drawn 0, 1, 2, or 3 times in a set of 10 draws — there is randomness in how many copies each particle gets, beyond what the weights prescribe. This sampling variance is O(M) — it scales with the number of particles. Systematic resampling uses a single random offset u ~ Uniform[0, 1/M] and places M equally-spaced pointers at u, u + 1/M, u + 2/M, … across the cumulative weight function. Every particle with weight close to 1/M is nearly guaranteed to receive exactly one copy; the only randomness is in the single offset u, which is O(1) — it does not grow with M. In practice this means the particle population after systematic resampling is much more representative of the target distribution than after multinomial resampling with the same M. The filter achieves better localization accuracy with fewer particles, or equivalently, can run in real time with a smaller M while maintaining the same quality.

Next: IMU preintegration — fusing 200 Hz IMU between LIDAR updates →