Assignment 3: Mapping and Estimation

COMP 417
Assignment 3: Mapping and Estimation (15 points)

Hand-in: As a single PDF file on My Courses.
Learning goal: Prep for MT2
Q1 (5 points): A 1D robot walks through the “2 door” environment, shown below.
The motion model is 𝑥𝑡 = 𝑥𝑡−1 + 𝑢𝑡−1 + 𝜖 with 𝜖~𝒩(0, 0.2
2
).
The measurement model is:
𝑝(𝑧𝑡
|𝑥𝑡) = {
𝑝(𝑧 == 1) = 0.9 𝑎𝑛𝑑 𝑝(𝑧 == 0) = 0.1, 𝑖𝑓 𝑥𝑡
𝑖𝑠 𝑖𝑛 𝑓𝑟𝑜𝑛𝑡 𝑜𝑓𝑎 𝑑𝑜𝑜𝑟
𝑝(𝑧 == 1) = 0.1 𝑎𝑛𝑑 𝑝(𝑧 == 0) = 0.9, 𝑖𝑓 𝑥𝑡
𝑖𝑠 𝑖𝑛 𝑓𝑟𝑜𝑛𝑡 𝑜𝑓𝑎 𝑤𝑎𝑙𝑙.
The robot is using a particle filter with N=10 particles to estimate is position. Its initial belief,
𝑏𝑒𝑙(𝑥0), is represented by 10 vertical lines, shown below, where the horizontal position (x-axis)
is the sampled state and the height (w-axis) is the particle weight (all are equal at this stage).
The robot takes two steps and makes two measurements: 𝑢0 = 1, 𝑧1 = 0, 𝑢1 = 1, 𝑧2 = 0.
Propose the value of one particle (state and weight) that is likely to be a part of the estimate of
𝑏𝑒𝑙(𝑥2). Show the series of computations that would lead to these values, starting from the
𝑏𝑒𝑙(𝑥0) shown and mentioning each intermediate value computed along the way, as the controls
and measurements are processed by the algorithm.
Note that a particle filter has inherent randomness, so there are many different proposals
possible. Marking will be based on the details used to justify yours. However, do not assume
extremely unlikely events, as this would be interpreted as a lack of understanding.
-1 0 1 2 3 4
0.1
w
x
Q2 (5 points): Assume that a robot’s belief in its current state, 𝒙, is modeled as a normal
distribution (Gaussian), over the x, and y dimensions of a 2D state-space. This means the
likelihood of it being at any state is:
𝑝(𝒙) ∝ 𝑒
−(𝑥−𝜇)
𝑇Σ
−1
(𝑥−𝜇)
,
for mean vector 𝜇 = [
𝜇𝑥
𝜇𝑦
] and covariance matrix Σ = [
𝑉𝑎𝑟(𝑥) 𝐶𝑜𝑣(𝑥, 𝑦)
𝐶𝑜𝑣(𝑥, 𝑦) 𝑉𝑎𝑟(𝑦)
].
A robot begins from the origin (0,0) with perfect certainty of its location. The robot is omnidirectional and can control its cross-track error precisely, with 1 cm/m variance, but it has poor
distance control, making 10 cm/m variance errors in stopping distance. It moves to the point
(1,1) along two different paths:
a) Straight-line: It tries to move sqrt(2) meters in the 45 degree direction along line y=x.
b) L-shaped: It tries to move 1 meter right and then 1 meter up.
Write the 6 values that describe the Gaussian (2 mean vector terms, 4 covariance matrix terms)
for situations a) and b). Sketch the ellipse formed by the 1-sigma confidence bound. Explain
your reasoning – the explanation and correct mapping between the meaning of the terms and
the problem situation are more important than the precise values computed.
Q3: Assume a robot with a 1D state-space starts at the origin (x=0), it makes 2 motions,
following controls 𝑢0 and 𝑢1, and takes two sensory measurements, 𝑧1 and 𝑧2, of the a
landmark, 𝑚1 with known position (that is, we are doing localization, not SLAM).
Using the probabilistic form of the Bayes filter, write out the expression for 𝑝(𝑥2|𝑢0, 𝑢1, 𝑧1, 𝑧2),
also known as our belief in the robot’s location at time t=2, 𝑏𝑒𝑙(𝑥2
). Make sure your final
expression is composed of only the 3 basic elements of a Bayes filter:
a) The initial belief (the belief in the robot’s location at time 0), 𝑝(𝑥0
) = 𝑏𝑒𝑙(𝑥0
).
b) The measurement model, 𝑝(𝑧𝑡
|𝑥𝑡
)
c) The motion model, 𝑝(𝑥𝑡
|𝑥𝑡−1, 𝑢𝑡−1)
(of course, each of these can be repeated, have their t indices replaced by integers, and
combined in math as needed)
Show your work and clearly draw a box around the final expression.
𝑚1
𝑢0
𝑥1
𝑧1
𝑧2
𝑢1
𝑥2
𝑥0