Log odds

Why the cells hold a log odds and not a probability, and what the clamp is for.

U8.3MappingUniversity30 min

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: SLAM explained: simultaneous localisation and mapping

A cell should hold a probability that it is occupied. Almost nobody stores one, and the reason is worth understanding properly, because the same trick appears everywhere in probabilistic robotics.

The problem with probabilities

Combining independent evidence with Bayes' rule means multiplying:

p_new = p_old * p_reading / normaliser

Three things go wrong. The multiplication needs a normaliser, so every update touches two terms. Repeated multiplication of numbers below one underflows towards zero, and floating point resolution near 0 and near 1 is where the interesting cells live. And a cell that has reached 0.0 or 1.0 can never be argued out of it again, so one bad reading is permanent.

The odds, and their logarithm

Define the odds as p / (1 - p), and the log odds as its natural logarithm:

l = log(p / (1 - p))

Now Bayes' rule becomes addition:

l = l + l_reading

No multiplication, no normaliser, no underflow. An unknown cell is exactly 0, which is also what an array of zeros gives you for free. The range is the whole real line, so nothing saturates by accident. And evidence is symmetric where you can see it: +0.85 then -0.85 returns a cell exactly to where it started. The same two updates done as probabilities also cancel, but only once the normalisers have been worked through, and not at all once a cell has rounded to 1.0.

This function has other names in other rooms. It is the logit, it is the inverse of the logistic function, and it is the same quantity a neural network's final layer produces before a sigmoid. Recognising it in all three places is part of the job.

Getting back to a probability

p = 1.0 / (1.0 + math.exp(-l))

You only need this to draw the map or to hand it to something that wants probabilities. The mapper itself never converts.

The two constants

L_OCC  = +0.85      # a hit: this cell just became more likely occupied
L_FREE = -0.40      # a pass-through: less likely

L_OCC corresponds to a single reading being right about occupancy with probability 0.7, and L_FREE to a pass-through being right with about 0.6. They are deliberately timid. One reading should not settle a cell, because one reading is often wrong, and twenty agreeing readings should settle it firmly.

|L_OCC| > |L_FREE| in almost every implementation. A hit is the stronger evidence: things that reflect are really there, whereas a beam passing through a cell can happen to miss a thin object in it.

Both constants are per beam. The half-cell steps from U8.2 land in most cells twice, and a mapper that adds L_FREE at every step gives each pass -0.8, nearly as much as a hit, which quietly undoes the point of the paragraph above. Collect the cells a beam crosses in a set and add L_FREE to each of them once.

The clamp, which is not optional

l = max(-L_MAX, min(L_MAX, l + update))

with L_MAX about 10, which is a probability of 0.99995.

Without it, a robot that stares at a wall for a minute drives that cell's log odds to several hundred. The map is now so certain that when the wall is moved, undoing that certainty takes more than two minutes of readings, because each pass-through takes off 0.4 where each hit put on 0.85, during which the robot plans around a wall that is not there. The clamp caps how confident a cell may become, and therefore caps how long it takes to change its mind. It is what makes the map able to handle a world that moves.

from bugbot import *
import math
connect()

L_OCC, L_FREE, L_MAX = 0.85, -0.4, 10.0

def p_of(l):
    return 1.0 / (1.0 + math.exp(-l))

l = 0.0
for i in range(30):
    l = max(-L_MAX, min(L_MAX, l + L_OCC))
    if i in (0, 1, 4, 9, 19, 29):
        print("after", i + 1, "hits: l =", round(l, 2), " p =", round(p_of(l), 5))

print("and three pass-throughs later:", round(p_of(l + 3 * L_FREE), 5))

Run this in the simulator

Note how flat the probability column goes after ten hits while the log odds keeps climbing to the clamp. That headroom is the map's resistance to a single wrong reading, and the clamp is what stops the headroom becoming infinite.

What a grid cannot represent

Worth saying once, plainly. The standard grid assumes cells are independent, and they are not: a wall is a run of correlated cells, and one beam's evidence really bears on all the cells it crosses at once. The assumption is wrong and the maps are good anyway, which is a common state of affairs in this subject.

Where it shows: a map built from a badly localised robot blurs rather than showing you that it is confused.

Walls that come out a cell too thick are a different effect, and a plainer one. Readings wobble by a centimetre or two, so a reading that comes back short puts its hit in the floor cell just in front of the wall. The free marking stops a cell short of every hit, so it reaches that cell only when a reading comes back long, and not always then. The cell gets more hits than passes, each hit outweighs a pass, and it ends up occupied. U8.4 shows it on a real map.

Task: adding up the evidence

Print p one:, the probability a cell is occupied after one hit starting from an empty map. Then take 25 readings, updating a grid in log odds with a clamp at 10 and each cell changed at most once per reading, and print wall l: and wall p: for the cell the wall is in.

from bugbot import *
import math
connect()

CELL = 5.0
L_OCC, L_FREE, L_MAX = 0.85, -0.4, 10.0
X0, Y0 = 100.0, 50.0

Challenges

1. How many hits does it take to get from 0.5 to 0.99, and how many more to reach the clamp?
2. Remove the clamp and work out how many readings it would then take to talk the cell back down to 0.5.
3. Set L_FREE to -0.85 as well, run the map in U8.4, and look at the row just in front of the wall. What changes, and what have you given up to get it?