Occupancy Grid Mapping & SLAM

For a robot to navigate autonomously, it must construct a map of its environment and localize itself within it (Simultaneous Localization and Mapping - SLAM).

An occupancy grid represents the environment as a discrete grid of cells, where each cell m_i has an occupancy probability P(m_i).

• P(m_i) = 0.5: Unknown space
• P(m_i) > 0.5: Occupied (obstacle)
• P(m_i) < 0.5: Free space

To avoid floating-point underflow/overflow and speed up computations, we use Log-Odds representation: l(m_i) = log( P(m_i) / (1 - P(m_i)) )

The update rule when a sensor measurement z_t is received: l_t(m_i) = l_{t-1}(m_i) + inverse_sensor_model(m_i, z_t) - l_0

Sensors like LiDAR or ultrasound return distance measurements. Ray casting is used to update all cells along the beam path. Cells before the hit point are updated with free probability, while the cell at the hit point is updated with occupied probability.

Interactive goals: Run the Occupancy Grid simulator. Drive the robot around the map using keyboard/controls. Watch the sensor beams scan the environment, resolving walls and obstacles from unknown gray territory into occupied black or free white space. Try increasing sensor noise to see how probabilistic updates filter out spurious measurements.

CBSE/ICSE CS focus: Multi-dimensional arrays, spatial hashing, database coordinate queries, noise filtering algorithms.