Original subtitles

In this lecture I will continue talking about occupancy grid mapping.

We will define more mathematical notations to discuss the mapping algorithm.

Remember, we want to update the occupancy probability of each cell

from our measurements in a Bayesian framework.

However, keeping track of probabilities directly can be hard.

Instead of using occupancy probability itself,

let me introduce a new concept that will make our computation really simple.

If there is a probability of something happening,

written as p(X) and the odds can be considered as a ratio.

This ratio is the probability of the thing happening

over the probability of the thing not happening.

We are going to use the odds of a cell occupied, which can be expressed

as shown on the slide using the posterior probability notation.

Applying Bayes' rule, we can rewrite the odds to include the sensor model term,

the prior term, or both, the numerator and the denominator.

Then the evidence term p(z) naturally goes away.

Things get simpler when we take the logarithm of the odds.

Let's take the log of both sides of the equation.

Note that the left-hand side includes the posterior odds and

the right-hand side includes the sensor model and the prior.

Because of the characteristics of log functions,

the two terms multiplied on the right-hand side gets separated into an addition.

This is a formula for the log-odds update of occupancy grid mapping.

The map stores the log-odds values of each cell and

the measurement model is represented as a log-odds as well.

The computation for map updates then becomes additions of those log odds.

There are two things you need to remember when you apply this update rule.

First, the update is done only for observed cells.

Second, the updated values become priors

when you receive new measurements in the future time steps.

The update rule becomes recursive.

Let me show how the update works in detail.

We will first have a closer look at the measurement model and

think about the two cases of measurements.

As we defined in the previous lecture,

a cell will be observed as either occupied or free.

Of course, there are many cells we don't even observe.

We will simply not update anything for these cells.

For the occupied measurements, we can write the log-odds occupied as shown.

For the free measurements, we can write the log-odd free like this.

Note that the conditioning value of m is reversed for

the free case to indicate that m is 0 matches with z = 0.

Keeping the update rule in mind,

let's look at a simple example of occupancy grid mapping.

We have these values for the measurement model parameters.

In a small occupancy grid map initialized with zero log-odds values.

This initialization is equivalent to having the same probability

of the cells being occupied and being free.

Now we receive a new measurement from our range sensor,

which emits a single ray in this example.

As you have seen, the yellow cell is measured as being occupied and

the light blue cells are measured as being free empty space.

For the cells that are observed to be occupied, we update the log-odd

by adding the log-odd occupied measurement parameter, 0.9 in this case.

For the cells that are observed to be free, we update the log-odd by

subtracting the log-odd free measurement parameter, 0.7.

After all the updates, we move on to get ready to take more measurements.

When we receive a new measurement,

we update the observed cells in the same way as the previous moment.

You can see that as the cells are observed multiple times being free,

they start to get darker.

This means that our belief of those cells being occupied gets lower.

You just have seen a simple example of occupancy grid mapping.

In practice and for your assignments, a range sensor will have more than one ray.

Additionally, you will need to find out what cells are observed based

on your pose estimate of the robots and distance measurements.

We are going to talk about that in the next lecture.