An occupancy grid is a map that divides the environment into a regular grid of cells and stores, for each cell, the probability that it is occupied by an obstacle. In robot navigation, it is the standard way to represent free space, obstacles and unknown areas so that a robot can localize itself, plan paths and avoid collisions.
The idea treats mapping as a problem of probabilistic estimation. Each range measurement from a LiDAR, sonar or depth camera is uncertain, so instead of declaring a cell blocked after one reading, the robot accumulates evidence over many observations. The result is a map that tolerates sensor noise and changes gracefully as the world changes.
How an occupancy grid is built
Each new sensor reading updates the grid through an inverse sensor model, which states how a measurement changes belief about each cell. For a laser beam, the cells along the ray up to the hit point become more likely free, the cell at the hit point becomes more likely occupied, and cells beyond it stay unchanged because the sensor could not see them.
To keep the update fast and numerically stable, implementations store the log-odds of occupancy rather than the probability. A Bayesian update then becomes a simple addition per cell: a fixed increment for a hit and a fixed decrement for a miss. Values are clamped between an upper and a lower bound so that the map can still react when an obstacle moves.
The ray from the sensor to the hit point is traced with a line algorithm such as Bresenham’s in 2D or a voxel traversal in 3D. Cells are finally thresholded into three classes for planning and display, as summarized below.
| Cell state | Probability range | Common encoding | Meaning for navigation |
|---|---|---|---|
| Free | Below about 0.2 to 0.35 | 0 | Safe to traverse |
| Occupied | Above about 0.65 to 0.8 | 100 | Obstacle, never enter |
| Unknown | Prior near 0.5 | -1 | Not yet observed, treat with caution |
Key parameters and their trade-offs
The behavior of an occupancy grid depends on a small set of parameters. Resolution is the most consequential choice, because memory and computation grow with the square of map size in 2D and the cube in 3D.
| Parameter | Typical value | Effect of a larger value | Effect of a smaller value |
|---|---|---|---|
| Cell resolution | About 2 to 10 cm indoors | Less memory, coarser obstacles | Finer detail, more memory and CPU |
| Hit log-odds increment | About 0.6 to 0.9 | Obstacles appear faster | More robust to spurious hits |
| Miss log-odds decrement | About 0.3 to 0.5 | Moved obstacles clear faster | Map is more stable |
| Clamping bounds | Probability about 0.12 to 0.97 | Slower adaptation to change | Faster adaptation, more flicker |
| Maximum ray range | Several meters to tens of meters | More map coverage per scan | Less noise from far returns |
A common rule is to set the resolution at roughly a quarter to a half of the smallest gap the robot must pass through, so doorways and aisles remain clearly open in the map.
2D grids, 3D grids and costmaps
Most indoor wheeled robots use a 2D occupancy grid built from a planar LiDAR, stored as an image with a resolution and origin. Robots that move in 3D or must detect overhanging obstacles use a 3D occupancy representation, usually an octree such as OctoMap, which stores large free or unknown regions in a compact way.
An occupancy grid is often confused with a costmap, but the two serve different purposes. The occupancy grid represents what the world looks like; the costmap represents how expensive it is for this robot to be in each cell, combining the occupancy grid with robot footprint, inflation zones and other layers.
| Map type | Stores | Main use | Typical limitation |
|---|---|---|---|
| 2D occupancy grid | Occupancy probability per cell | Localization and global planning | Misses obstacles above or below the scan plane |
| 3D octree map | Occupancy per voxel, multi-resolution | Drones, manipulators, rough terrain | Higher compute and memory |
| Costmap | Traversal cost per cell | Path planning and obstacle avoidance | Robot-specific, not a world model |
| Elevation map | Height per cell | Legged and off-road robots | Cannot model overhangs |
| Feature map | Landmark positions | Lightweight localization | No explicit free space |
Using the grid for localization and planning
In localization, a particle filter such as AMCL compares each new laser scan with the stored occupancy grid. A precomputed likelihood field, which gives the distance from every cell to the nearest obstacle, makes this comparison fast. In SLAM, the grid is built and the pose is estimated at the same time, and loop closures correct the accumulated map.
For path planning, graph search algorithms such as A* or Dijkstra treat free cells as nodes and adjacent cells as edges. Because a raw grid ignores robot size, planners almost always work on an inflated costmap rather than directly on occupancy values.
Limitations and frequent errors
Occupancy grids rest on simplifying assumptions, chiefly that cells are independent and that the world is static. Ignoring these assumptions causes recognizable problems.
| Symptom | Likely cause | Remedy |
|---|---|---|
| Ghost obstacles remain | Miss updates too weak or clamping too tight | Raise miss decrement, adjust bounds |
| Glass walls appear free | Laser passes through transparent surfaces | Add sonar or mark walls manually |
| Blurred or doubled walls | Pose drift during mapping | Improve odometry, enable loop closure |
| Narrow doors appear closed | Resolution too coarse | Use finer cells near passages |
| Tables invisible to robot | 2D scan plane below the tabletop | Add a depth camera and 3D layer |
In simple terms
Think of a sheet of graph paper laid over a floor plan. A robot shades each square according to how sure it is that something solid is there: light for empty floor, dark for walls, gray for places it has not seen yet.
Every time the robot looks around, it makes the shading a little more confident. A single odd reading does not ruin the map, because each square reflects many looks over time. The robot then uses this shaded paper to find out where it is and to pick a safe route.
A practical example
A hospital delivery robot must carry medication between wards on three floors. During commissioning, a technician drives it through each floor while it runs SLAM with a 5 cm occupancy grid built from a 2D LiDAR. Loop closures at corridor junctions keep the walls straight across about 400 m of hallway.
In daily operation, the robot localizes against the saved grid and plans on an inflated costmap. Because the scan plane passes below hospital beds and carts with high frames, the team adds a depth camera layer that marks those obstacles in the costmap. The result is reliable navigation through busy corridors without collisions with overhanging equipment.