Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Sheet 8 solutions
Exercise 1: Counting Model
A robot applies the so-called simple counting approach to build a grid map of a 1D en-
vironment consisting of the cells c0, . . . , c3. While standing in cell c0, the robot integrates
four measurements zt0 , . . . , zt3 . After integrating these measurements, the resulting belief
of the robot with regards to the occupancy of the four cells is b0 = 0, b1 = 14 , b2 =
2
3
, b3 = 1. Given that the first three measurements are zt0 = 1, zt1 = 2, zt2 = 3,
compute the value of the last measurement zt3 .
A counting model will compute the belief of a cell ci as:
bi =
hitsi
hitsi +missesi
For convenience, let us represent graphically what we know about the measurements. For
each measurement we denote with a shaded rectangle a hit, with an empty rectangle a
miss and with a dashed rectangle the area which is not subject to update:
c0 c1 c2 c3
zt0 = 1
zt1 = 2
zt2 = 3
This representation tells us that up until time t2 the hit/miss scenario is the following:
c0 c1 c2 c3
hits 0 1 1 1
misses 3 2 1 0
For each cell let us now consider the possible scenarios for a new measurement zt3:
• For b0 to be 0, either we get another miss or we should not be subject to update.
1
• For b1 to be 14 we necessarily need another miss, hence zt3 > 1.
• For b2 to be 23 we necessarily need another hit, hence we have zt3 = 2.
• For b3 to be 1, either we get another hit or the cell is not subject to update. The
latter is consistent with our observation of zt3 = 2.
We thus conclude that zt3 = 2.
Exercise 2: Occupancy Mapping
A robot has to build an occupancy grid map (cells c0, . . . cn) of a simple one-dimensional
environment using a sequence of measurements from a range sensor.
Assume a very simple sensor model: every grid cell with a distance (based on its coordi-
nate) smaller than the measured distance is assumed to be occupied with p = 0.3. Every
cell behind the measured distance is occupied with p = 0.6. Every cell located more
than 20cm behind the measured distance should not be updated. Calculate the resulting
occupancy grid map using the inverse sensor model (see mapping lecture slide 32) using
Python.
Assign the cell coordinates, which span from 0 to 200 (both endpoints included) with in-
crements of 10, to one array c and the belief values to another array m. Use matplotlib.
pyplot.plot(c,m) to visualize the belief. The measurements and the prior belief are
given in the following table.
Grid resolution 10 cm
Map length (1D only) 2 m
Robot position c0
Orientation (of the sensor) heading to cn (see figure)
Measurements (in cm) 101, 82, 91, 112, 99, 151, 96, 85, 99, 105
Prior 0.5
In order to solve this exercise we will use log-odds, as they provide a very simple update
formula, with only one addition and one subtraction.
Recall the log-odds update formula on slide 29 of the grid mapping lecture:
`(mi|z1:t, x1:t) = `(mi|zt, xt) + `(mi|z1:t−1, x1:t−1)− `(mi)
From the exercise we know that the prior should be (formula given on slide 28):
p(mi) = 0.5 ⇒ `(mi) = log p(mi)
1− p(mi) = 0
2
We also know that the inverse sensor model is the following:
p(mi|zt, xt) =
0.3 if position(mi) ≤ zt
0.6 if position(mi) > zt ∧ position(mi) ≤ zt + 20 cm
0.5(unused) if position(mi) > zt + 20 cm
The log-odds ratio should be applied to this function in order to obtain `(mi|zt, xt). Note
that unused in this context means we should not update the correspondingmi cells. Doing
an update with p(mi|zt, xt) = 0.5 would be equivalent, since l(0.5) = 0, but computa-
tionally more expensive.