OccupancyGrid

An occupancy grid is a probabilistic representation of an environment used in robotics and autonomous systems. It expresses the environment as a two-dimensional grid of uniformly sized cells, where each cell stores the probability that the corresponding area is occupied by an obstacle. The map is built from sensor measurements and robot motion and is commonly used for navigation, obstacle avoidance, and as a input to SLAM systems.

Each cell holds p(occupied|observations). To facilitate updates, the grid often stores the log-odds of occupancy, L = log(p/(1-p)), allowing simple incremental updates via Bayes' rule as new sensor data arrives. The inverse sensor model specifies how a measurement affects the grid: for a laser scan, cells along a beam are updated as free, the farthest cell at the detected range is updated as occupied, and other cells remain unchanged or probabilistically updated.

Construction and use: The robot's pose is used to transform local measurements into the world frame, and the grid has a chosen resolution (cell size) that trades detail for memory. In practice, occupancy grids are updated online as the robot moves, producing a map that can be used by a planner or by localization algorithms. Variants include Bayesian occupancy grids and sparse representations.

Advantages and limitations: Occupancy grids are intuitive and easy to implement and integrate with standard planning and localization frameworks. Limitations include the independence assumption between cells, discretization error, and memory requirements for large environments; dynamic objects and errors in the sensor model can degrade accuracy. Extensions include probabilistic gray-level grids, multi-resolution grids, and posterior estimating methods.