Occupancy Grid Map

Each cell in an occupancy grid does not store a binary occupied/empty state. Instead, it holds a probability of occupancy, typically modeled using a log-odds representation for numerical stability. This allows the system to fuse multiple, potentially conflicting, sensor readings over time using Bayesian updates (e.g., the inverse sensor model). The probability value reflects the system's cumulative belief about that space, gracefully handling sensor noise and temporary occlusions.

The environment is divided into a fixed, regular array of cells, most commonly in 2D (for ground robots) or 3D (voxel grids for drones or manipulators). This discretization imposes a fundamental resolution vs. memory trade-off.

• Fine resolution (e.g., 5 cm cells) captures environmental details but requires significant memory and computation.
• Coarse resolution (e.g., 20 cm cells) is efficient but may miss narrow passages or small obstacles. The chosen cell size is a critical design parameter that directly impacts navigation safety and computational feasibility.

Occupancy grids are inherently designed for multi-sensor fusion. Measurements from diverse exteroceptive sensors—like LiDAR range scans, stereo camera depth maps, or sonar readings—are converted into probabilistic evidence about cell occupancy. Each sensor's unique noise characteristics and field-of-view are accounted for via its inverse sensor model. This allows a robot to build a consistent, unified world model from heterogeneous, asynchronous, and imperfect data streams, which is essential for robust operation in complex environments.

Traditional occupancy grids often assume a static world, where mapped obstacles do not move. This is a significant limitation in human environments. Modern extensions address this by:

• Temporal filtering: Discounting old measurements to allow the map to "forget" and reflect changes.
• Dynamic occupancy grids: Modeling each cell with a velocity distribution to track moving obstacles.
• Multi-hypothesis tracking: Distinguishing between static, dynamic, and potentially dynamic objects. These advancements are crucial for autonomous vehicles and robots operating around people.

The naive implementation of a high-resolution 3D grid is prohibitively expensive. Key engineering optimizations include:

• Octree/Quadtree Representations: Hierarchical data structures that subdivide space only where needed, dramatically reducing memory for sparse environments.
• Hashed Data Structures: Sparse voxel grids that store only occupied cells.
• Multi-Resolution Maps: Using fine resolution near the robot and coarser resolution at a distance.
• GPU Acceleration: Parallelizing Bayesian updates across thousands of cells using frameworks like CUDA or OpenCL for real-time performance.

The primary utility of an occupancy grid is to enable safe motion planning. Planners treat the grid as a costmap:

• High occupancy probability translates to a high cost or forbidden region.
• Low/unknown probability translates to traversable space. Algorithms like A* or D* search for optimal paths through this cost field. Furthermore, the gradient of the occupancy probabilities can be used for potential field methods, where the robot is repelled from occupied cells and attracted to the goal.

The core computational problem that an occupancy grid map solves. SLAM is the process by which a robot builds a map of an unknown environment while simultaneously using that map to localize itself within it. The occupancy grid is a common probabilistic representation for the map in many SLAM implementations.

• Front-end processes sensor data (e.g., LiDAR scans) to generate local occupancy observations.
• Back-end optimizes the global map and robot trajectory, correcting errors like drift.

The primary sensor data used to populate occupancy grids. LiDAR sensors emit laser pulses to measure distances, creating a point cloud—a dense set of 3D coordinates representing surfaces in the environment.

• Each LiDAR scan is a snapshot point cloud.
• The occupancy grid mapping algorithm projects these 3D points into a 2D plane (for 2D maps) and uses ray casting to determine which cells along the laser beam's path are free (unoccupied) and which are occupied.

The mathematical engine for updating cell probabilities. Occupancy grids use a Bayesian filtering approach, often implemented via the log-odds representation, to fuse multiple, noisy sensor measurements over time.

• Each cell stores a log-odds value, not a raw probability.
• New sensor readings (e.g., a LiDAR hit) provide evidence that updates the log-odds.
• This method is computationally efficient and prevents probabilities from saturating at 0 or 1.

The primary application of a completed occupancy grid. Once built, the grid acts as a configuration space for planning. Algorithms like A* or D* search for collision-free paths from a start to a goal.

• Occupied cells (high probability) are treated as impassable obstacles.
• Free cells (low probability) form the traversable space.
• Unknown cells can be treated as obstacles (conservative) or explored.

Techniques to improve the accuracy of the inputs to the grid. Raw sensor data is noisy. Sensor fusion combines data from multiple sources (LiDAR, IMU, wheel encoders) to create a better estimate of the robot's pose (position & orientation), which is critical for correctly registering scans into the global map.

• Kalman Filters and Particle Filters are common estimation algorithms.
• Accurate pose estimation minimizes misalignment when integrating new scans.