• Introduction
• Emulator API
• Initialization
• Step 1: Motion Update
• Step 2: Measurement Model
• Step 3: Normalization
• Lab Report
• Submission
• Hints

Introduction

For this lab we will implement Markov Localization to localize a simulated robot. We will do this by setting up the robot to detect if it adjacent to a door along a one dimensional hallway. Knowing the locations of the doors, along with the motion of the robot and when it detects a door, we can estimate the robot’s location.

Emulator API

Download the Robot.m MATLAB class into the same folder where you will be writing your MATLAB script for this lab. The Robot class can be used as follows. First, an instance of the class must be constructed by running,

robot = Robot(dt);

where dt is the amount of time to wait between plotting future steps, and robot is the instance of the Robot class. When initialized, a plot showing the probability density function of the robot location, the location of the doors, and the true location of the robot is shown. Next, running,

[detected, dx] = robot.step(pdf);

updates the plot with the new probability density function pdf, and returns two values, dx, the displacement of the robot since the last time Robot.step() was called, and detected, whether a door was detected at the current location. After the robot is finished moving, calling Robot.step() will return that the displacement dx is zero.

The Robot class also has other variable which will be useful:

Robot.x

An array of locations to evaluate the probability of the robot currently being located.

Robot.door_locations

An array of the locations of each of the doors in the simulated environment.

Initialization

At first, we will assume that we don’t know where the robot is located. Therefore, the probability density function should be constant.

Reminder: a probability density function must sum to one.

The following steps can be used to implement Markov Localization.

Step 1: Motion Update

The first step is to update the PDF with the motion model. This can be done by convolving the current PDF with the PDF of our motion model,

where,

where $\Delta x$ is the distance the robot has moved since the last time the Markov Localization code was run. As a reminder,

This can be done in MATLAB using the conv() function. For example,

pdf = conv(pdf, motion_model, "same");

Step 2: Measurement Model

The second step is to apply our measurement. If the detected value return by Robot.step() is true, we are next to one of the doors. Therefore, we will multiply our current PDF of the robot location, $p(x_t|x_{t-1},u_t)$, by the PDF of the measurement, $p(z_t|x_t,m)$. If the door is not detected, we will do nothing. We can calculate $p(z_t|x_t,m)$ as,

where $\alpha$ is a scaling factor and $m_k$ is the location of the $k$th door. Since the probability density function must integrate to one (analogously the probability mass function must sum to one) we can start by setting $\alpha$ to one, then divide the PDF by its sum, i.e.,

p = p / sum(p);

Step 3: Normalization

After the previous two steps of the Markov Localization algorithm, the PDF of the robot location may not sum (e.g., integrate) to one. Therefore, Normalization is required. As in the previous step, this can be done by dividing the PDF by its sum,

pdf = pdf / sum(pdf);

Don’t forget to check if dx is zero to know when to end your loop!

Lab Report

After completing the code for this lab, write a lab report which includes several plots of your data at interesting points in time. Also include the typical sections described in the lab policies sections of the syllabus.

Submission

Turn in a PDF copy of your lab report created using LaTeX or Microsoft Word. Remember to include your code in your report.

Hints

1. A good value for dt is around 0.1 s.
2. Initialize the Robot class. Does the plot appear? Can you access class properties such as Robot.x?
3. Run Robot.step() once with a constant probability density function. Does this look right?
4. Implement your loop, but don’t change the probability density function. Does your loop successfully terminate?
5. Implement the motion update and normalization, but not the measurement update. Does the plot look correct?
6. Create and plot your measurement model on a separate plot. Does it look correct?
7. Add the measurement update. Does the algorithm correctly estimate the robot location?