Log odds

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

U8.3MappingUniversity30 min

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: +0.85 then -0.85 returns a cell to where it started, which a probability multiplication does not.

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.

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 another minute of readings, 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: thin walls come out thicker than they are, and a map built from a badly localised robot blurs rather than showing you that it is confused.

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 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 and describe what happens to a wall seen at a glancing angle.