Worksheet

U8.5 Ray casting the map

Mapping · University · about 35 min

What this lesson is about

The forward model: given a map and a pose, what would the sensor read?

• Why it matters
• The cost, and what everybody does about it
• Doing it
• Unknown is not occupied

Questions 6 marks in all

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

   CELL = 5.0
   occupied_row = 6
   y = 2.0
   r = 0.0
   while int((y + r) / CELL) < occupied_row:
       r += 1.0
   surface = 33.0
   print(r, surface - y)
   

2. [1 mark]A ray caster's predictions are consistently a few centimetres shorter than the real readings. Why?

   1. AIt stops on entering an occupied cell, so it reports the near edge of the cell rather than the surface inside it
   2. BThe sensor adds a constant offset to every reading
   3. CThe steps of 1 cm skip past thin walls
   4. DUnknown cells are being treated as blocked

3. [1 mark]A particle filter has 300 particles and uses 2 beams each, at 10 Hz, and each ray cast marches 150 steps. How many grid lookups is that per second?

4. [1 mark]What does a likelihood field precompute, and what does it save?

   1. AThe distance from every cell to the nearest occupied cell, so scoring a beam is one lookup at its end point instead of a march
   2. BThe ray cast from every cell in every direction, so no casting is needed at run time
   3. CThe log odds of every cell, so the grid need not be stored
   4. DThe frontier cells, so exploration is faster

5. [1 mark]A planner uses a ray cast to ask whether a straight route is safe. How should that caster treat unknown cells?

   1. AAs blocked, so the robot never drives into a place it has not looked at
   2. BAs free, so it is only scored on evidence it has
   3. CAs occupied only if they are next to a known wall
   4. DIt makes no difference to the answer

6. [1 mark]Why can using two of the eight beams improve the estimate as well as the speed?

   1. ANeighbouring beams are correlated, and treating eight near-identical beams as independent makes the filter overconfident
   2. BThe outer beams are always less accurate than the inner ones
   3. CFewer beams mean less half-cell bias
   4. DThe weights underflow when more than two are multiplied

The task: predict a reading from the map

Standing at (100, 50), build a map from the scans. Then ray cast from a pose 20 cm behind the robot and print predicted:. Drive back 20 cm, measure, and print measured: and error:.

from bugbot import *
import math
connect()

CELL, W = 5.0, 40
L_OCC, L_FREE, L_MAX, FAR = 0.85, -0.4, 8.0, 170.0
START_X, START_Y = 100.0, 50.0
grid = [0.0] * (W * W)

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

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

Challenges

1. Cast rays at the eight angles scan() uses and compare the whole predicted fan with the real one.
2. Add a mode that treats unknown cells as blocked and see how much shorter the predictions get.
3. Time 1,000 casts. How many particles could you afford at 10 Hz?