5.5 Occupancy grid mapping

Occupancy grid mapping is a crucial technique in robotics for creating probabilistic representations of environments. It divides space into fixed-size cells, assigning each a probability of being occupied or free based on sensor data. This method enables robots to navigate, plan paths, and avoid obstacles effectively.

The process involves using sensors like laser range finders, sonar, and stereo vision to gather environmental data. The binary Bayes filter and log odds representation are used to update cell probabilities, integrating new measurements and handling conflicting information. This approach supports various applications, including localization, path planning, and exploration.

Occupancy grid mapping overview

• Occupancy grid mapping is a technique used in robotics to create a probabilistic representation of the environment based on sensor data
• It involves discretizing the environment into a grid of fixed-size cells and estimating the probability of each cell being occupied or free
• Occupancy grid maps are commonly used in autonomous robots for tasks such as navigation, path planning, and obstacle avoidance

Grid representation of environment

Fixed-size cells in grid

Top images from around the web for Fixed-size cells in grid

• 

  Frontiers | Robot DE NIRO: A Human-Centered, Autonomous, Mobile Research Platform for ... View original

  Is this image relevant?

• 

  Frontiers | Robot DE NIRO: A Human-Centered, Autonomous, Mobile Research Platform for ... View original

  Is this image relevant?

1 of 1

Top images from around the web for Fixed-size cells in grid

• 

  Frontiers | Robot DE NIRO: A Human-Centered, Autonomous, Mobile Research Platform for ... View original

  Is this image relevant?

• 

  Frontiers | Robot DE NIRO: A Human-Centered, Autonomous, Mobile Research Platform for ... View original

  Is this image relevant?

1 of 1

• The environment is divided into a grid of fixed-size cells, typically square or rectangular
• Each cell represents a small portion of the environment and is associated with a probability value indicating its occupancy state
• The size of the cells determines the resolution of the occupancy grid map
  • Smaller cells provide higher resolution but increase computational complexity and memory requirements
  • Larger cells result in lower resolution but are more computationally efficient

Cell occupancy probability values

• Each cell in the grid is assigned a probability value representing the likelihood of it being occupied or free
• Probability values range from 0 to 1, where:
  • 0 indicates a free cell with high confidence
  • 1 indicates an occupied cell with high confidence
  • 0.5 represents an unknown or unexplored cell
• The occupancy probability values are updated based on sensor measurements and the robot's belief about the environment

Sensor data for mapping

Laser range finders

• Laser range finders (LRFs) are commonly used sensors for occupancy grid mapping
• LRFs emit laser beams and measure the time of flight to determine the distance to obstacles
• They provide accurate and high-resolution range measurements, enabling precise mapping of the environment
• LRFs are particularly effective in indoor environments with smooth surfaces

Sonar sensors

• Sonar sensors use sound waves to measure distances to objects
• They emit ultrasonic pulses and measure the time it takes for the echoes to return
• Sonar sensors are less accurate compared to LRFs but are useful in environments with transparent or reflective surfaces
• They have a wider field of view but lower angular resolution compared to LRFs

Stereo vision

• Stereo vision systems use two cameras to capture images from slightly different viewpoints
• By analyzing the disparity between the two images, depth information can be extracted
• Stereo vision provides dense 3D information about the environment
• It is effective in outdoor environments and can handle textureless surfaces
• However, stereo vision is computationally intensive and sensitive to lighting conditions and calibration errors

Bayesian occupancy grid mapping

Binary Bayes filter

• The binary Bayes filter is a probabilistic framework used for occupancy grid mapping
• It maintains a belief distribution over the occupancy state of each cell in the grid
• The filter updates the occupancy probabilities based on sensor measurements and the robot's motion
• It incorporates the sensor model and the motion model to estimate the posterior probability of occupancy

Log odds representation

• The log odds representation is an alternative way to represent occupancy probabilities
• Instead of storing the probabilities directly, the log odds of occupancy are used
• Log odds values range from negative infinity to positive infinity, with 0 representing an unknown state
• The log odds representation simplifies the update equations and avoids numerical instabilities
• It allows for efficient computation and storage of occupancy probabilities

Inverse sensor model

• The inverse sensor model describes the probability of a cell being occupied given a sensor measurement
• It maps sensor readings to occupancy probabilities, taking into account the characteristics of the sensor
• The inverse sensor model depends on the type of sensor used (e.g., LRF, sonar) and its noise characteristics
• It considers factors such as the sensor's field of view, maximum range, and measurement uncertainty
• The inverse sensor model is used to update the occupancy probabilities of cells based on new sensor measurements

Map updates from sensor data

Integrating new measurements

• As the robot moves and acquires new sensor measurements, the occupancy grid map is updated
• Each new measurement provides information about the occupancy state of cells within the sensor's field of view
• The inverse sensor model is applied to convert the sensor readings into occupancy probabilities
• The updated probabilities are combined with the existing occupancy probabilities using Bayesian inference

Updating occupancy probabilities

• The occupancy probabilities of cells are updated using the binary Bayes filter or log odds representation
• The update process involves multiplying the prior occupancy probability by the likelihood of the new measurement
• The resulting posterior probability represents the updated belief about the occupancy state of each cell
• The update equation ensures that the occupancy probabilities remain consistent with the sensor measurements over time

Handling conflicting information

• In some cases, sensor measurements may provide conflicting information about the occupancy state of a cell
• Conflicting measurements can arise due to sensor noise, dynamic objects, or changes in the environment
• The occupancy grid mapping algorithm needs to handle conflicting information and maintain a consistent map
• Techniques such as weighted averaging, evidence accumulation, or robust estimation can be used to resolve conflicts
• The algorithm may also incorporate temporal information to distinguish between static and dynamic objects in the environment

Localization with occupancy grids

Monte Carlo localization

• Monte Carlo localization (MCL) is a probabilistic localization approach that uses occupancy grid maps
• It represents the robot's belief about its pose (position and orientation) using a set of weighted particles
• Each particle represents a possible pose of the robot and is associated with a weight indicating its likelihood
• MCL updates the particle weights based on the similarity between the observed sensor measurements and the expected measurements given the particle's pose and the occupancy grid map

Particle filter approach

• The particle filter is the core component of Monte Carlo localization
• It maintains a set of particles that approximate the posterior distribution of the robot's pose
• The particle filter involves three main steps: prediction, update, and resampling
  • Prediction: The particles are propagated forward based on the robot's motion model, accounting for motion uncertainty
  • Update: The particle weights are updated based on the likelihood of the observed sensor measurements given each particle's pose and the occupancy grid map
  • Resampling: Particles with low weights are replaced by new particles sampled from the high-weight particles, concentrating the belief around the most likely poses
• The particle filter iteratively refines the pose estimate as new sensor measurements are received, allowing the robot to localize itself within the occupancy grid map

Applications of occupancy grids

Path planning and navigation

• Occupancy grid maps are widely used for path planning and navigation in autonomous robots
• The map provides a representation of the environment's obstacles and free space
• Path planning algorithms, such as A* or RRT, can use the occupancy grid to find optimal or feasible paths from the robot's current position to a target location
• The planned path takes into account the occupancy probabilities of cells, avoiding obstacles and preferring free space

Obstacle avoidance

• Occupancy grid maps enable robots to detect and avoid obstacles in real-time
• By analyzing the occupancy probabilities of cells in the robot's vicinity, it can identify potential collisions
• Obstacle avoidance algorithms, such as potential fields or velocity obstacles, use the occupancy information to generate safe and collision-free motion commands
• The robot can dynamically adjust its trajectory based on the updated occupancy grid map to navigate through cluttered environments

Environment exploration

• Occupancy grid mapping is valuable for environment exploration and mapping of unknown areas
• The robot can incrementally build and refine the occupancy grid map as it explores the environment
• Exploration strategies, such as frontier-based exploration or information-theoretic approaches, can guide the robot to efficiently cover and map the unknown regions
• The occupancy grid map provides a compact and probabilistic representation of the explored environment, facilitating tasks such as coverage planning and map merging

Challenges and limitations

Computational complexity

• Occupancy grid mapping can be computationally intensive, especially for large environments and high-resolution grids
• Updating the occupancy probabilities for each cell based on sensor measurements requires significant computational resources
• The computational complexity grows with the size of the environment and the number of cells in the grid
• Efficient data structures and algorithms, such as quadtrees or octrees, can be used to optimize the storage and processing of occupancy grids

Memory requirements

• Storing the occupancy probabilities for each cell in the grid can consume a significant amount of memory
• The memory requirements increase with the size of the environment and the resolution of the grid
• Techniques such as sparse representations or adaptive resolution can help reduce the memory footprint
• Memory-efficient data structures, such as compressed occupancy grids or hierarchical representations, can be employed to handle large-scale environments

Dynamic environments

• Occupancy grid mapping assumes a static environment, where the occupancy state of cells remains constant over time
• In dynamic environments with moving objects or changing obstacles, the occupancy grid map may become outdated quickly
• Handling dynamic objects requires additional techniques, such as tracking moving objects or incorporating temporal information into the mapping process
• Adaptive occupancy grid mapping approaches can update the map in real-time based on new sensor measurements, but they may still struggle with highly dynamic scenes

Sensor noise and uncertainty

• Sensor measurements are subject to noise and uncertainty, which can affect the accuracy of the occupancy grid map
• Noisy or erroneous sensor readings can lead to incorrect occupancy probabilities and inconsistencies in the map
• Sensor models need to account for the characteristics and limitations of the specific sensors used
• Robust estimation techniques, such as Bayesian filtering or outlier rejection, can help mitigate the impact of sensor noise and uncertainty
• Fusing information from multiple sensors with complementary characteristics can improve the overall mapping accuracy and robustness

Extensions and variations

3D occupancy grids

• Traditional occupancy grid mapping focuses on 2D representations of the environment
• However, many real-world environments are three-dimensional, requiring 3D occupancy grids for accurate mapping
• 3D occupancy grids extend the concept of 2D grids by adding an additional dimension to represent height or elevation
• They allow for the representation of complex 3D structures, such as multi-level buildings or uneven terrain
• 3D occupancy grids introduce additional computational and memory challenges due to the increased dimensionality

Multi-resolution grids

• Multi-resolution occupancy grids use variable cell sizes to adapt the map resolution based on the environment's complexity
• They allow for high-resolution mapping in areas with dense obstacles or important features while using lower resolution in open or less relevant regions
• Multi-resolution grids can significantly reduce the computational and memory requirements compared to fixed-resolution grids
• They enable efficient mapping and navigation in large-scale environments with varying levels of detail
• Techniques such as octrees or multi-level grids are commonly used to implement multi-resolution occupancy grids

Hybrid metric-topological maps

• Hybrid metric-topological maps combine the strengths of occupancy grid mapping with topological map representations
• Occupancy grids provide a detailed metric representation of the environment, capturing the spatial layout and obstacle information
• Topological maps represent the environment as a graph of interconnected nodes and edges, capturing the connectivity and high-level structure
• Hybrid maps integrate both representations, allowing for efficient planning and navigation at different levels of abstraction
• The metric occupancy grid is used for local planning and obstacle avoidance, while the topological map enables global reasoning and high-level decision making
• Hybrid maps offer a balance between the detailed spatial information of occupancy grids and the compact and scalable representation of topological maps