Navigation · Theory · M2

M2-T1 — Occupancy Grids for Planning

A grid is the simplest map a planner can use. The two choices that matter are how fine it is and what to do about cells nobody has seen.

Lesson 1 of 6
Module 2: Maps and Costmaps
Theory
About 8 minutes to read

Most mobile robots plan on a grid: the floor is cut into small squares and each square says whether it is free, occupied or unknown. The idea is old and plain, which is why it is everywhere. Two decisions, made once and rarely revisited, decide how well it works: the size of the squares, and what a planner is allowed to assume about squares nobody has looked at.

Learning objectives

After this lesson, you should be able to:

Describe an occupancy grid and how a probability per cell becomes free, occupied or unknown.
Choose a resolution from the smallest gap the robot must pass and estimate the memory and search cost of that choice.
Explain the three policies for unknown space (forbid, allow, penalise) and when each is right.
Explain why a planning grid is derived from the map rather than being the map.

The intuition

Imagine laying graph paper over the floor plan of the hospital and shading every square that has a wall in it. A planner can now ask a very cheap question about any place: is this square shaded? That is an occupancy grid. It does not know what a door or a bed is. It only knows squares.

A mapping system such as SLAM keeps, for every cell, a belief that the cell is occupied. A navigation system does not need the belief, it needs a decision, so it applies two thresholds: below one the cell is free, above the other it is occupied, and in between, or never observed, it is unknown. The planning grid is the result of that decision, together with the choices made in this lesson.

The same wall and 0.9 m door on two grids. A coarse grid saves memory but turns a comfortable door into a squeeze, and thickens every wall to a whole cell.

The mathematics

From belief to decision

Mapping code usually stores the log-odds of occupancy, because adding evidence is then a sum. A cell with probability p has log-odds l:

Log-odds

l=\ln (\frac{p}{1-p})

p=\frac{1}{1+e^{(-l)}}

\text{each hit adds}\,l_{\text{hit}},\,\text{each miss adds}\,l_{\text{miss}}(\text{negative}),\,l\,\text{is clamped to}[l_{\min},\,l_{\max}]

p: probability that the cell is occupied.
l: its log-odds; 0 means “no idea” (p = 0.5).
l_hit, l_miss: evidence added per observation that ends in the cell, or passes through it.
l_min, l_max: clamps that keep the cell able to change its mind later.

The clamp is not decoration. Without it a cell seen occupied a hundred times needs a hundred misses to be freed, and a moved object becomes a ghost (lesson M2-T4).

Choosing a resolution

A grid of cell size s covering W × H metres has (W/s)(H/s) cells. Halving s multiplies the cells, and the work to search them, by about four. The cell size must resolve the smallest gap the robot has to pass with room to spare, and no more:

Resolution rule

\mathrm{gap}_{\{\text{in}\}\text{cells}}=\frac{\mathrm{gap}}{s}\;\mathrm{keep}

\mathrm{gap}_{\{\text{in}\}\text{cells}}\ge \frac{2\times r_{\text{inscribed}}}{s}+3

rule of thumb

s\le \frac{\mathrm{gap}}{8}

for the narrowest door

The “+ 3” leaves a few cells of free space inside the door after the inflation of the next lesson. A wall also becomes at least one cell thick, so the grid cannot be finer than the thinnest wall is useful.

Unknown space

Policies for unknown space
Policy	Planner may cross unknown?	Good for	Risk
Forbid	Never	Maps that are complete; safety-critical routes	Cannot explore, and a stale gap in the map blocks the route forever
Allow	Yes, at the same cost as free space	Exploration; planning towards frontiers	May plan through walls that were never seen
Penalise	Yes, but with a higher cost	Mixed: complete map with a few holes	The penalty is one more number to tune

A worked example

Resolution for the east wing. The map is 50 m × 30 m and the narrowest door is 0.90 m. Scout has an inscribed radius of 0.20 m.

Resolution example

\text{cells at}\,0.05\,\mathrm{m}:\,(\frac{50}{0.05})\times (\frac{30}{0.05})=1000\times 600=

600\,000

0.6 MB at one byte per cell

\text{cells at}\,0.10\,\mathrm{m}:\,500\times 300=

150\,000

\text{cells at}\,0.25\,\mathrm{m}:\,200\times 120=

24\,000

door in cells

:\,\frac{0.90}{0.05}=18

\frac{0.90}{0.10}=9

\frac{0.90}{0.25}=3.6

needed

:\,\frac{2\times 0.20}{0.10}+3=7\,\text{cells at}\,0.10\,\mathrm{m},\,\frac{2\times 0.20}{0.25}+3=4.6\,\text{cells at}\,0.25\,\mathrm{m}

At 0.25 m the door is 3.6 cells wide, fewer than the 4.6 needed, so it can close completely depending on where the wall lines fall relative to the grid. At 0.10 m the door is 9 cells, which is more than the 7 needed. At 0.05 m it is also fine but costs four times as many cells for no extra benefit here. The choice is 0.10 m.

Evidence in log-odds. With p_hit = 0.7 each hit adds ln(0.7/0.3) = 0.847. Three hits give l = 2.54, which is p = 0.927. A cell that has been hit three times is already “probably occupied”, and with a clamp at l_max = 3.5 it takes five equally strong misses (5 × 0.847 = 4.2 > 3.5) to bring the cell below zero again.

Engineering implications and limitations

Match the grid to the narrowest gap, not the sensor

A lidar can resolve centimetres; the planner does not need it to. The SLAM map can be fine (0.05 m) while the navigation grid is coarser (0.10 m). Resampling takes the maximum, so a thin obstacle is never lost.

Three states, not two

Nav2 stores unknown as its own value (-1 in a published OccupancyGrid message) and lets the costmap decide with the track_unknown_space setting whether it is treated as free, unknown or lethal. Decide on purpose: the default that works in a simulation of a finished map can stall a robot in a real building where the map has holes.

Size matters twice

Resolution multiplies memory and the cost of every layer update, inflation and search. A 0.025 m grid of a whole hospital floor can need more memory and time than the planning budget allows. Rolling windows (a costmap that moves with the robot) bound the cost for local planning (module 6).

Where the grid ends

A grid describes occupancy, not meaning. It cannot say that a region is a lift, that a lane is one-way, or that a surface is carpet. Lessons M2-T5 and M2-T6 add those.

Common misconceptions

“A finer grid is always a better map.”

It is a more expensive map. Beyond the size needed to resolve the narrowest gap, finer cells only add memory and search time.

“Unknown means free until proven otherwise.”

That is one policy. For a robot in a finished building, unknown cells are more likely to be an unmapped wall than open floor, so forbidding or penalising them is often right.

“The SLAM map and the planning grid are the same thing.”

They are related. The planning grid is derived from the map with a threshold, a resolution and a policy chosen for the planner.

“Probabilities are stored so that planners can use them.”

Planners need decisions. The probability is for the mapper; the planner gets free, occupied or unknown.

Engineering takeaways

An occupancy grid stores free, occupied or unknown per cell; mapping keeps a belief and the planner gets a decision.
Log-odds make evidence additive, and the clamps keep cells able to change their mind.
Pick the resolution from the narrowest gap the robot must pass: about eight cells across, not finer.
Halving the cell size quadruples cells and search work.
Decide the unknown-space policy deliberately: forbid, allow or penalise.

References and further reading

The original occupancy grid papers and the Nav2 documentation.

H. Moravec and A. Elfes, “High Resolution Maps from Wide Angle Sonar”, IEEE ICRA, 1985.
A. Elfes, “Using Occupancy Grids for Mobile Robot Perception and Navigation”, Computer, 22(6), 1989.
S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, chapter 9.
Nav2 documentation, “Costmap 2D” and “Setting Up the Costmap”, docs.nav2.org.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

A hospital floor is 80 m × 40 m. How many cells does a 0.05 m grid have, and how many does a 0.10 m grid have?

Explanation

At 0.05 m: 1600 × 800 = 1 280 000 cells. At 0.10 m: 800 × 400 = 320 000 cells, a quarter as many.

Question 2

The narrowest door is 0.80 m and Scout’s inscribed radius is 0.20 m. Is a 0.25 m grid acceptable by the rule in this lesson?

Explanation

No. The door is 3.2 cells wide, but the rule needs (2 × 0.20)/0.25 + 3 = 4.6 cells. A 0.10 m grid gives 8 cells against 7 needed, which passes.

Question 3

A cell has log-odds 2.0 and the clamp is 3.5. Each miss adds −0.4. How many misses clear it to the free side (l below 0)?

Explanation

It needs more than 5 misses: after 5 the log-odds is 0, which is still “no idea”, and the sixth makes it −0.4. Without a clamp a cell hit many more times would need correspondingly more.

What’s next

Next: how an occupancy grid becomes a cost map that keeps a body-sized robot away from walls.

Practice this lesson

Build an Inflated Costmap

Scout keeps clipping door frames: inflate the obstacles correctly so the planner keeps clear.

Next lesson

M2-T2 — Inflation and Footprints

Compute the inscribed and circumscribed radii of a footprint and set an inflation radius and cost decay from them.

Nothing below is required to finish this lesson.

Lab
M2-L1: Build an Inflated Costmap
Scout keeps clipping door frames: inflate the obstacles correctly so the planner keeps clear.

Learning objectives

The intuition

The mathematics

From belief to decision

Choosing a resolution

Unknown space

A worked example

Engineering implications and limitations

Match the grid to the narrowest gap, not the sensor

Three states, not two

Size matters twice

Where the grid ends

Common misconceptions

“A finer grid is always a better map.”

“Unknown means free until proven otherwise.”

“The SLAM map and the planning grid are the same thing.”

“Probabilities are stored so that planners can use them.”

Engineering takeaways

References and further reading

Knowledge check

Question 1

Question 2

Question 3

What’s next

Build an Inflated Costmap

M2-T2 — Inflation and Footprints

Related content

Get notified when the next lesson and new labs are released.