FastSLAM

FastSLAM splits SLAM into easy pieces. Each particle is one guess of the robot's whole path, and given that path, every landmark can be estimated on its own with a tiny 2D Kalman filter. Particles whose maps explain the readings well are kept, and the rest are dropped.

Number of particles Odometry noise

Factoring the problem

If the robot's path were known exactly, the landmarks would be independent of each other. FastSLAM uses that fact:

$$p(\mathbf{x}_{1:t}, \mathbf{m} \mid \mathbf{z}, \mathbf{u}) = p(\mathbf{x}_{1:t} \mid \mathbf{z}, \mathbf{u}) \prod_{j=1}^{N} p(\mathbf{m}_j \mid \mathbf{x}_{1:t}, \mathbf{z})$$

The path is tracked by particles, and each particle keeps $N$ small 2D EKFs, one per landmark. The cost grows with $N$ instead of $N^2$.

What to notice

The particles spread as the robot drives, then tighten when it sees landmarks it already mapped. Each faint cloud of triangles is one particle's map. Too few particles and the filter can lose the true path, a problem called particle depletion, which is worst on long loops. FastSLAM was among the first SLAM methods to scale to large maps, and its grid-based cousin is behind the GMapping package used in early ROS.