All language subtitles for 01_3-2-1-occupancy-grid-map.en

In this lecture,
we will start talking about a specific

mapping algorithm called
Occupancy Grid Mapping.

I'm going to explain visually
what we want to achieve and

introduce some important terms and
measurement models for this week.

Let us begin with a video
from a robot competition.

A real mobile robot is
running on the ground.

The data you're going to deal with in this
week were collected from the same robot.

Except that the robot
ran inside the building.

The robot has many on-board sensors.

But we are most interested in
the range sensor it has on the top.

Let me explain how
the sensor works briefly.

The sensor emits laser rays in
some pre-defined directions.

And receives their reflections to
give us the traveled distance.

Rays travel longer distances, if objects
are far away in their directions.

Other rays travel short distances
when reflected from objects nearby.

As the robot collects this information
over time, while moving around.

We can build a map of
the objects that block the rays.

This is a result of indoor mapping.

Using the range sensor in
the way that I just explained.

Anything hit by the laser
rays appears bright.

In contrast, places where the rays pass
unobstructed appear dark in the figure.

You can see the rough layout of the area.

Let's start talking about how we can build
occupancy grid maps from laser readings.

Let me define some terms
we're going to use often.

The term Occupancy is defined
as a binary random variable.

Remember that, a random variable is a
function from a sample space to the reals.

This case Occupancy is
defined in the probability space

that has two possible states.

Free and occupied.

The occupancy random variable,
then, has two values, 0 and 1.

An Occupancy grid map is just
an array of occupancy variables.

Each element of the grid
can be represented

with a corresponding occupancy variable.

This figure shows a 2D example
of Occupancy grid map.

Occupancy grid mapping requires,

a Bayesian filtering algorithm to
maintain a Occupancy grid map.

Bayesian filtering implies
a recursive update to the map.

A robot can never be
certain about the world so

we use the probabilistic notion of
occupancy instead of the occupancy itself.

Now let me talk about
the sensor measurements.

Occupancy grid mapping algorithms
usually incorporate a range sensor.

This sensor provides distance information.

However in our map cell's point of view
there are two possible measurements.

A cell could be passed through by the ray.

Which means it is free empty space.

The light blue cells in the figure
are an example of free cells.

Also it is possible that
a cell is hit by the ray.

Which means a cell is
occupied by something.

The yellow cell where the ray starts at,
is an example of occupied cells.

We will use 0, for the Free measurements.

1, where the Occupied measurement for
each cell.

Now, we're going to think about
a probabilistic model of the measurements.

Given the occupancy state of each cell.

There are only four possible conditional
probabilities of measurements,

that we can enumerate.

Because the variables z and
m are all binary,

probability that z is 1 given m is 1 Is

the probability that we have occupied
measurements for an occupied cell.

Probability that z is 0 given m is 1

is the probability that we have free
measurement for an occupied cell.

We can define a probabilities of
observation given m is 0, in the same way.

These are the measurement
parameters we need to set.

False measurement stem from sensor noise,

the discretized space representation,

moving objects, and
uncertain knowledge of the robot motion.

So we have four parameters.

However, if you remember what
the conditional probability is.

You may notice that we actually have two
parameters for our measurement model.

Now, we have basic understanding of

elements of the Occupancy Grid Mapping Algorithm.

We have defined the Occupancy variable
that represents the state of grid cells.

And the measurement model parameters
that will be used to update the map.

If we had some prior
information of the cell, and

we may take that into consideration,
according to Bayes' rule.

We'll talk about how to obtain
a posterior occupancy grid map.

Following the Bayes'
rule in the next lecture.