Occupancy Grid

The core of an occupancy grid is its probabilistic nature. Each cell stores the log-odds or probability of occupancy, typically updated using Bayesian filtering (e.g., an inverse sensor model). This allows the system to handle sensor noise and uncertainty, fusing multiple noisy observations over time into a stable, consistent map. For example, a cell might start with a prior probability of 0.5 (unknown), be updated to 0.8 after a LiDAR hit, and then gradually decrease toward 0.2 after several consecutive scans show no obstacle.

The environment is divided into a fixed, regular array of cells (voxels in 3D). This discretization simplifies complex spatial reasoning into a manageable data structure.

• Resolution is a critical parameter: finer grids capture more detail but require more memory and computation.
• World coordinates are mapped to grid indices, enabling fast lookup. This structure is inherently compatible with parallel processing on GPUs and efficient collision checking for path planning.

Occupancy grids are inherently dynamic. They integrate sensor data over time from one or more sensors (sensor fusion). As a robot moves, new sensor readings (from LiDAR, stereo cameras, or radar) are incorporated to update cell probabilities. This process:

• Resolves ambiguity from single, noisy measurements.
• Handles moving objects by using techniques like decay models or separate dynamic layers.
• Enables the creation of a consistent global map from a stream of local observations.

For real-time robotics, efficiency is paramount. Occupancy grids enable this through:

• Local updates: Only cells within the sensor's field of view are updated per cycle.
• Efficient data structures: Often implemented as 2D/3D arrays in memory for O(1) access. Octrees (like OctoMap) are used for sparse 3D environments to save memory.
• Parallelization: The independent nature of cell updates makes the algorithm highly parallelizable on modern hardware.

The grid is not just a map; it's a direct input to planning algorithms. The occupancy probabilities are used to compute costmaps for navigation.

• Inflation layers add costs around occupied cells to keep paths at a safe distance.
• Planners like A* or D* search over this cost grid to find safe, efficient paths.
• This tight coupling between perception (the grid) and action (the plan) is fundamental to autonomous navigation.

A critical feature is the explicit representation of unknown space (cells that have not yet been observed). This is distinct from free space. It allows robots to:

• Reason about exploration: Actively seek to reduce unknown areas (frontier-based exploration).
• Make safe decisions: A planner can treat unknown cells as potentially occupied, avoiding risky maneuvers into unexplored territory.
• This ternary state (occupied, free, unknown) is more informative for autonomous decision-making than a binary map.

A Particle Filter (or Sequential Monte Carlo method) is a common algorithm for implementing SLAM with occupancy grids, known specifically as FastSLAM. It represents the robot's possible poses (location and orientation) as a set of random samples called particles. Each particle carries its own hypothesis of the map. As the robot moves and senses, particles are weighted by how well their map aligns with new sensor readings, and are resampled accordingly. This method is highly effective for the nonlinear, non-Gaussian estimation problems inherent in robotics.

• Advantage: Can model complex multi-modal belief states (e.g., a robot unsure if it's in one of two identical corridors).
• Computational Load: The number of particles directly trades off with accuracy and real-time performance.

In robotic navigation, a Costmap is a specialized 2D grid used by planners (like the ROS Navigation Stack). While an occupancy grid stores occupancy probability, a costmap assigns a traversal cost to each cell. Costs integrate data from the occupancy grid, inflating obstacles to account for the robot's footprint, and can include factors like proximity to obstacles, preferred lanes, or terrain type. The path planner then searches for the minimum-cost path from start to goal.

• Layers: Typically composed of a static layer (pre-existing map), obstacle layer (real-time sensor data), and inflation layer (safety buffer).
• Output: Enables safe and efficient planning for differential drive or holonomic robots.

Sensor Fusion is the algorithmic process of combining data from multiple, disparate sensors (e.g., LiDAR, cameras, radar, IMU) to create a more accurate, complete, and reliable occupancy grid than is possible with any single sensor. It overcomes the limitations of individual sensors: LiDAR gives precise geometry but poor semantics, cameras provide rich texture and color but poor direct depth, and IMUs offer high-frequency motion data.

• Bayesian Framework: Often implemented using probabilistic updates (e.g., Bayesian filtering) where each sensor reading provides evidence to update the occupancy probability of a cell.
• Example: Fusing a camera-based semantic segmentation (identifying 'grass') with LiDAR geometry can mark a cell as 'occupied but traversable' for an outdoor robot.

A Dynamic Occupancy Grid extends the classic static model to also estimate the velocity of occupied cells. Instead of a binary state (free/occupied), each cell estimates a probability distribution over possible velocities. This is crucial for navigating in environments with moving objects like pedestrians, vehicles, or other robots. It allows the system to not only know where obstacles are but also where they will be, enabling predictive collision avoidance.

• Representation: Often uses a 4D grid (2D space + 2D velocity) or multiple hypothesis tracking per cell.
• Application: Essential for autonomous vehicles and robots operating in bustling human environments.