slam.txt (2863B)
1 =============================================================================== 2 SLAM (Simultaneous Localization and Mapping) 3 =============================================================================== 4 5 SLAM = Simultaneous Localization and Mapping. A robot dropped into an unknown 6 environment has to build a map and figure out where it is in that map — at the 7 same time. The circularity is the whole problem: a good map requires knowing 8 where you were when you took each measurement, and knowing where you are 9 requires a map to measure against. Wheel odometry drifts, sensors are noisy, 10 so neither side is ever known exactly. 11 12 The Bayesian formulation. You define a joint posterior over trajectory and map 13 given everything observed: 14 15 p(x₁:ₜ, m | z₁:ₜ, u₁:ₜ) 16 17 where x is pose, m is the map, z are sensor readings, u are control/odometry 18 inputs. That's it — SLAM is the problem of computing this posterior, and every 19 algorithm is a different tractable approximation of it. 20 21 The recursion is the Bayes filter from before, with the map bolted into the state: 22 23 • Predict: apply the motion model p(xₜ | xₜ₋₁, uₜ). You moved forward 1m ± noise, 24 so the pose belief smears out. 25 26 • Update: apply the observation model p(zₜ | xₜ, m). A laser scan that matches 27 a known wall sharpens the belief; the map cells get updated too. 28 29 Why the naive version fails. The map has thousands of landmarks, and observing 30 one landmark correlates it with the robot pose and thus with every other 31 landmark. A full covariance matrix over N landmarks is O(N²) to store and 32 update, which is why EKF-SLAM chokes past a few hundred features. 33 34 The workarounds are the interesting part: 35 36 FastSLAM uses a Rao-Blackwellized particle filter. Key insight: conditioned on 37 a known trajectory, the landmarks are independent of each other. So sample 38 trajectories as particles, and attach a small independent EKF per landmark 39 per particle. The correlation problem dissolves. 40 41 Graph SLAM / factor graphs (GTSAM, g2o, Ceres) — the modern default. 42 Drop the filter, keep every pose as a node and every measurement as a 43 constraint edge. Under Gaussian noise, maximizing the joint posterior is 44 equivalent to minimizing a sum of squared residuals, so it becomes sparse 45 nonlinear least squares. The information matrix is sparse because each 46 measurement touches only a few poses, which is what makes it scale. 47 48 Loop closure is where the Bayesian machinery earns its keep. Recognizing 49 "I've been here before" injects a constraint linking two distant poses, and 50 the optimizer redistributes accumulated drift backward across the whole 51 trajectory. Getting one wrong catastrophically corrupts the map, so place 52 recognition usually pairs with robust kernels or switchable constraints — 53 themselves a way of putting a heavier-tailed prior on the residuals so 54 outliers can't dominate.