Occupancy Grid Mapping
Transform chaotic sensor data into a structured, navigable world. Occupancy Grid Mapping is the foundational probabilistic framework that allows autonomous mobile robots to perceive their environment, distinguishing free space from obstacles with mathematical precision.
Core Concepts
Discretized Space
The environment is divided into a grid of fixed-size cells. Each cell represents a specific square area in the physical world, simplifying complex geometry into a manageable matrix.
Probabilistic Values
Cells are not just black or white. They store a probability value (0 to 1) representing the likelihood of being occupied, allowing the robot to account for sensor noise.
Binary Bayes Filter
The map state is updated recursively using Bayes' rule. As new sensor readings arrive, the belief state of each cell shifts, reinforcing the certainty of obstacles or free space.
Log-Odds Notation
To avoid numerical instability with floating-point probabilities, algorithms often use log-odds. This transforms multiplication into simple addition, speeding up real-time processing.
Inverse Sensor Model
This model interprets raw range data (like LiDAR hits). It determines which cells along a beam are 'free' and which specific cell contains the 'obstacle'.
Global vs. Local Maps
OGM is scalable. Robots often maintain a static global map for path planning and a smaller, rolling local map for immediate collision avoidance.
How It Works
At the heart of an autonomous robot's navigation stack is the translation of ray-cast data into spatial knowledge. When a LiDAR sensor strikes an object, it returns a distance measurement.
The Occupancy Grid Mapping algorithm traces a line from the robot's center to that hit point. Every grid cell along that line is updated with a lower probability of occupancy (making it "free space"), while the cell at the very end of the line receives an increased probability (marking an "obstacle").
Over thousands of scans per second, these probabilities converge. Transient noise filters out, while static walls and shelving units solidify into high-probability barriers, creating a robust map that is safe for navigation planning.
Real-World Applications
Warehouse Automation
AGVs use dynamic occupancy grids to navigate changing layouts where pallets are constantly moved, ensuring forklifts and robots don't collide in high-traffic aisles.
Service Robots
Hospital delivery bots rely on high-resolution grid maps to navigate narrow corridors and patient rooms, distinguishing between permanent walls and moving gurneys.
Autonomous Driving
While often using vector maps for lanes, self-driving cars utilize local occupancy grids for immediate drivable surface detection and obstacle tracking in complex urban environments.
Search and Rescue
In unstructured disaster zones where no prior map exists, robots build occupancy grids in real-time (SLAM) to identify safe paths through debris and rubble.
Frequently Asked Questions
What is the difference between an Occupancy Grid and a Feature Map?
An Occupancy Grid discretizes the world into a matrix of cells where each cell holds a binary or probabilistic value of being occupied. A Feature Map (or Vector Map) stores the environment as geometric landmarks (lines, corners, points). Grid maps are generally better for path planning and navigation in unstructured environments, while feature maps are more memory-efficient.
How does grid resolution affect robot performance?
Grid resolution is a trade-off between precision and computational load. A smaller cell size (e.g., 1cm) offers high precision for tight maneuvers but requires significantly more memory and processing power. A larger cell size (e.g., 10cm) is faster to compute but may cause the robot to perceive narrow passages as blocked.
How are moving objects handled in Occupancy Grid Mapping?
Standard OGM assumes a static environment. However, dynamic objects can be handled by updating probabilities quickly or using specific "dynamic map" layers. If an object moves, the sensor rays will eventually pass through the space it previously occupied, lowering that cell's occupancy probability back to free space.
What sensors are best for generating these maps?
2D LiDAR is the industry standard due to its high accuracy and direct range measurements. Depth cameras (RGB-D) and ultrasonic sensors can also be used, though sonar typically has a wider cone that requires more complex inverse sensor models to map accurately onto a grid.
What is the "Unknown" state?
Ideally, a grid map has three states: Free, Occupied, and Unknown. Typically initialized with a probability of 0.5 (unknown), cells only change state when sensors observe them. This distinction is crucial for exploration algorithms to direct the robot toward unmapped areas.
Why use Log-Odds instead of standard probability?
Updating probabilities using Bayes' rule involves multiplication, which can be computationally expensive and prone to floating-point underflow errors close to 0 or 1. Log-odds notation converts these probabilities into a logarithmic scale, allowing updates to be performed via simple addition and subtraction.
Can Occupancy Grids work in 3D?
Yes, 3D occupancy grids use "voxels" (volumetric pixels) instead of 2D cells. However, full 3D grids consume immense memory. An efficient alternative is an Octree structure (like OctoMap), which hierarchically groups empty space to save memory while preserving detail where obstacles exist.
How does SLAM relate to Occupancy Grid Mapping?
SLAM (Simultaneous Localization and Mapping) is the broader process. The Occupancy Grid is the map representation output by the SLAM algorithm (like Gmapping or Cartographer). The robot uses the grid to figure out where it is (Localization) while simultaneously updating the grid (Mapping).
What is "Ray Casting" in this context?
Ray casting is the technique used to update the map. For every sensor reading, a virtual ray is traced from the robot to the obstacle. Algorithms like Bresenham's line algorithm identify every grid cell touched by this ray to update their probabilities as "free," except for the final cell which is "occupied."
How much memory does a typical map require?
It depends on size and resolution. A 100x100 meter warehouse mapped at 5cm resolution results in a 4 million cell grid. If using 8-bit integers per cell (0-255 values), that's roughly 4MB of RAM—very manageable for modern embedded systems, though it scales quadratically with area size.
What happens if the map becomes misaligned (Drift)?
If odometry errors accumulate, the robot may "paint" obstacles in the wrong place, creating double walls. This requires Loop Closure algorithms within the SLAM framework to detect when the robot has returned to a known location and mathematically warp the grid to correct the alignment.