robotics//motion planning//occupancy grid

An occupancy grid is a map that divides a floor (or a volume) into cells and stores in each cell the probability that it is occupied, and it is the standard map of mobile robots: lidar and depth-camera readings update it continuously, and a planner turns its free cells into the nodes of a graph to search. A warehouse of 50 by 50 metres at 5 cm resolution is a million cells, about a megabyte at one byte per cell, small enough for any onboard computer.

An occupancy grid is a map that divides a floor (or a volume) into cells and stores in each cell the probability that it is occupied, and it is the standard map of mobile robots: lidar and depth-camera readings update it continuously, and a planner turns its free cells into the nodes of a graph to search. A warehouse of 50 by 50 metres at 5 cm resolution is a million cells, about a megabyte at one byte per cell, small enough for any onboard computer.

Every beam of a range sensor says two things: the cells it crossed are probably free, and the cell where it stopped is probably occupied. Each cell keeps a running belief that every beam crossing it nudges up or down, so a person who walks through leaves a fading trace while a wall seen a thousand times becomes certain. For planning, cells are connected to their four or eight neighbours and searched with A* search or Dijkstra's algorithm; for a four-connected grid the Manhattan distance is the admissible heuristic.

Resolution is the design decision. Cells too coarse close narrow aisles and make a robot refuse paths that exist; cells too fine multiply memory and the number of nodes a search must expand, which costs planning time at every replan.

A navigation costmap is an occupancy grid with layers on top: an inflation layer that grows obstacles by the robot's radius, turning the map into the robot's configuration space, plus layers for moving obstacles and forbidden zones. Nav2 in ROS 2 is built this way.

Moving things are its weak point. The grid assumes a static world, so people and forklifts leave ghost obstacles until enough beams clear them; costmaps decay or clear old marks, and a robot in a busy aisle relies on its local planner more than on the map.

It assumes the robot's pose is known when each beam is drawn in. Building the map while estimating the pose at the same time is SLAM; in three dimensions the same idea is stored in an octree to avoid filling empty space with cells.