1 Definition and Concept
An occupancy grid is a spatial representation that divides an environment into evenly sized cells and assigns each cell a state describing whether the corresponding area is occupied, free, or not yet observed. It is a common abstraction in robotics and related fields because it reduces complex geometry into a form that is easy to store, update, and query.
The model is especially useful when sensors provide partial or noisy information. By converting measurements into grid-based estimates, a system can reason about obstacles, open space, and uncertainty in a consistent way.
1.1 Basic idea
The basic idea is to overlay a grid on a physical area and interpret each cell as a small region of space. If a sensor indicates that an object is present in a region, the corresponding cell is marked as occupied. If a sensor beam passes through a region without interruption, that area may be marked as free.
This discretization makes it possible to represent environments with simple data structures while preserving enough detail for navigation and mapping tasks. The grid can be repeatedly revised as new observations arrive.
1.2 Cell states
Each cell in an occupancy grid usually belongs to one of three broad categories: occupied, free, or unknown. These states capture the most important information needed for spatial reasoning.
The interpretation of a cell depends on the sensing method, the map resolution, and whether the grid is deterministic or probabilistic.
1.2.1 Occupied cells
Occupied cells correspond to areas believed to contain an obstacle, wall, object, or other physical obstruction. In navigation, these cells are treated as unsafe or non-traversable unless the obstacle can move or the map is otherwise updated.
1.2.2 Free cells
Free cells represent areas that are considered open and available for movement or observation. They are typically inferred from sensor rays or scans that have passed through the cell without detecting an obstacle.
1.2.3 Unknown cells
Unknown cells are regions for which the system has insufficient information. They are neither confirmed free nor confirmed occupied, and they often remain so until a sensor observes them directly.
1.3 Deterministic versus probabilistic grids
Deterministic occupancy grids store a fixed label for each cell, such as occupied or free. They are straightforward to interpret, but they may oversimplify uncertain measurements.
Probabilistic grids assign each cell a likelihood of occupancy. This approach is more flexible because it can express uncertainty, combine repeated observations, and support gradual refinement of the map over time. It is widely used in practice because real sensors rarely provide perfect readings.
2 Representation and Data Structures
Occupancy grids are usually implemented as arrays or similar regular data structures. Their simplicity makes them efficient to index, update, and visualize.
The chosen representation affects memory use, geometric accuracy, and the ease of integrating sensor data from different sources.
2.1 Grid resolution
Grid resolution refers to the size of each cell in physical units. A fine resolution captures more detail but increases memory consumption and computational cost. A coarse resolution is cheaper to store and process, but it may blur narrow passages or small obstacles.
The best resolution depends on the application. Navigation in a cluttered indoor space often requires smaller cells than large-scale environmental surveying.
2.2 Coordinate systems
Occupancy grid systems usually distinguish between coordinates in the real world and coordinates in the array used to store the map. Transformations between these systems are essential for updating and querying the grid correctly.
2.2.1 World coordinates
World coordinates describe positions in a physical reference frame, often using metric units such as meters. Sensor measurements, robot poses, and object locations are commonly expressed in this form.
2.2.2 Grid coordinates
Grid coordinates identify the row and column, or voxel index, of a cell in the map structure. Converting from world coordinates to grid coordinates allows the system to determine which cell corresponds to a given physical location.
2.3 Binary and probabilistic encoding
Binary encoding stores only two states, usually occupied and free, sometimes with unknown treated separately. It is compact and easy to use, but it cannot represent uncertainty well.
Probabilistic encoding stores a confidence value, often as a probability or log-odds score. This allows the map to accumulate evidence from multiple measurements and to smooth out occasional sensor errors.
2.4 2D versus 3D occupancy grids
Two-dimensional occupancy grids are common in ground robot navigation, where the environment can often be projected onto a plane. Three-dimensional grids extend the same idea to volume, allowing representation of shelves, overhangs, aerial obstacles, and complex structures.
Three-dimensional forms usually require more memory and more processing, so they are often implemented with compact representations or hierarchical structures.
3 Construction Methods
Occupancy grids are built from measurements collected by one or more sensors. Construction methods determine how raw observations are translated into cell states.
Because sensing is inherently imperfect, map building usually includes geometric projection, uncertainty handling, and repeated updates over time.
3.1 Sensor-based mapping
Sensor-based mapping uses observations from devices such as lidar, sonar, radar, or cameras to infer which parts of space are occupied or free. Each sensor type contributes different strengths, such as range accuracy, field of view, or robustness to lighting conditions.
3.1.1 Lidar-based construction
Lidar systems measure distance by emitting laser pulses and recording reflections. They are well suited to occupancy grid construction because they provide precise range data that can be traced back into the map to mark free and occupied cells.
3.1.2 Sonar-based construction
Sonar uses sound waves to estimate distance. It is often used in underwater or low-cost mobile systems, though its wider beam and greater uncertainty can make map interpretation less precise than lidar.
3.1.3 Camera-based construction
Camera-based methods infer occupancy from image data, often with the help of stereo vision, structure-from-motion, or learned depth estimation. These approaches can provide rich information, but they usually require more processing and careful calibration.
3.2 Ray tracing and inverse sensor models
Ray tracing identifies the cells crossed by a sensor beam from the sensor origin to the measured endpoint. Cells along the beam are often updated as free, while the endpoint region is updated as occupied if a return is detected.
An inverse sensor model defines how a measurement should alter the belief about each cell. It translates sensor observations into occupancy updates rather than attempting to model the environment directly from first principles.
3.3 Bayesian updating
Bayesian updating combines prior knowledge with new evidence to revise the estimated occupancy of each cell. Repeated observations can strengthen confidence in a cell’s status, while contradictory data can reduce it.
This method is popular because it provides a principled way to manage uncertainty and incorporate incremental measurements from a robot moving through the environment.
3.4 Multi-sensor fusion
Multi-sensor fusion merges data from different sensing modalities to produce a more reliable grid. For example, a robot may combine lidar for accurate geometry with cameras for visual context or sonar for complementary coverage.
Fusion can improve robustness when one sensor is limited by lighting, surface reflectivity, range, or noise. It also helps fill gaps that appear when a single sensor has blind spots.
4 Applications
Occupancy grids are widely used wherever a machine needs to understand space, avoid obstacles, or plan motion in a structured environment. Their regular layout makes them a practical foundation for many autonomy systems.
4.1 Mobile robot navigation
Mobile robots use occupancy grids to determine where they can move safely. The grid provides a clear distinction between traversable and blocked regions, helping the robot follow routes through rooms, corridors, warehouses, or outdoor areas.
4.2 Path planning
Path planning algorithms use occupancy information to search for routes between positions while avoiding cells marked as occupied. The grid supports common planning methods by turning geometry into a graph-like search space.
4.3 Obstacle avoidance
Obstacle avoidance relies on rapid checks of nearby cells to decide whether the robot should slow down, stop, or steer away from a hazard. Occupancy grids are useful because they provide an immediate local summary of nearby space.
4.4 Simultaneous localization and mapping
In simultaneous localization and mapping, a robot builds a map while also estimating its own position. Occupancy grids are often used as the map representation because they can be updated incrementally as the robot moves and senses its surroundings.
4.5 Environmental modeling
Occupancy grids can represent built spaces, natural terrain, or indoor layouts in a compact, analyzable form. They are used to study spatial structure, estimate available volume, and support simulation or decision-making systems.
5 Algorithms and Processing
Once a grid has been created, it must be maintained, refined, and sometimes combined with other maps. Processing steps often determine how useful the representation becomes in practice.
5.1 Grid updating
Grid updating revises cell values when new sensor data arrives. A well-designed update method can preserve previous evidence while still reacting quickly to changes in the environment.
5.2 Thresholding and classification
Thresholding converts probabilistic values into discrete labels. For example, cells above a chosen probability may be classified as occupied, while cells below another threshold may be treated as free.
This step is often used when a planning system needs a simple map rather than a graded uncertainty estimate.
5.3 Inflation of obstacles
Obstacle inflation enlarges occupied regions by a safety margin to account for robot size, localization error, and motion uncertainty. It helps prevent path planners from selecting routes that are technically open but too narrow or risky.
5.4 Map merging
Map merging combines multiple occupancy grids into a single representation. This is useful when data come from different robots, different time periods, or separate local maps that must be aligned into one frame.
5.5 Dynamic environment handling
Dynamic environment handling addresses changes caused by moving objects, shifting barriers, or temporary obstacles. Some systems decay old information over time so the map does not remain permanently biased by outdated observations.
6 Advantages and Limitations
Occupancy grids offer a practical compromise between simplicity and expressive power. They are easy to understand and widely supported, but they also have structural limits.
6.1 Strengths
A major strength is regularity: the uniform cell structure makes indexing and updating straightforward. Occupancy grids also support probabilistic reasoning, incremental construction, and broad compatibility with planning algorithms.
6.2 Weaknesses
The main weakness is discretization. Fine details can be lost when space is reduced to cells, and curved or irregular shapes may appear blocky. Large environments can also become expensive to store if high resolution is used.
6.3 Memory and computation trade-offs
Increasing resolution improves detail but raises memory use and processing time. Lower resolution reduces cost but may fail to capture important features such as thin walls, narrow gaps, or small objects.
6.4 Sensitivity to sensor noise
Noisy measurements can create false obstacles or erase real ones if not handled carefully. Probabilistic updates, filtering, and repeated observations help reduce these effects, but they do not eliminate them entirely.
7 Variants and Extensions
Several extensions build on the same grid concept while adding more structure or richer information. These variants address scalability, dynamics, and contextual interpretation.
7.1 Costmaps
Costmaps assign each cell a traversal cost rather than only a binary occupancy value. Cells near obstacles may receive elevated costs, allowing planners to prefer safer or smoother routes without treating every nonfree area as equally blocked.
7.2 Octrees and hierarchical grids
Octrees organize three-dimensional space in a hierarchy of subdivided cubes. They reduce memory use by storing large uniform regions compactly while preserving detail where it is needed.
7.3 Dynamic occupancy grids
Dynamic occupancy grids represent changing environments by estimating not only whether a cell is occupied, but also whether its occupancy is stable or in motion. They are useful in scenes with pedestrians, vehicles, or other moving elements.
7.4 Semantic occupancy grids
Semantic occupancy grids attach labels such as wall, floor, chair, or vehicle to cells in addition to occupancy information. This gives the map more meaning and can improve high-level reasoning, object-aware navigation, and human-robot interaction.
8 Related Technologies
Occupancy grids belong to a broader family of spatial representation methods. Related technologies differ in how they encode geometry, connectivity, and meaning.
8.1 Point clouds
Point clouds store sets of measured points in space, often with high geometric fidelity. Unlike occupancy grids, they do not directly divide space into labeled regions, which can make planning less direct.
8.2 Voxel maps
Voxel maps represent three-dimensional space as volumetric cells. They are closely related to occupancy grids, but the term is usually used when the representation is explicitly volumetric rather than planar.
8.3 Topological maps
Topological maps represent environments as nodes and connections rather than as metric grids. They are compact and useful for route-level navigation, but they provide less local geometric detail than occupancy grids.
8.4 Grid-based SLAM systems
Grid-based SLAM systems use occupancy grids as the map component in simultaneous localization and mapping. They integrate sensor data, motion estimates, and probabilistic updates to build maps while tracking position.