Worksheet

U8.3 Log odds

Mapping · University · about 30 min

What this lesson is about

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

• The problem with probabilities
• The odds, and their logarithm
• Getting back to a probability
• The two constants
• The clamp, which is not optional
• What a grid cannot represent

Questions 8 marks in all

1. [1 mark]What does this program print?

   import math
   p = 0.7
   l = math.log(p / (1 - p))
   print(round(l, 2))
   print(round(1.0 / (1.0 + math.exp(-l)), 2))
   

2. [1 mark]What does this program print?

   import math
   L_OCC, L_FREE, L_MAX = 0.85, -0.4, 10.0
   l = 0.0
   for update in (L_OCC, L_OCC, L_FREE, L_OCC, L_FREE):
       l = max(-L_MAX, min(L_MAX, l + update))
   print(round(l, 2), round(1.0 / (1.0 + math.exp(-l)), 3))
   

3. [1 mark]Why do occupancy grids store log odds rather than probabilities?

   1. ABayes' rule becomes addition, with no normaliser, no underflow, and no cell stuck for ever at 0 or 1
   2. BLog odds use less memory than a probability
   3. CLog odds make neighbouring cells independent
   4. DLog odds are always between 0 and 1, so they are easier to draw

4. [1 mark]Why is |L_OCC| larger than |L_FREE| in almost every implementation?

   1. AA hit is stronger evidence: things that reflect are there, but a beam can pass through a cell and miss a thin object in it
   2. BOccupied cells are rarer, so they need a larger update to be seen
   3. CIt stops free space growing faster than walls
   4. DIt corrects for the half-cell bias of ray casting

5. [1 mark]A mapper steps along each beam in half cells and adds L_FREE = -0.4 at every step. What is one beam passing through a cell really worth?

   1. AAbout -0.8, nearly as much as a hit, because the steps land in most cells twice
   2. B-0.4, as intended
   3. C-0.2, because each step covers only half a cell
   4. DNothing, because the second step cancels the first

6. [1 mark]What is the main purpose of clamping each cell's log odds to plus or minus 10?

   1. AIt caps how confident a cell can become, and so how long it takes to change its mind when the world changes
   2. BIt prevents floating point overflow
   3. CIt keeps the probability exactly between 0.1 and 0.9
   4. DIt stops free cells becoming frontiers

7. [1 mark]A cell starts unknown at log odds 0 and receives only hits of +0.85, with a clamp at 10. How many hits does it take to reach the clamp?

8. [1 mark]The function log(p / (1 - p)) has another standard name, the inverse of the logistic function. What is it?

The 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

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/u8-3-log-odds/
The simulator checks it and tells you when it passes. Nothing to install, no account.

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?