%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#2C3E50', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#f5f5f5'}}}%%
flowchart TD
subgraph Sample["1. PROPAGATE"]
S1["Move particles<br/>according to motion model"]
S2["Add process noise"]
end
subgraph Weight["2. CORRECT"]
W1["Weight each particle<br/>by measurement likelihood"]
W2["Particles in walls = 0"]
end
subgraph Resample["3. RESAMPLE"]
R1["Clone high-weight particles"]
R2["Eliminate low-weight particles"]
end
Sample --> Weight --> Resample
Resample -.->|"Next iteration"| Sample
style Sample fill:#2C3E50,color:#fff
style Weight fill:#E67E22,color:#fff
style Resample fill:#16A085,color:#fff
1272 Particle Filters for Indoor Localization
Learning Objectives
After completing this chapter, you will be able to:
- Understand particle filter principles and when to use them
- Implement the propagate-correct-resample cycle
- Apply particle filters to indoor localization
- Handle non-linear systems and multi-modal distributions
- Choose between Kalman and particle filters
1272.1 Introduction to Particle Filters
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.
1272.1.1 The Core Idea: A Swarm of Hypotheses
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.
TipFor Beginners: Understanding Particle Filters
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:
- Wi-Fi/BLE signals aren’t perfect circles (non-Gaussian)
- Buildings have walls that block paths (non-linear constraints)
- Multiple possible locations might match sensor readings initially
1272.2 The Propagate-Correct-Resample Algorithm
1272.2.1 Step 1: Propagate (Prediction)
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:
- \(f(\cdot)\): Motion model (position = position + velocity x dt)
- \(u_k\): Control input (e.g., commanded velocity from IMU)
- \(w_k\): Process noise (adds randomness)
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.
1272.2.2 Step 2: Correct (Update Weights)
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:
- \(p(z_k | x_i)\): Likelihood of measurement given particle state
- Particles matching measurements get high weights
- Particles in impossible locations (walls) get zero weight
Example: If Wi-Fi AP “AP-FoodCourt” shows -65 dBm:
- Particles 5m from AP (expected -65 dBm) get high weight
- Particles 50m away (expected -85 dBm) get low weight
- Particles inside concrete walls get zero weight
1272.2.3 Step 3: Resample (Regenerate)
Create a new generation of particles by sampling with probability proportional to weights:
- High-weight particles: Duplicated (likely locations get more samples)
- Low-weight particles: Eliminated (unlikely locations discarded)
- Result: Particles concentrate around high-probability regions
Resampling methods:
- Multinomial resampling: Draw N particles randomly with replacement
- Systematic resampling: Deterministic, lower variance (preferred)
- Residual resampling: Guarantees high-weight particles survive
Why resample? Without resampling, all particles eventually get near-zero weights (degeneracy problem). Resampling maintains particle diversity.
1272.3 When to Use Particle Filters
TipParticle Filter vs Kalman Filter
| 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:
- Indoor localization with Wi-Fi/BLE (signal propagation is non-linear)
- Robot kidnapping problem (unknown initial position)
- Tracking with ambiguous measurements (bearing-only tracking)
- Systems with map constraints (buildings, road networks)
When to avoid:
- Linear systems with Gaussian noise (Kalman is optimal and faster)
- Real-time embedded systems with limited CPU
- High-dimensional state spaces (curse of dimensionality)
1272.5 Particle Filter Design Decisions
1272.5.1 Number of Particles
| 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.
1272.5.2 Resampling Strategies
Low Variance Resampling (recommended):
- Deterministic selection with single random offset
- Lower variance than multinomial
- Guarantees representative sample
Effective Sample Size:
\[N_{eff} = \frac{1}{\sum_i (w_i)^2}\]
Resample when \(N_{eff} < N/2\) (too many low-weight particles)
1272.5.3 Map Integration
Particle filters excel with map constraints:
- Wall collision detection: Set weight = 0 for particles inside walls
- Semantic constraints: Elevator particles can only move vertically
- Floor transitions: Only allow through stairs, elevators, escalators
- Occupancy grids: Precompute traversable areas
1272.6 Comparison with Other Filters
| 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 |
1272.7 Summary
Particle filters provide flexible state estimation for complex IoT scenarios:
- Swarm of hypotheses: Represent uncertainty with many particles
- Propagate-Correct-Resample: The fundamental algorithm cycle
- Map constraints: Natural handling of walls and obstacles
- Multi-modal: Can track multiple possible locations simultaneously
- Trade-off: More computation than Kalman, but handles non-linearity
1272.8 What’s Next
- Fusion Architectures - Centralized vs distributed fusion
- Real-World Applications - Smartphone rotation, activity recognition
- Best Practices - Common pitfalls to avoid
- Exercises - Practice implementing particle filters