Welcome everyone to the second module of this course. In this module, we will discuss the creation of two environmental maps; the occupancy grid map and the high-definition road map. Both of the maps we will discuss play a critical role in the task of motion planning, as we will see throughout this course. We will start by defining the occupancy grid map in detail, and understand how it can be created on an autonomous vehicle. We will then try to understand the noise inherent in measurement data used for the creation of an occupancy grid map. Finally, you will see how to handle this noise in the measurement data, by learning about Bayesian updates of occupancy grid beliefs. Let's get started. An occupancy grid is a discretized grid which surrounds the current ego vehicle position. This discretization can be done in two or three dimensions. The methods we discussed can be applied to both two and three-dimensional problems. However, to simplify both the explanations as well as the computational requirements in this module, we will only be focusing on the 2D version. Each grid square of the occupancy grid indicates if a static or stationary object is present in that grid location. If so, that grid location is classified as occupied. An example of static objects that would be classified as occupying a grid cell can include trees, buildings, road signs, and light poles. In the domain of autonomous vehicles, other objects which you might not think of as obstacles, should also be classified as occupying space, including all non drivable surfaces such as lawns or sidewalks. Each square of the occupancy grid noted by Mi, maps to a binary value in which one indicates that the square is occupied by a static object, and zero indicates that it is not. In this map, we can see that the squares with trees and grass cover are labeled as one, whereas the road is labeled zero. The resulting map looks like this. All the occupied squares of the grid are purple, and the rest of the map corresponding to the drivable surfaces is left transparent. We will now look at the set of assumptions that are made in order to create an accurate occupancy grid. First, the environment that is currently measured to create this occupancy grid only corresponds with static objects. Meaning, all dynamic objects or moving objects must be removed from the sensor data before it is used for occupancy grid mapping. Second, each grid cell is independent of all others. This assumption is made to simplify the update functions needed to create the occupancy grid. Finally, the current vehicle state is exactly known in relation to the occupancy map at every time step. In the domain of self-driving cars to observe distance between the car and the current state of the world, the LIDAR sensor is used most frequently. As a quick reminder, the LIDAR sensor uses pulses of light to measure the distance to all objects surrounding the car, and returns a point cloud of measurements throughout its field of view. In this video, we can see the output of the LIDAR sensor. Several components of the LIDAR data need to be filtered out before this data can be used to construct an occupancy grid. The first step is to filter all LIDAR points which comprise the ground plane. In this case, the ground plane is the road surface which the autonomous car can safely drive on. Next, all points which appear above the highest point of the vehicle are also filtered out. This set of LIDAR points can be ignored as they will not impede the progression of the autonomous vehicle. Finally, all non-static objects which had been captured by the LIDAR need to be removed. This includes all vehicles, pedestrians, bicycles, and animals. Once all filtering of the LIDAR data is complete, the 3D LIDAR data will need to be projected down to a 2D plane to be used to construct our occupancy grid. The filtering and compression of the LIDAR data to create accurate occupancy grids for autonomous cars, will be covered in a later video in this module. The LIDAR data which is now filtered and compressed, resembles data from a high definition 2D range sensor, which accurately measures distance to all static objects around the vehicle in the plane. However, there is still a problem. After all the filtering has been completed, there are still major map uncertainties due to the filtering methods used on the data, the complexity of the data at hand, and most of all, environmental and sensor noise. In order to handle this noise, the occupancy grid will be modified to be probabilistic. Instead of cell i storing a binary value for occupied, now each cell i will store a probability between zero and one, corresponding to the certainty that the given square is occupied. The higher the value stored, the higher the probability that the given square is occupied. To use this set of probabilities, the occupancy grid can now be represented as a belief map denoted by the term B-E-L are bel. To keep notations simple, Mi represents a single square of the occupancy grid, where i can be constructed from measurements Y, and the vehicle location X. The belief over Mi is equal to the probability that the current cell Mi is occupied given the sensor measurements gathered for that cell location. To convert back to a binary map, a threshold value can be established at which a given belief is confident enough to be classified as occupied. Any value below the set threshold will be set to free. As an example, the occupied square in the figure to the left has a probability of 0.94, which classifies the square is occupied. On the other hand, the square found on the street only has a probability of 0.12 of being occupied, and thus will be classified as a free location. Multiple sets of measurements can be combined from time one to time t to achieve far more accurate belief of occupancy. In fact, we can update beliefs in a recursive manner so that at each time step t, we use all prior information from time one onwards to define our belief. The belief at time t over the map cell Mi is defined as the probability that Mi is occupied given all measurements and the vehicle position from time one to t. To combine multiple measurements into a single belief map, Bayes theorem can be applied. In the case of the occupancy grid, we get a Bayesian update step that takes the following form. The distribution p of y_t given Mi, is the probability of getting a particular measurement given a cell Mi is occupied. This is known as the measurement model, which you studied in detail in course two. The belief at time T minus one over Mi corresponds to the prior belief stored in our occupancy grid from the previous time step. We rely on the Markov assumption, that all necessary information for estimating cell occupancy is captured in the belief map at each time step. So no earlier history needs to be considered in the cell update equations. Finally, eta in this case corresponds to a normalizing constant applied to the belief map. This is needed to scale the results to make sure it remains a probability distribution. Lets see an occupancy grid in action. In this video, we will follow the autonomous vehicle as it drives out of the driveway and down a road, while the occupancy grid is updating in real time. The lighter grid cells represent free squares, whereas the black grid cells represent occupied squares. We can also see the raw LIDAR data in red, and the filtered outputs in orange. Notice how the map tracks the vehicle motion which is estimated using the same techniques as we've presented in course two. In this video, the threshold of belief needed for an object to be classified as obstructing is set to very high, thus only large static objects are getting identified as occupied. Lowering this threshold value will result in more cells to be tagged as occupied, but will lead to noisier maps as well. All right. So let's summarize what you've just learned. In this video, you learned the basic definition of the Occupancy grid map, and saw how the LIDAR sensor data can be filtered and compressed to create an occupancy grid. You then learned how to represent the occupancy grid as a belief map, and applied Bayesian updates to incorporate new measurements in the occupancy grid. In the next video, we will discuss some of the numerical problems with our belief space map representation, and introduce the logit function as a solution to this problem. We will also look at an inverse measurement model which is needed to create the occupancy map grid from 2D LIDAR data using the logit function. See you there.
