Occupancy Grid

Each cell in an occupancy grid stores a probability value (typically between 0 and 1) representing the belief that the corresponding volume of space is occupied by an obstacle. This is fundamentally different from a binary map.

• Bayesian Update: New sensor measurements (e.g., from LiDAR or depth cameras) are integrated using recursive Bayesian estimation, often via a log-odds formulation for numerical stability.
• Handles Uncertainty: Explicitly models sensor noise and the inherent ambiguity of partial observations (e.g., an unseen cell may be free or occupied).
• Prior Knowledge: Can be initialized with a uniform prior (e.g., 0.5) or informed priors if map structure is partially known.

The environment is partitioned into a fixed, regular array of volumetric cells (voxels in 3D, pixels in 2D). This transforms the continuous world into a discrete, computationally tractable data structure.

• Resolution Trade-off: Cell size determines the map's fidelity versus memory and computational cost. Finer resolution captures more detail but increases grid size exponentially in 3D.
• World Frame: The grid is anchored to a fixed global or local coordinate frame, allowing consistent integration of sensor data over time.
• Bounded Space: The grid has finite dimensions, requiring strategies for dynamic expansion or sliding window approaches for large-scale navigation.

The grid is updated by inverse sensor models that translate raw sensor readings into probabilistic evidence about cell occupancy.

• Ray Casting: For a range sensor like LiDAR, cells along the measured ray are typically updated as free space, while the cell at the endpoint is updated as occupied. Cells beyond the endpoint remain unknown.
• Multi-Sensor Fusion: Evidence from heterogeneous sensors (e.g., stereo cameras, radar, ultrasonic sensors) can be fused into the same grid using the same probabilistic framework, provided each sensor's noise characteristics are modeled.
• Dynamic Objects: Basic occupancy grids model static environments; tracking dynamic objects requires separate filtering or layered representations.

Occupancy grids are the spatial backbone for several critical autonomous system functions.

• Mapping: Building a persistent occupancy map of an environment (a key output of SLAM systems).
• Path Planning: Algorithms like A* or D* search for collision-free paths through the grid, treating occupied cells as obstacles.
• Collision Avoidance: Provides a real-time model for local planners to evaluate potential motions for safety.
• Space Exploration: In robotic exploration, the grid identifies frontiers between known free and unknown space to guide the robot towards unmapped areas.

The basic occupancy grid has been extended to address its limitations and enable richer scene understanding.

• Semantic Occupancy Grids: Each cell stores not only occupancy probability but also a distribution over object classes (e.g., car, pedestrian, vegetation), enabling semantic-aware navigation.
• Elevation Maps: A 2.5D variant where each (x,y) column stores height or multiple surface layers, efficient for ground vehicle navigation.
• ESDF (Euclidean Signed Distance Field): Derived from an occupancy grid, an ESDF stores the distance from each cell to the nearest obstacle surface, providing gradient information crucial for smooth trajectory optimization.
• Multi-Resolution Hierarchies: Using data structures like Octrees (e.g., OctoMap) to represent the grid, allowing for efficient memory use by allocating fine resolution only where needed.

Occupancy grids are one of several ways to model 3D space, each with distinct trade-offs.

• vs. Point Clouds: A point cloud is a raw, unstructured set of measurements. An occupancy grid is a processed, unified probabilistic model derived from point clouds. Grids are better for queries like "is this volume occupied?"
• vs. Voxel Grids: A (binary) voxel grid is a similar discrete structure, but an occupancy grid is explicitly probabilistic. A voxel grid is often the output after thresholding an occupancy grid.
• vs. Signed Distance Fields (SDFs): SDFs provide a continuous distance to the nearest surface, ideal for precise geometry and rendering. Occupancy grids are better for fast, probabilistic updates from streaming sensor data.
• vs. Bounding Boxes: Bounding boxes are object-centric. Occupancy grids are environment-centric, modeling all occupied space regardless of object identity, which is crucial for navigating cluttered, unstructured environments.

Occupancy grids act as a spatial middleware between low-level perception and high-level task and motion planning (TAMP). A semantic layer can be added where cells are tagged with object classes from semantic segmentation, creating a semantic occupancy grid. This allows planners to reason not just about "free space" but also about "navigable space near the kitchen counter" or "area containing fragile objects." This bridges geometric mapping with symbolic AI for complex instruction following.

A voxel grid is a volumetric, grid-based representation of 3D space where each cubic cell (voxel) contains discrete data, such as occupancy probability, color, or semantic features. Unlike an occupancy grid which is primarily probabilistic, a voxel grid is a more general data structure often used as the input tensor for 3D convolutional neural networks (3D CNNs) for tasks like 3D object detection and semantic segmentation. It provides a regular, memory-intensive but computationally efficient format for processing 3D data.

A point cloud is a set of discrete data points in a 3D coordinate system, representing the external surfaces of objects as captured by sensors like LiDAR or depth cameras. It is the raw, unstructured data from which many representations, including occupancy grids, are derived. Key processing tasks include:

• Point cloud registration: Aligning multiple scans.
• Surface reconstruction: Creating a continuous mesh.
• 3D object detection: Finding and classifying objects. Architectures like PointNet are designed to process this unordered data directly.

A Signed Distance Field (SDF) is a continuous volumetric representation where the value at any 3D point is the shortest distance to the surface of an object, with the sign indicating interior (negative) or exterior (positive). It provides an implicit, smooth surface representation ideal for collision checking and high-fidelity 3D reconstruction. Unlike the probabilistic, discrete occupancy grid, an SDF encodes precise geometry and is commonly used in advanced sim-to-real transfer learning and Neural Radiance Fields (NeRF).

Simultaneous Localization and Mapping (SLAM) is the core robotics problem where an agent builds a map of an unknown environment while simultaneously tracking its location within it. Occupancy grids are a classic map representation used in probabilistic SLAM frameworks like Gmapping (using a particle filter). SLAM algorithms fuse data from LiDAR, cameras (Visual Odometry), and IMUs (Visual-Inertial Odometry) to maintain a consistent, globally referenced map essential for autonomous navigation.

An octree is a hierarchical tree data structure that recursively subdivides 3D space into eight octants. It provides a memory-efficient, multi-resolution alternative to a dense occupancy grid. Only subdivisions containing data or obstacles are allocated, enabling:

• Efficient storage of sparse environments.
• Fast spatial queries for collision detection.
• Adaptive resolution (finer detail near objects, coarser elsewhere). Octrees are fundamental in 3D computer graphics, physics engines, and advanced mapping systems where scalability is critical.

Sensor fusion is the process of combining data from multiple disparate sensors (e.g., LiDAR, cameras, radar, IMU) to produce a more accurate, complete, and reliable environmental model than any single sensor provides. Occupancy grids are a common fusion output, integrating probabilistic readings from different modalities into a unified spatial representation. Techniques like Kalman filters and Bayesian inference are used to update grid cell probabilities, making the system robust to individual sensor noise, occlusion, or failure.