Homework answers / question archive / COMP 417, Fall 2020 Assignment 3: Mapping and Estimation (15 points) Out: Nov 5, 2020 Due: Nov 12, 2020 – 2pm (I cannot offer any extensions as the midterm starts right after)   Hand-in: As a single PDF file on My Courses

COMP 417, Fall 2020 Assignment 3: Mapping and Estimation (15 points) Out: Nov 5, 2020 Due: Nov 12, 2020 – 2pm (I cannot offer any extensions as the midterm starts right after)   Hand-in: As a single PDF file on My Courses

Computer Science

Share With

---

COMP 417, Fall 2020

Assignment 3: Mapping and Estimation (15 points)

Out: Nov 5, 2020

Due: Nov 12, 2020 – 2pm (I cannot offer any extensions as the midterm starts right after)

 

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²).  The measurement model is:

 

. 

 

 

The robot is using a particle filter with N=10 particles to estimate is position. Its initial belief, ????????????(????₀), 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: ????₀ = 1, ????₁ = 0, ????₁ = 1, ????₂ = 0. 

 

Propose the value of one particle (state and weight) that is likely to be a part of the estimate of

????????????(????₂). Show the series of computations that would lead to these values, starting from the ????????????(????₀) 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.

 

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:

 

????(????) ∝ ????−(????−????)^????Σ⁻¹(????−????),

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:

 

1. Straight-line: It tries to move sqrt(2) meters in the 45 degree direction along line y=x.
2. 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 ????₀ and ????₁, and takes two sensory measurements,

 

 and ????₂, of the a landmark, ????₁ with known position (that is, we are doing localization, not SLAM). 

 

 

????

1

????

0

????

1

????

1

????

2

????

1

????

2

????

0

 

Using the probabilistic form of the Bayes filter, write out the expression for ????(????₂|????₀, ????₁, ????₁, ????₂), also known as our belief in the robot’s location at time t=2, ????????????(????₂). Make sure your final expression is composed of only the 3 basic elements of a Bayes filter:

1. The initial belief (the belief in the robot’s location at time 0), ????(????₀) = ????????????(????₀).
2. The measurement model, ????(????_????|????_????)
3. 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.