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.
