A map as a lattice of beliefs — each cell probably free or probably full. Every range reading updates the cells along the beam by an inverse sensor model: add log-odds for a hit, subtract for a miss. Storing log-odds instead of raw probability turns a fragile product of tiny numbers into a stable running sum — and makes the update exactly the per-cell Bayes filter. Rendered, not quoted.
Each cell holds a scalar l, its log-odds of being occupied, starting at 0 (prior 0.5). A reading updates one cell additively:
l ← l + L_hit on a hit, l ← l + L_miss on a miss, with L_hit = ln(p/(1−p)) and L_miss = −L_hit.
Occupancy probability is recovered by p = σ(l) = 1/(1+e^−l). Because the prior is 0.5, the running sum of log-odds is the Bayesian posterior odds — no normalisation step, no drift.
Neighbour sphere: the-bayes. Bayes’ rule applied per cell, carried in log-odds — Elfes and Moravec’s occupancy grid. The map is a field of independent binary Bayes filters; the log-odds form is what makes thousands of noisy readings accumulate into a stable estimate rather than collapse.
Robust to sensor noise by construction: a wrong reading nudges one cell by ±L, and consistent evidence outvotes it.
Live re-check of a well-observed free cell (3000 miss readings): the log-odds estimate must stay finite and equal the closed-form posterior (≈0). If the engine is tampered, the raw-product form underflows to 0/0 = NaN and this badge flips red.
A ranging sensor sweeps rays from the robot. Each ray marks the cells it passes through as miss (probably free) and the cell it stops on as hit (probably full). Readings carry ~8% flip noise, applied from a fixed seed.
The proven map: for every cell, the additive log-odds estimate equals the exact per-cell Bayesian posterior, and long observation sequences never underflow.
wall The occupancy grid assumes cell independence — each cell filtered alone. Real worlds have structure: a doorway, a thin table leg, a glass wall the sonar sees through. Independence lets a beam paint a whole corridor free and miss the chair in it.
The inverse sensor model itself is a hand-tuned assumption (AMBER): wrong beam width or range variance biases every update. Dynamic obstacles violate the static-world premise outright.
“Just multiply the cell’s occupancy probability by each reading’s likelihood.”
→ Products of many numbers below 1 underflow to 0; a well-observed cell becomes 0/0. Add log-odds instead.
“A confident cell should saturate at p = 1.”
→ Hard 1 or 0 can never be revised when the world changes. Log-odds is clamped to ±20 so the map can still learn.
“Order the updates for accuracy.”
→ Addition is commutative; the estimate is order-independent by construction. The verifier shuffles and confirms.
Disclosed planted void. This swaps the additive log-odds for the naive form — multiply raw probabilities directly. Algebraically identical, but a long sequence underflows: a certified-free cell collapses to NaN and can no longer be read as free. The Witness (7) catches it live.