After completing this chapter, you will be able to:
Particle filters are powerful tools for tracking and localization in non-linear, non-Gaussian environments. Unlike Kalman filters, which assume Gaussian noise and linear dynamics, particle filters can handle arbitrary probability distributions and complex constraints like walls and obstacles.
Instead of maintaining a single estimate (like Kalman filters), particle filters represent the probability distribution using a “swarm” of particles – each particle is a hypothesis about the true state.
Imagine you’re blindfolded in a shopping mall trying to figure out where you are:
The Swarm Approach: Your brain generates 1000 guesses (particles) about your location, scattered across the entire floor plan.
Step 1 - Move (Propagate): You walk 10 steps forward. Each of your 1000 hypothetical locations also “walks” 10 steps. Some guesses might now be inside walls (impossible).
Step 2 - Listen (Correct): You hear a fountain. Hypotheses near the fountain get “rewarded” (high weight), while hypotheses far from water get “penalized” (low weight).
Step 3 - Regenerate (Resample): You create 1000 new hypotheses, favoring the high-weight ones. Your swarm concentrates near likely locations.
After 30 seconds of walking: 95% of your particles cluster within 2 meters of your true location!
Why This Works for IoT:
Move each particle according to the motion model, adding noise:
\[x_i^{k|k-1} = f(x_i^{k-1}, u_k) + w_k\]
Where:
Example: If a person walks 10 steps north, move each particle 10 steps north plus Gaussian noise (+/-0.5 meters) for GPS drift, variable stride, etc.
Weight each particle by how well it matches sensor observations:
\[w_i^k = w_i^{k-1} \cdot p(z_k | x_i^{k|k-1})\]
Where:
Example: If Wi-Fi AP “AP-FoodCourt” shows -65 dBm:
Create a new generation of particles by sampling with probability proportional to weights:
Resampling methods:
Why resample? Without resampling, all particles eventually get near-zero weights (degeneracy problem). Resampling maintains particle diversity.
| Challenge | Kalman Filter | Particle Filter |
|---|---|---|
| Non-linear motion | Requires EKF/UKF | Handles arbitrary non-linearity |
| Non-Gaussian noise | Assumes Gaussian | Works with any distribution |
| Multi-modal distributions | Single peak only | Multiple peaks naturally |
| Map constraints | Difficult | Particles outside walls = 0 |
| Computational cost | Low (matrix ops) | Higher (scales with particle count) |
When to use particle filters:
When to avoid:
Scenario: Navigate a 3-floor shopping mall using smartphone Wi-Fi/BLE signals and IMU.
Setup:
Initial State (t=0):
Step 1: User Walks 10 Steps North (t=1-10s):
Propagate: Move each particle 10 steps north (15m total)
Step 2: Receive Wi-Fi Measurements (t=10s):
Correct: Calculate weight for each particle based on expected vs observed RSSI:
For each particle i at position (x,y):
expected_entrance = RSSI_model(distance(particle, entrance_AP))
expected_foodcourt = RSSI_model(distance(particle, foodcourt_AP))
likelihood = gaussian_pdf(observed_entrance - expected_entrance)
* gaussian_pdf(observed_foodcourt - expected_foodcourt)
weight[i] = previous_weight[i] * likelihoodParticles near entrance (matching -55 dBm): weight increases 10x Particles near food court (wrong signal): weight decreases 100x
Step 3: Resample:
Convergence (t=60s):
After walking through store, taking elevator, hearing escalator sounds:
| Application | Particles | Accuracy | CPU | Memory |
|---|---|---|---|---|
| Simple 2D tracking | 100-500 | Good | Low | ~4KB |
| Indoor localization | 500-2000 | Very good | Medium | ~20KB |
| Multi-floor building | 1000-5000 | Excellent | High | ~100KB |
| Autonomous vehicle | 5000-50000 | Precise | Very high | ~1MB |
Rule of thumb: Start with 500-1000 particles, increase if output is noisy or convergence is slow.
How many particles do you really need? Particle count trades accuracy vs computational cost.
For a 2D position problem (x, y) in a 50m × 50m area: - Uniform grid with 1m resolution: \(50 \times 50 = 2500\) cells - Coverage rule: Need ~10 particles per likely cell for good PDF approximation - If position uncertainty is 10m × 10m (100 cells), need \(100 \times 10 = 1000\) particles minimum
Computational cost (per update cycle):
For 10 Hz real-time: Max 100ms per cycle → Max ~12,000 particles on ESP32. For higher rates, reduce particle count or use fewer state variables.
Diminishing returns: Going from 500→1000 particles cuts error by ~30%. Going from 1000→2000 cuts error by only ~15%. Above 2000, gains are marginal unless tracking high-dimensional state.
Low Variance Resampling (recommended):
Effective Sample Size:
\[N_{eff} = \frac{1}{\sum_i (w_i)^2}\]
Resample when \(N_{eff} < N/2\) (too many low-weight particles)
Particle filters excel with map constraints:
| Filter | Linearity | Noise | Modality | Computation | Best For |
|---|---|---|---|---|---|
| Kalman | Linear | Gaussian | Unimodal | O(n^3) | GPS tracking |
| EKF | Weakly nonlinear | Gaussian | Unimodal | O(n^3) | GPS-IMU fusion |
| Particle | Any | Any | Any | O(N particles) | Indoor localization |
Choosing between these filters in production is rarely a pure accuracy decision. Compute budget, power consumption, and implementation complexity dominate the choice.
Case Study: Apple AirTag vs Tile Tracker localization
Apple AirTag uses a particle filter approach for its Find My network localization. When an AirTag is “lost,” every passing iPhone acts as a measurement source, reporting BLE RSSI. The cloud-side particle filter fuses these intermittent, asynchronous measurements from thousands of anonymous iPhones to estimate the AirTag’s position. A Kalman filter would fail here because: (1) measurements arrive at unpredictable intervals from random directions (non-uniform noise), (2) the AirTag could be in a pocket, a car, or outdoors (multi-modal signal propagation), and (3) urban environments create multipath reflections that violate Gaussian assumptions.
Tile, by contrast, uses a simpler trilateration approach with fewer participating devices. The accuracy difference (AirTag: ~3m median in urban areas vs Tile: ~15m) is largely attributable to Apple’s particle filter approach leveraging a billion-device measurement network.
Embedded constraint example: A Nordic nRF52840 MCU (256 KB RAM, 64 MHz Cortex-M4) can run a 500-particle filter for 2D indoor localization in approximately 8ms per update cycle. This consumes roughly 40 KB of RAM (500 particles x 4 state variables x 4 bytes x 5 for overhead). Increasing to 2,000 particles pushes computation to 35ms and memory to 160 KB – still feasible but leaving limited headroom for the BLE stack. On an ESP32 with 520 KB RAM and dual cores, 5,000 particles are practical, with one core dedicated to the filter and the other handling communications.
A particle filter for a 2D indoor positioning problem may work well with 1,000 particles but require 100,000 particles in a 3D problem with non-linear sensor models. The required particle count scales exponentially with state space dimensionality — this ‘curse of dimensionality’ limits particle filters to moderate state dimensions.
Naive multinomial resampling produces higher variance than systematic resampling and can cause particle impoverishment faster. Use systematic or stratified resampling to maintain particle diversity more efficiently.
A particle filter with 1,000 particles running at 100 Hz on a microcontroller will exceed available CPU capacity. Use the particle filter at fog/cloud tier and deploy a lightweight prediction-only filter at the edge for real-time state estimates between full filter updates.
Particle filters provide flexible state estimation for complex IoT scenarios:
Particle filters are like sending out a thousand tiny explorers to find where you really are!
Oh no! Bella the Battery lost her favorite toy somewhere in the Smart School! The school was BIG – three floors with hallways, classrooms, and a cafeteria. How could the Sensor Squad find it?
Max the Microcontroller had a brilliant idea: “Let us send out 1000 imaginary mini-scouts to search!”
Step 1 – Scatter the Scouts: Max scattered 1000 tiny imaginary scouts ALL over the school – in every hallway, every classroom, every floor. Each scout was a GUESS about where the toy might be.
Step 2 – Move the Scouts: Bella remembered, “I walked about 20 steps north after lunch.” So Max told all 1000 scouts: “Move 20 steps north!” But some scouts bumped into WALLS. “If you are inside a wall, you are in an impossible place – you are OUT!” said Max. 200 scouts disappeared.
Step 3 – Listen for Clues: Sammy the Sensor detected the toy’s Bluetooth signal. “It is a STRONG signal, so the toy must be nearby!” Scouts that were close to where the signal was strongest got GOLD STARS (high weight). Scouts far away got no stars.
Step 4 – Pick the Winners: Lila the LED helped with the next step: “Scouts with lots of gold stars get to CLONE themselves. Scouts with no stars are removed.” Now most of the 1000 scouts were clustered near the cafeteria on the 2nd floor!
After three more rounds of clues, 950 scouts were in the SAME corner of the cafeteria. “The toy must be THERE!” cheered Bella. And it was – sitting on a lunch tray!
“Each scout was a particle, and together they found the answer!” explained Max. “Even though no single scout knew where the toy was, the SWARM figured it out!”
| Word | What It Means |
|---|---|
| Particle | A tiny guess about where something might be |
| Propagate | Moving all the guesses based on what you know happened |
| Resample | Making copies of good guesses and removing bad ones |
| Converge | When all the guesses cluster together near the right answer |
| Multi-modal | When the answer could be in two or more different places at once |
Algorithms:
Applications:
Implementation:
Use particle filters when your problem has non-linear dynamics (walls, obstacles), non-Gaussian noise (Wi-Fi signals), or multi-modal distributions (could be on any floor). Start with 500-1000 particles and use systematic resampling triggered by effective sample size. For linear Gaussian problems, prefer Kalman filters for their lower computational cost and optimality guarantees.
| If you want to… | Read this |
|---|---|
| Compare with the Kalman filter for linear problems | Kalman Filter for IoT |
| Explore the complementary filter as a lightweight alternative | Complementary Filter and IMU Fusion |
| See particle filters applied in localisation and tracking | Data Fusion Applications |
| Understand fusion system architectures | Data Fusion Architectures |
| Return to the module overview | Data Fusion Introduction |