Building maps from sensor data: multi-sensor fusion, inverse measurement models, and MAP occupancy estimation.
So far we've assumed the robot has a map. But where do maps come from? Blueprints are rarely accurate — they don't include furniture, open doors, or recent renovations. A truly autonomous robot must build its own map from sensor data.
This chapter tackles a simplified version of the problem: mapping with known poses. We assume the robot knows exactly where it is at all times (perhaps from a very good localization system) and wants to build a map from its sensor readings.
The approach: represent the map as a grid of binary random variables. Each cell is either occupied (wall, furniture) or free (navigable space). The algorithm estimates the posterior probability of occupancy for each cell, given all sensor data collected along the known robot path.
The gold standard is the full posterior over the map:
where m is the map, z1:t all measurements, and x1:t the known path. But maps are enormous — tens of thousands of cells. The space of all possible maps is 210,000 or larger. Computing a full posterior is intractable.
The key approximation: factorize the posterior into independent per-cell estimates:
Each cell mi is estimated independently using the binary Bayes filter from Chapter 4. This ignores dependencies between neighboring cells (e.g., walls are continuous), but makes the problem tractable.
The algorithm maintains a log-odds value for each cell:
The update rule is beautifully simple:
where l0 = log(p(mi) / (1 - p(mi))) is the prior log-odds (typically 0 for a 50/50 prior).
| Log-odds l | Probability p | Meaning |
|---|---|---|
| l << 0 | p ≈ 0 | Definitely free |
| l = 0 | p = 0.5 | Unknown (prior) |
| l >> 0 | p ≈ 1 | Definitely occupied |
The inverse sensor model p(mi | xt, zt) is "inverse" because it reasons from effects (measurement) to causes (map). Given the robot pose and a range reading, what does this tell us about each grid cell?
For range finders, the model is intuitive:
• Cells before the measured endpoint (range < ztk - α/2): probably free (the beam passed through). Return lfree.
• Cells at the measured endpoint (|range - ztk| < α/2): probably occupied (the beam hit something). Return locc.
• Cells beyond the endpoint or outside the beam cone: unknown. Return l0 (no update).
| Cell Location | Return Value | Interpretation |
|---|---|---|
| In beam, before endpoint | lfree (< 0) | Free space |
| At beam endpoint | locc (> 0) | Obstacle |
| Beyond endpoint / outside beam | l0 (= 0) | No information |
Robots often have multiple sensor types: lasers, sonars, cameras. How do we combine them into one map?
Approach 1: Naive Bayes fusion. Run the occupancy grid algorithm with all sensors, updating the same log-odds grid. Problem: if sensor A sees an obstacle (a thin pole) but sensor B doesn't (sonar bounces off it), they produce conflicting evidence. The result depends on which sensor fires more often — not ideal.
Approach 2: Conservative fusion (recommended). Build a separate map for each sensor type. Combine them by taking the maximum occupancy:
If any sensor thinks a cell is occupied, the combined map marks it occupied. This is pessimistic (biased toward obstacles) but safe for navigation.
The hand-crafted inverse sensor model (Chapter 3) is simple but crude. Can we learn a better one from data?
The challenge: Bayes rule gives us the ideal inverse model:
But this integral is over all possible maps — intractable. We need to marginalize over all maps that agree with a given cell value mi.
The learning approach: Generate training data by sampling random maps, simulating sensor readings (forward model), and recording the (pose, measurement, cell occupancy) tuples. Then train a function approximator (logistic regression, neural network) to predict occupancy from pose and measurement.
However, the hand-crafted model works surprisingly well for laser range finders (which are clean and well-behaved). Learning is most valuable for noisy sensors like sonar or cameras.
The standard occupancy grid makes a strong independence assumption: each cell is estimated independently. This ignores spatial correlations — walls are lines, not random scattered points.
Maximum A Posteriori (MAP) occupancy mapping tries to find the single map that maximizes the full joint posterior:
This is the mode of the full posterior, not the product of per-cell modes.
In practice, MAP occupancy mapping is rarely used. The factored approach is fast, simple, and produces maps that are good enough for navigation. MAP methods are important theoretically, showing what we lose through independence assumptions.
An alternative to inverse sensor models: use forward models directly. The forward model p(z | x, m) is the physics-based model we already know from Chapter 6 — beam models, likelihood fields, etc.
Forward models have a clear advantage: they model the actual physics of sensing. They capture occlusion (cell B is hidden behind cell A), cross-cell dependencies, and sensor-specific effects naturally.
The challenge: forward models map from map to measurement, but we need to update the map given a measurement. This requires iterative optimization or sampling — much more expensive than the simple additive log-odds update.
| Approach | Pros | Cons |
|---|---|---|
| Inverse model | Fast (additive), simple | Ignores inter-cell dependencies |
| Forward model | Physically correct, handles occlusion | Slow (iterative), complex |
Watch an occupancy grid being built. The robot moves through a simple room, firing range beams. Cells in the beam path turn white (free); cells at beam endpoints turn black (occupied).
The robot (orange dot) casts beams into the environment. Free cells lighten, occupied cells darken. Click Step to advance the robot and update the map.
| Concept | Key Idea |
|---|---|
| Occupancy grid | Map as a grid of binary occupancy values, estimated independently per cell |
| Log-odds | Additive updates, numerically stable, fast |
| Inverse sensor model | p(mi | x, z): free before endpoint, occupied at endpoint |
| Multi-sensor fusion | Separate maps per sensor, combine with max |
| MAP occupancy | Maximize full joint posterior; theoretically better but expensive |
Occupancy grid mapping is one of the most successful algorithms in robotics. It is fast, robust, and produces maps that are immediately useful for path planning and navigation. The log-odds representation makes updates trivial, and the algorithm handles noisy sensors gracefully.