Occupancy Grid

Each cell in an occupancy grid stores a probability value, typically between 0 and 1, representing the likelihood that the corresponding volume of space is occupied by an obstacle. This is a direct application of Bayesian estimation, where sensor measurements are used to recursively update these probabilities. The grid does not store raw sensor data but a fused, persistent belief state.

• Binary vs. Probabilistic: Early grids used binary (occupied/free) values, but modern implementations use probabilities to model sensor noise and ambiguity.
• Bayesian Update Rule: The probability for a cell is updated using Bayes' theorem: P(Occupied | Measurement) ∝ P(Measurement | Occupied) * P(Occupied). This allows the system to integrate evidence over time.

The environment is divided into a fixed, regular array of cells, most commonly in 2D (a grid) or 3D (a voxel grid). This discretization transforms the continuous world into a finite, computationally tractable representation.

• Resolution Trade-off: Cell size is a critical parameter. Fine resolution captures detail but increases memory and computation costs exponentially. Coarse resolution is efficient but may miss small obstacles.
• Hierarchical Grids: Advanced implementations use octrees (like OctoMap) to adaptively subdivide space only where needed, providing high resolution near obstacles and low resolution in open areas, optimizing memory usage.

Occupancy grids are a primary fusion framework for integrating asynchronous, heterogeneous sensor data. Measurements from lidar, radar, sonar, and stereo cameras are all converted into a common representation of occupancy evidence.

• Inverse Sensor Model: Each sensor type requires an inverse sensor model function that translates a raw measurement (e.g., a lidar range return) into an update for the cells along the measurement ray. This model defines P(Measurement | Occupied) for cells within the sensor's field of view.
• Temporal Fusion: The grid maintains state over time, allowing it to fuse data from sensors operating at different rates and to handle temporary occlusions.

While classic occupancy grids assume a static world, real-world applications require handling moving objects. This is addressed through techniques that model change over time.

• Temporal Filtering: Simple methods use a decay factor or a moving average to gradually forget old measurements, allowing the map to adapt to changes.
• Dynamic Occupancy Grids: More advanced approaches extend the state representation. Each cell may store not just occupancy probability, but also estimates of velocity and acceleration, enabling short-term motion prediction. These are often implemented using Bayesian filtering techniques over the grid cells.

The processed occupancy grid is the primary input for path planning and collision avoidance algorithms in autonomous robots and vehicles.

• Cost Maps: Planning algorithms often convert the probabilistic grid into a cost map, where cell costs are inversely related to the distance from the nearest occupied cell, creating gradients for smooth planning.
• Traversability Analysis: Beyond simple occupancy, grids can encode additional properties like terrain type, slope, or semantic class (e.g., road, grass, building) to inform more sophisticated navigation decisions.

Occupancy mapping is intrinsically linked with the Simultaneous Localization and Mapping (SLAM) problem. The robot must know its own pose to correctly insert sensor data into the grid, and a consistent map is needed to localize.

• Mapping with Known Poses: If pose is provided (e.g., from a high-quality Visual-Inertial Odometry system), building the grid is straightforward.
• Full SLAM: In graph-based SLAM, the occupancy grid is often built as a post-processing step after the pose graph is optimized. Alternatively, pose graph constraints directly influence the consistency of the resulting map.

SLAM is the core computational challenge that occupancy grids help solve. It is the process by which a robot builds a map of an unknown environment while simultaneously determining its own position within that map. Occupancy grids provide a probabilistic, discretized representation of the map, which is updated as the robot moves and senses obstacles.

• Online vs. Offline: SLAM can be performed online (in real-time) or offline (processing logged data).
• Front-end vs. Back-end: The front-end handles sensor data and feature extraction (e.g., creating an occupancy grid from lidar scans), while the back-end performs optimization to correct accumulated pose error.
• Key Challenge: The inherent coupling—accurate mapping requires knowing the robot's pose, and accurate localization requires a good map.

Bayesian filtering is the overarching probabilistic framework that underpins occupancy grid updates. It provides a recursive method to estimate the state of a dynamic system (like a map) from noisy sensor data.

• Recursive Update: The filter maintains a belief state (the grid) and updates it with each new observation using Bayes' rule: Belief(state) ∝ MeasurementModel * PriorBelief(state).
• Occupancy Grid Mapping is a specific instance of a Bayes filter applied to a static world, where each cell's occupancy probability is estimated independently.
• Related Algorithms: The Kalman Filter, Particle Filter, and Histogram Filter are all implementations of the Bayesian filtering principle for different problem structures.

The inverse sensor model is a critical function in occupancy grid mapping that defines how a sensor measurement translates into an update for grid cell probabilities. It answers: "Given I received measurement z at pose x, what is the probability that cell m_i is occupied?"

• Contrast with Forward Model: A forward sensor model gives P(z | m_i, x) (the likelihood of a measurement given the map). The inverse model provides P(m_i | z, x), which is needed for the Bayesian update.
• Design Challenge: Crafting an accurate inverse model is non-trivial, as it must account for sensor noise, field of view, and beam spreading. For lidar, it often involves modeling a probability distribution along the beam and at the endpoint.
• Approximation: The standard log-odds approach uses a simplified, piecewise model (high probability at the endpoint, low probability along the beam).

A dynamic occupancy grid extends the classic static model to also estimate the velocity of occupied cells, enabling tracking of moving obstacles within the grid framework.

• State Representation: Each cell's state is expanded from a binary {Occupied, Free} to include a velocity vector (v_x, v_y). The belief becomes a distribution over occupancy and motion.
• Bayesian Filtering: Requires more complex filters, like a Bayesian Occupancy Filter (BOF) or particle-based methods, to estimate the joint distribution.
• Critical for Autonomy: Allows autonomous vehicles to not only know where obstacles are but also predict where they will be, enabling safe path planning in dynamic environments like urban streets.

Elevation mapping is a complementary 2.5D representation often used alongside occupancy grids. Instead of a binary occupancy, each grid cell stores the estimated height (elevation) and variance of the terrain surface.

• Data Fusion: Commonly created by fusing 3D sensor data (lidar, stereo vision) and robot pose estimates. Octomap can also be used to generate elevation data by projecting 3D occupancy.
• Application: Crucial for ground robot navigation over uneven terrain, allowing the system to distinguish between traversable slopes and impassable obstacles.
• Relationship to Occupancy Grids: While an occupancy grid answers "is something there?", an elevation map answers "what is the height of the surface there?". They are frequently used in tandem for robust navigation.