Mapping
Mapping refers to the ability of a robot to construct a representation or model of its environment. This is crucial for various robotic tasks, including localization, planning, and navigation. In this document, we'll dive deep into Occupancy Grid Mapping (OGM).
 |
|---|
| Overview of mapping in robotics. |
Occupancy Grid Mapping (OGM)
OGM is a mapping method where the environment is represented as a discrete grid. Each cell in this grid represents a patch of space in the real world, and can either be occupied, free, or unknown.
 |
|---|
| An example occupancy grid. The black boxes indicate occupied regions, the white boxes indicate unoccupied (free) regions, and the gray boxes indicate unexplored regions. |
Naive OGM
In a naive OGM, measurements from sensors (e.g., LiDAR or ultrasonic sensors) are used directly to update the grid. If a sensor measurement indicates that there's an obstacle at a specific location, the corresponding cell in the grid is marked as occupied. Conversely, if there's no obstacle, it's marked as free.
The major drawback of this approach is its binary nature. In other words, there's no room for uncertainty, which can lead to inaccuracies in the map, especially in dynamic environments or with noisy sensors.
 |
|---|
| Our implementation of OGM involves using a 2D lidar. The lidar scans show the distance of different points around the robot. |
How does this work in detail?
Imagine we have a robot that has never been turned on before and we initialize it to be able to start tasks. It does not know anything about its surroundings. If we assume a grid representation of the environment, it would look something like this:
 |
|---|
However, we know that the actual environment has some obstacles and looks like this:
 |
|---|
To understand its surroundings, we incorporate a naive OGM approach. Let's say the robot is initialized like the following:
 |
|---|
We plan to use a LiDAR sensor to determine whether obstacles exist and whether the space discretized into grids is safe or not. For simplicity, Imagine that we have a really bad LiDAR that only emits two rays.
The initial ray cast would be emitted.
 |
|---|
Our sensors will detect that both emitted rays have hit an object. Given the length and angle of emission of these rays, we can determine which grid points are occupied. Afterwards, we know that all the other grid points this ray has traversed through are free, since if it was not, the ray would have detected a hit there and would not have gone through.
 |
|---|
How do we find the free grids in between?
This is where the Bresenham Algorithm comes into play. The Bresenham algorithm is a line-drawing algorithm that determines the points that should be selected to form a close approximation to a straight line between two points. The idea is to identify which grid points that belong on this like to classify as free. The algorithm is relatively simple:
Given: Start Point: (\((x_1, y_1)\)\)
Endpoint: (\((x_2, y_2)\)\)
Horizontal Difference: (\(\Delta x = |x_2 - x_1|\)\)
Vertical Difference: (\(\Delta y = |y_2 - y_1|\)\)
We choose to find the grids that the line \(\(y = mx + b\)\) exists in.
The method's core revolves around finding the dominant axis. That is, if \(\(\Delta x > \Delta y\)\), the algorithm moves along the x grid, and if \(\(\Delta y > \Delta x\)\), it moves along the y grid.
To quantify this, the algorithm uses a decision variable \(\(D\)\), where \(\(D\)\) is defined as:
The algorithm iterates until \(\(D = 0\)\). If \(\(D \neq 0\)\), the following updates are made:
and
Once that is complete, we can update our robot map to represent those occupied and unoccupied grids.
 |
|---|
Now imagine if the robot moved to another spot and used it's LiDAR again:
 |
|---|
Keep in mind, that if a robot does not move and its sensor does not change its behavior, the map will always remain static.
In this case, now, we can see that the left ray has collided with an object and the right ray has gone towards the edge of our environment. This can be another obstacle or a max length for the ray of the LiDAR. Once again, we identify a plan to identify the free spaces between these two rays and their endpoints
 |
|---|
Using the Bresenham algorithm, we can classify the points and update our map:
 |
|---|
We can continue iterating throughout the map and time to keep improving on the mapped representation of the environment until all the grids are determined either occupied or not.
Probabilistic OGM
To counter the issues with the naive OGM, the Probabilistic OGM was introduced. Instead of binary values, probabilistic OGMs use probabilities to represent the likelihood that a cell is occupied.
If \(P_{occ}\) is the probability that a cell is occupied, then:
where:
-
\(P(z_t | \text{occ})\) is the probability of the sensor measurement \(z_t\) given that the cell is occupied.
-
\(P_{prev}\) is the probability that the cell was occupied in the previous time step (prior).
-
\(P(z_t)\) is the probability of the sensor measurement \(z_t\) at time \(t\).
This Bayesian update ensures that uncertainties in sensor measurements and temporary changes in the environment are handled more gracefully.
Demo
To try out the OGM algorithm, run this Google Colab notebook:
