Occupancy Grid Mapping

Imagine you are a robot, and your goal is to move around a room and figure out specific areas in which there are obstacles obstructing your path. Unfortunately, your robot eyes are only so good, and your robot brain can only hold so much information. How do you solve this?

In other words, your goal is to generate a map with imperfect data, minimal computation, and low-resolution storage. First, you collect data using some sort of sensor, like radar or lidar, that (roughly) tells you where an object exists relative to you. Then, you compare these data with those you have already collected, apply fancy statistical formulae, and conclude roughly where you believe obstacles exist in your surroundings.

We do this by representing the world as a 2-D grid, with each point (cell) on the grid corresponding to a small square area of points in the real world. Then, if there's an obstacle, or part of an obstacle, in some area of the real world, we mark the entire corresponding cell with a "yes, this contains an obstacle". Since there are only two possibilities, either a cell contains an object or it does not, we can represent them respectively as a 1 or a 0.

We can visualize this using Lego:

The robot (left) maps the real world environment onto a 2-dimensional grid, represented using Lego (right) with yellow indicating an occupied cell and blue indicating a free cell.

Contents

Occupancy Grid Mapping

Definition

Key Results

Applications

Robot Decision-Making

Open Research Problems

References

Definition

Occupancy Grid Mapping (OGM) is used for probabilistic generation of an environment map. The technique was introduced in 1985 by H. Moravec and A. Elfes. Suppose that a robot must scan its surroundings to map out an area. Theoretically, this is easy given conditions like infinite time and perfect sensors. Realistically, however, we have finite time, computation, storage, and imperfect/noisy sensor data. OGM is the technique of projecting the environment to a two-dimensional grid of positions, where each grid cell holds a value representing whether the associated real-world area is occupied or free [1].

Generating this map, under real-world conditions, is difficult. However, under certain assumptions we can approximately solve the problem. There exist three key assumptions:

Agent pose is known
Adjacent grid cells are independent
Environment is static

It is a common assumption that the agent's position is known to the agent [2]. However, agent localization is a deeply related area to OGM and is a problem in and of itself. The second assumption, that grid cells are independent, is necessary to make OGM computationally tractable. It is noted that this assumption is bad, since often a single object will take up multiple grid cells worth of space [3]. Assuming independence thus removes inherent structure from generated maps, while making the problem computationally feasible. The third assumption feeds into the second, and we will see how in the next section. Assuming the environment is static, then an OGM algorithm can correctly assume multiple sensor recordings of the same location all correspond to the same real-world free-space or object. We can think of an OGM map internally as a still image.

Key Results

As it stands, OGM strives to obtain a 2D array of 0s and 1s representing free and occupied cells. For a map with m rows and n columns, with each cell having a possible value of 0 or 1, OGM seeks the correct mapping out of 2^(m*n) possibilities. This implies an exponential search through the entire map space -- computationally infeasible.

Even with this, there's no concise way to handle map data conflict. Suppose our agent collects a sensor reading, moves elsewhere, then comes back to the original location and takes another sensor reading. We have two cases -- either both readings are the same, or they are different. In both cases, we obtain more information about the cells involved, but there's no intuitive way to maintain this information in a single grid value (or to use all collected information to select the correct map from the entire map space).

The main key result for OGM is one of approximation -- we can approximate which map is correct by iteratively updating our belief space of the current environment as we take in new information. Instead of trying to remember all possible data we record, we accumulate evidence that each cell is free or occupied. We do this by assuming the environment is static, and each grid cell is independent.

To do this, we must derive an update rule for obtaining new evidence. Ideally, we would save all of our evidence and determine cell occupancy based on everything received, however this is computationally infeasible so we assume we only care about the current evidence and the previous accumulation we have thus far. Our derivation starts by defining an "odds" function, and translating our representation of a cell being free or occupied to the probability of a cell being occupied [2, 4, 6].

Given these, we apply Bayes' Law and logarithm rules to obtain our update rules. We care about updating the stored cell value based on some currently received evidence. A key insight here is to store the log-odds instead of storing the occupancy values. We choose to take the logarithm because it reduces floating-point errors compared to storing just the odds.

The inverse sensor model is the probability of receiving some evidence given the current cell is actually occupied. Inverse sensor models yield probability distributions over what the actual state is, as opposed to yielding the current state given some collected evidence. This is the only value we need in our update rule. Given the inverse sensor model probability, we can negate it (subtract the probability from 1) and divide into it by the same negation and take the log of the result -- this yields the term in our update rule.

This update rule translates our exponential search into a linear update -- much more computationally feasible. However, we trade off map structure -- OGM algorithms receive no information about how grid cells relate to each other, yet often in a real environment many cells will relate to each other (eg: an obstacle spanning multiple cells). As a result, it becomes a necessary condition to assume the environment is static.

This gives us a general OGM algorithm [3]:

instantiate m by n resolution grid of 0s, assume robot state is known (localized to the environment)
while not done mapping do
- take sensor measurement (inverse sensor model)
- update corresponding grid cells via update rule
- move to non-mapped areas

More positive grid cells are more likely to be occupied, while more negative grid cells are more likely to be free.

Applications

OGM has wide-reaching applications. Anything that requires environment mapping can implement OGM to some degree.

Robot Decision-Making

Both navigation and mapping are important topics in robotics. Path-planning, generating a valid sequences of movements from point A to point B, inherently requires an environment map to exist. One could use OGM to generate and/or represent such a mapping used for path-planning algorithms. OGM is useful in real applications due to the log-odds update rule -- data output from sensors are imperfect and noisy, but the log-odds update rule helps buffer the noise. OGM is also useful for grid-search methods (like A*) since it produces a grid-based map.

Others

SLAM -- Simultaneous Localization and Mapping -- require an agent determine where it is in the unknown world, while also mapping out the world. Some algorithms use grid mapping (and, as a result, OGM) to map out the environment, while others use topological mapping. New SLAM algorithm development is an active research area [5].

OGM is useful for indoor localization and mapping. Typically, agents use sonar, radar, or lidar sensors to receive distance measurements and propagate into grid cell data. Thus, GPS and other outdoor-based localization sensors are unnecessary for OGM [10].

Agent localization and mapping are of general interest in the computer vision community. Some work has been done feeding OGM maps into neural networks [7].

Variations

Reflection Maps

While occupancy grid mapping determines if a cell is occupied, one alternative approach is to record the regularity of a grid cell reflecting a (lidar/sonar) beam. This approach generates a reflection map rather than an occupancy map. Reflection maps are created by calculating the ratio between when a beam does not pass through a cell (occupied) versus when it does (free). This counting technique is useful when the terrain may having transparent or non-opaque obstacles like glass walls. Reflection mapping, however, is more prone to noise compared to an OGM map belief space [8].

Simplified OGM

In OGM, a grid cell may contain any value on the real number line. Unfortunately, floating-point numbers take up more space and power compared to simple integers. This is bad for low-power and low-resource agents. Simplified OGM solves this by instead giving each cell a value of 1 or 0 saying whether the cell is occupied or free. The upside to this approach is there is less computation and data storage needed, however accuracy (due to the lack of a belief space) is reduced [9].

Open Research Problems

OGM tells us where obstacles are (could be), but tells us nothing about the obstacles themselves. Suppose a robot can move over small rocks but cannot climb larger rocks nor small boulders. OGM tells us nothing about what is in the way, only that there exists something in the way [2].

While sensor measurement is typically imperfect and noisy, some sensors are susceptible to their own limitations. For example, when a lidar sensor is used in a glass terrain, the received data may be skewed by lasers reflecting in strange ways against the glass. One potential way forward is to use the counting method to create a reflection map, but even this is not perfect [8].

Additionally, all OGM problems rely on a single agent, but this problem can certainly be parallelized across multiple agents -- either each agent obtains an individual segment of the map, or each agent has a unique sensor and they work concurrently on each grid cell. While the general OGM technique may remain the same, potentially some awareness of other agents would need to be added. One would need to account for agent data conflict. However, this is potentially handled by OGM itself using the log-odds update rule.

References

Authors

Clifford Bakalian
Justin Goodman