Sheet 8 solutions
July 3, 2019
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.
The solution of this exercise will thus involve applying for each measurement and for each
cell the log-odds update formula. Once we are done with that we convert from log-odds
to probability and display the output. Note that the inverse transformation is the unique
solution w.r.t. p of the log-odds definition:
` = log
p
1− p ⇒ exp ` =
p
1− p
⇒ (1− p) exp ` = p ⇒ exp ` = p(1 + exp `)
⇒ p = exp `
1 + exp `
=
exp `+ 1− 1
1 + exp `
= 1− 1
1 + exp `
import numpy as np
import matplotlib.pyplot as plt
# Inverse sensor model in log-odds form
def log_inv_sensor_model(z, c):
if c > z - 10:
# The sensor detects a wall for this cell
return np.log(0.6 / (1 - 0.6))
# The sensor detects free space for this cell
return np.log(0.3 / (1 - 0.3))
# Cell position (in cm) for each cell
c = range(0, 201, 10)
# Map belief in log-odds form
logodds = np.zeros(len(c))
# Set of measurements (in cm)
meas = [101, 82, 91, 112, 99, 151, 96, 85, 99, 105]
# Initial prior of the cells, the non informative prior of p = 0.5 will
# yield 0 in log-odds form, so technically we could leave it out in the
# the log-odds update formula
prior = np.log(0.5 / (1 - 0.5))
print("prior:", prior)
# Integrate each measurement
for i in range(len(meas)):
# Update every cell of the map
3
for j in range(len(c)):
# Anything beyond 20cm of the measurement should not be updated
if c[j] > meas[i] + 20:
continue
# Log-odds update formula for the cells
logodds[j] = logodds[j] - prior + log_inv_sensor_model(meas[i], c[j])
# Apply the inverse transformation from log-odds to probability
m = 1 - 1. / (1 + np.exp(logodds))
# Plot the resulting estimate
plt.plot(c, m)
plt.xlabel("x-position [cm]")
plt.ylabel("occupancy p(x)")
plt.savefig("graph.pdf")
plt.show()
The resulting belief is the following:
0 25 50 75 100 125 150 175 200
x-position [cm]
0.0
0.2
0.4
0.6
0.8
oc
cu
pa
nc
y
p(
x)
Note that the resulting graph is not a distribution, i.e., it does not normalize to 1. Rather,
each vertex of the curve represents the parameter of a Bernoulli distribution associated to
the corresponding cell.
Exercise 3: Occupancy Mapping
Prove that in the occupancy grid mapping framework the occupancy value of a grid cell
P (mj|x1:t; z1:t) is independent of the order in which the measurements are integrated.
4
Let us consider the log-odds update formula and let us recursively unwrap it:
`(mi|z1:t, x1:t) = `(mi|zt, xt) + `(mi|z1:t−1, x1:t−1)− `(mi) =
= `(mi|zt, xt) + `(mi|zt−1, xt−1) + `(mi|z1:t−2, x1:t−2)− 2 · `(mi) =
= . . . =
t∑
k=1
`(mi|zk, xk)− t · `(mi)
It is clear that `(mi|z1:t, x1:t) is simply a sum of the log-odds form of the inverse mea-
surements. Suppose that we exchange a measurement at time i with the measurement at
a different time j. Since the sum is a commutative operator we will still obtain the same
value of `(mi|z1:t, x1:t). Hence, we can repeat exchanging measurements to obtain any
order permutation of the measurements without changing the result. Finally, since the
log-odds value does not change, neither will the corresponding probability.