Occupancy Grid Map

A map that divides the environment into cells, each storing the probability that it's blocked by an obstacle.

The occupancy grid map was proposed by Hans Moravec and Alberto Elfes in 1985, and is one of the most common map forms in mobile robotics. It divides a plane (or a volume) into uniform cells, each storing the probability of being occupied, usually classified for use into free, occupied, and unknown. Each lidar or depth-camera frame updates the cells one by one through a binary Bayes filter, commonly implemented using log-odds to make the updates easy to accumulate. The classic algorithm assumes the robot's pose is already known, so it's commonly paired with SLAM. Path planning and obstacle avoidance can compute directly on top of it: ROS's nav_msgs/OccupancyGrid message is exactly this kind of map, with −1 marking unknown cells. A 3D version exists as octree-based maps such as OctoMap, and self-driving perception's occupancy networks instead predict 3D occupancy directly with a neural network.

ExampleA robot vacuum builds a planar grid map with its lidar while moving: walls and furniture get marked occupied, floor it has already crossed gets marked free, and unexplored areas stay unknown; it then plans its cleaning route over the free cells.

Also called

Occupancy Grid, Grid Map

Related

Simultaneous Localization and Mapping · Costmap · OctoMap · Occupancy Network · Path Planning · LiDAR SLAM

Sources

Wikipedia: Occupancy grid mapping
ROS 2 nav_msgs/OccupancyGrid 消息定义 (Chinese)