Occupancy grid maps

TL;DR:

• An occupancy grid cuts the world into cells and stores for each one how likely it is to be occupied: free, occupied or unknown.

• Each range reading marks the cells along the beam as free and the cell where it ends as occupied.

• Storing the evidence as log-odds turns each update into a simple addition, so repeated readings build confidence.

A robot with a distance sensor knows how far away the nearest thing is in a few directions. That is not yet a map. To plan a route, it needs to remember what it has seen and where. The most common memory for that is a grid of cells, laid over the floor like graph paper, with a number in each square.

What it does on a robot

An occupancy grid map divides the area into equal cells. Each cell holds the robot's belief that something solid occupies it. A cell starts out unknown. Readings gradually turn cells into free (probably empty) or occupied (probably an obstacle). Path planners such as A* (see path planning with A* on a grid) can search this map directly, and obstacle-avoidance methods read the occupied cells.

From range readings to cells

A range sensor such as a lidar or an ultrasonic sensor sends out a beam and reports a distance. A beam tells you two things. Everything between the sensor and the end point is free, because the beam passed through it. The cell at the end point is probably occupied, because the beam was reflected there. Everything beyond is unknown, because the beam never got there.

To turn this into cell updates, the robot needs its own position and heading in the map (see localization), then it works out which cells the beam crosses.

Probabilities and log-odds

A cell holds a probability p that it is occupied, starting at 0.5 (no idea). A reading nudges it. Probabilities are awkward to update by multiplication, so maps store the log-odds:

l = ln(p / (1 − p))

At p = 0.5, l = 0. A reading that says "occupied" adds a positive number, and one that says "free" adds a negative number. The conversion back is p = 1 / (1 + e^(−l)). Updating is just addition.

Worked example: a room mapped in 5 cm cells

A room is 4.0 m by 3.0 m. With 5 cm (0.05 m) cells, the grid has 4.0 / 0.05 = 80 columns and 3.0 / 0.05 = 60 rows, so 80 × 60 = 4800 cells. At one byte per cell that is 4800 bytes, small enough for a microcontroller.

The robot stands at the origin of the grid, facing along +x, and its range sensor reports a wall at 1.23 m straight ahead.

1. Which cell is the end? 1.23 / 0.05 = 24.6, so the beam ends in cell index 24 (covering 1.20 m to 1.25 m).

2. Free cells: cells 0 to 23 along the beam, which is 24 cells.

3. Occupied cell: cell 24.

Use a simple sensor model: an occupied reading adds l_occ = ln(0.7 / 0.3) = +0.847, a free reading adds l_free = ln(0.3 / 0.7) = −0.847 (example values: the sensor is right 7 times out of 10).

• After one hit, cell 24 has l = 0.847, so p = 1 / (1 + e^(−0.847)) = 0.70.

• After three hits (the robot takes three scans from the same place), l = 3 × 0.847 = 2.54, and p = 1 / (1 + e^(−2.54)) = 1 / (1 + 0.0789) = 0.927.

• If one scan misses (a noisy reading says free), l = 2.54 − 0.847 = 1.69 and p = 1 / (1 + e^(−1.69)) = 0.844. One bad reading dents the belief but does not erase it.

• A cell on the beam path that gets three free readings has l = −2.54 and p = 0.073.

You decide thresholds to read the map: for example p > 0.65 is treated as occupied, p < 0.35 as free, and in between as unknown. Cells beyond the wall, never touched by a beam, stay at p = 0.5.

Where it goes wrong

• Pose error. If the robot thinks it is 10 cm from where it is, every cell is marked in the wrong place and the walls smear into thick, doubled lines. Mapping depends on good localization, and the two are combined in SLAM.

• Resolution. Fine cells are accurate but cost memory and time: the same room at 1 cm cells has 400 × 300 = 120,000 cells, 25 times as many. Coarse cells blur narrow gaps.

• Moving objects. A person walking through leaves ghost obstacles unless the free updates cancel them.

• Glass and mirrors. Lidar and sonar may pass through or bounce off them, giving false free or occupied cells.

• Sensor limits. Beams have a maximum range and a width, so a single reading marks a cone, not a line.

• Overconfidence. If log-odds grow without limit, a cell can never change its mind. Clamp the values to a range.

Safety: A map is a belief, not a fact. Do not let a robot drive through a region just because the map shows it as free, especially near stairs, glass doors or people. Keep a live obstacle sensor and an emergency stop active, and do not look into the aperture of a lidar or open it, since its laser can harm eyes if the unit is damaged or modified.

How real robots use it

Robot vacuums, delivery robots and research platforms all keep grid maps. Some store separate layers, such as one for static walls and one for recent obstacles, and inflate the occupied cells by the robot's radius so a planner can treat the robot as a point. Three-dimensional versions use cubes (voxels) in the same way. The grid is the shared map that localization, planning and avoidance all read.

Try it yourself

On graph paper, mark a square room with a robot at one position. Write down five range readings at different angles and shade the free cells and the end cell for each. Then repeat from a second position. Where the two sets of readings agree, the evidence adds up. Try adding a "wrong" reading and see how the cell reacts.

Frequently asked questions

What is the difference between free and unknown?

A free cell has been seen to be empty by a beam passing through it. An unknown cell has no evidence either way, usually because no beam reached it.

Why use log-odds?

They turn the Bayesian update into addition, which is quick and avoids numbers getting too close to 0 or 1 in floating point arithmetic.