Perception · Theory · P8
P8-T6 — Scene Representations for Downstream Robotics Tasks
The fused result is only useful in the form the next module can use. Choose the form from the question it has to answer.
After the sensors are aligned and their estimates fused, the robot still has to hand the result to something: a planner that needs to know where it may drive, a controller that follows a person, a manipulator that must grasp a part. These consumers ask different questions, and no single representation answers all of them well. This lesson surveys the common representations, what each is good for and what it costs, and the rules that make an interface reliable: say what is unknown, state the frame and the time, and carry the uncertainty. It closes Module 8 with the point it began with: a scene description is a claim about the world, and it is only as trustworthy as the alignment, timing and uncertainty behind it.
Learning objectives
After this lesson, you should be able to:
- Describe object lists, occupancy grids, free-space maps, semantic maps and point clouds, and the questions each answers.
- Update an occupancy cell with log-odds and distinguish occupied, free and unknown.
- Estimate the memory of a grid or voxel representation.
- Choose a representation for a robot task and state what the interface must carry.
The idea: represent what the decision needs
The same scene can be written down in several ways, and each makes some questions easy and others hard. A list of objects makes “how many people are within 5 m?” easy and “is there a path between these shelves?” awkward. A grid of cells makes the second easy and the first awkward.
Object lists
A list of tracked objects, each with an identity, a class, a pose, a size, a velocity and an uncertainty. It is compact, carries meaning, and is what planners that predict others’ motion need. It is weak at describing things that are not objects: the floor, a wall, an unknown region.
Occupancy grids
The space around the robot is divided into cells, and each cell holds the probability that it is occupied. A planner can check a path cell by cell. The grid is independent of how many objects there are and represents unknown areas explicitly. It carries no identity or velocity, and its memory grows with the area and the resolution (and with the cube of the resolution in 3D).
Free space and drivable area
A region that the robot may enter, often derived from the grid or from a segmentation of the floor (Lesson P6-T3). It is the natural input to local planning, with the caution that “free” must mean observed and empty, not merely not seen to be occupied.
Semantic maps
Regions or cells labelled with a class: road, sidewalk, grass, door. They help a planner prefer or avoid surfaces, and a human check what the robot understands. They inherit the segmentation errors of Module 6.
Point clouds and voxels
The raw or lightly processed 3D points, or the occupied voxels of a 3D grid. Rich and flexible, and the right input for tasks that need shape, such as grasping or terrain analysis; heavy to store and transmit, and unstructured for planners.
Scene graphs
Objects as nodes and relations as edges: the cup is on the table, the door is part of the wall. They support reasoning and language-based instructions (Module 9), and require reliable relations, which are harder to estimate than positions.
What every interface must carry
- The frame. The coordinate frame of every position, with its convention, and the transform to the robot frame.
- The time. The time to which the data refer, so that a consumer can predict or compensate (Lesson P8-T3).
- The uncertainty. A covariance for positions, a probability for classes and occupancy. A planner that sees only a point cannot decide how much margin to leave.
- The unknown. Regions with no observation must be marked as such. “Not seen” is not “empty”.
- The provenance. Which sensors contributed and whether any were missing or in conflict, so a consumer can degrade safely.
The mathematics: occupancy updates and memory
Each cell of an occupancy grid stores the log-odds of being occupied, which turns the Bayesian update into addition:
- p
- the probability that the cell is occupied; 0.5 means unknown.
- l
- the log-odds stored for the cell: 0 for p = 0.5, positive for likely occupied, negative for likely free.
- lmeas
- the log-odds of the sensor model for this observation: positive for a hit (a return in the cell), negative for a pass-through (a beam went through the cell).
- l₀
- the prior log-odds; with a prior of 0.5 it is zero.
Repeated hits push the cell to occupied; repeated pass-throughs push it to free; contradicting observations pull it back. Clamping l to a range keeps the grid able to change when the world changes.
Memory. A 2D grid of side L at resolution h has (L/h)² cells, a 3D grid of height H has (L/h)² (H/h) voxels, each taking a few bytes. Halving the cell size multiplies a 2D grid by 4 and a 3D grid by 8.
Resolution and objects. A cell must be small enough that an object of interest spans several cells, and large enough that sensor noise does not scatter returns over many cells. A common choice is a cell of about a third of the smallest object, at least as large as the position noise.
Worked examples: an occupancy cell and a memory budget
A cell updates. The sensor model gives a hit probability 0.7, so lmeas = ln(0.7/0.3) = 0.847. The cell starts unknown (p = 0.5, l = 0). After one hit l = 0.847 and p = 0.70; after three hits l = 2.54 and p = 1/(1 + e−2.54) = 0.927. A pass-through with probability 0.3 of occupancy has lmeas = −0.847: two hits followed by two pass-throughs return the cell to l = 0, unknown. The cell is never “free” just because nothing was seen, only after pass-throughs.
Memory. A robot keeps a 100 m × 100 m local map at 0.2 m resolution in 2D: (100/0.2)² = 500² = 250,000 cells, about 250 kB at one byte per cell. At 0.1 m it is 1,000,000 cells (1 MB), four times as much. In 3D with a height of 10 m at 0.2 m, 500 × 500 × 50 = 12.5 million voxels, 12.5 MB at one byte each, and 50 times the 2D grid. Real systems use octrees or hashed voxels to store only the occupied and the observed parts.
Choosing. The table maps tasks to representations.
| Task | Needs | Representation | Interface must carry |
|---|---|---|---|
| Avoid obstacles while driving | where space is free, where objects move | free space or occupancy grid plus an object list | unknown cells, object velocity and covariance |
| Follow a person | identity and position over time | object list (tracks) | identity, covariance, “updated this cycle” flag |
| Pick a part from a bin | the shape and pose of one object | point cloud and a pose with covariance | frame, time, sensor calibration status |
| Navigate to “the red door” | places and relations | semantic map or scene graph | class probabilities and the map frame |
Why this matters for the fusion. Suppose the camera detection is 0.5 m off because of a rotated mount (Lab P8-L3). In an object list the object sits half a metre from where it is; the planner leaves a margin that may not be enough. In an occupancy grid the lidar cells are right and the camera-only class label lands on the wrong cells. The error shows differently in each form, and in each the consumer will believe it unless the interface says how far the data can be trusted.
Engineering implications and limitations
Ask the consumer first. Write down the questions the planner, the controller or the manipulator asks, and choose the representation that answers them cheaply. Several representations in parallel are normal: a grid for free space and an object list for movers.
Keep unknown separate from free. In a grid, initialise to unknown. In a drivable-area map, mark unobserved regions as not drivable unless the safety case allows otherwise. The most dangerous bug of a perception system is a hole in the data that looks like empty floor.
Use a time-decaying memory carefully. A grid that remembers forever keeps ghosts of moved objects; one that forgets fast loses objects that were briefly occluded. Clamp log-odds so that the map can change, and treat dynamic objects through the tracker (Module 7), not the grid.
Define the interface precisely. Frame, time, units, resolution, origin, uncertainty and status must be part of the message type, with tests, as for any other robot interface (Lesson P1-T3).
Degrade visibly. If a sensor is missing, in conflict or out of calibration, the representation should say so, and the planner should react: slow down, widen margins, stop. A silent degradation is the failure that matters.
Test the pipeline, not just the pieces. Run the whole chain, sensors to representation to planner, on logged scenes with injected faults (a rotated camera, a delayed lidar, a dropped sensor) and check that the robot behaves safely, as in the capstone of Module 9.
Stay honest. The labs in this module used simulated sensors with stated errors. Nothing in them shows that fused perception is safe; safety comes from calibration, timing, uncertainty handling and testing of the kind described here.
Common misconceptions
“There is one best scene representation.”
Each answers different questions. Systems usually keep a grid for space and a list for objects, and sometimes a point cloud for shape.
“No obstacle seen means free space.”
It may mean not observed, or observed badly (a dark or reflective surface). Free must be supported by observations passing through the cell.
“A map cell is true or false.”
It is a probability (a log-odds), updated by evidence, and it should be reported with its confidence to the planner.
“Once fused, the scene is trustworthy.”
It is trustworthy to the degree that the sensors were aligned in space and time and the uncertainties were honest. Without those, the representation is a confident claim that may be wrong.
Engineering takeaways
- Object lists, occupancy grids, free-space maps, semantic maps, point clouds and scene graphs each make different questions cheap; choose from the task.
- Occupancy is stored as log-odds: l ← l + lmeas − l₀; three hits at 0.7 give p = 0.93, and unknown (p = 0.5, l = 0) is distinct from free.
- A 100 m × 100 m grid at 0.2 m is 250,000 cells; the 3D version with 10 m of height is 12.5 million voxels. Halving the cell size multiplies memory by 4 (2D) or 8 (3D).
- Every interface must carry the frame, the time, the uncertainty, the unknown and the provenance.
- Fusion is only trustworthy with calibration, synchronisation, frame handling and honest uncertainties; degrade visibly and test with injected faults.
References and further reading
Papers on occupancy grids, octrees and scene graphs. The grid sizes and sensor probabilities in the examples are illustrative.
- Elfes, A. (1989). Using Occupancy Grids for Mobile Robot Perception and Navigation. Computer, 22(6).
- Thrun, S., Burgard, W. and Fox, D. (2005). Probabilistic Robotics. MIT Press: occupancy grid mapping with log-odds.
- Hornung, A., Wurm, K. M., Bennewitz, M., Stachniss, C. and Burgard, W. (2013). OctoMap: An efficient probabilistic 3D mapping framework based on octrees. Autonomous Robots.
- Armeni, I. et al. (2019). 3D Scene Graph: A Structure for Unified Semantics, 3D Space, and Camera. ICCV.
Knowledge check
Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.
Question 1
A cell has l = 0 (unknown). A sensor model gives lmeas = +0.85 for a hit and −0.85 for a pass-through. After 2 hits and 1 pass-through, what are l and p?
Explanation
l = 2 × 0.85 − 0.85 = 0.85; p = 1/(1 + e^(−0.85)) = 0.70. The cell is moderately likely occupied and not yet certain.
Question 2
A local 2D map covers 60 m × 60 m. How many cells does it have at 0.1 m resolution and at 0.05 m, and what does halving the cell size cost?
Explanation
600² = 360,000 cells at 0.1 m; 1200² = 1,440,000 at 0.05 m. Halving the cell size multiplies the 2D memory by 4 (by 8 in 3D).
Question 3
The lidar returns nothing in a region that is dark and shiny. A planner reads the grid as free there. What went wrong and what should the interface have said?
Explanation
No return was interpreted as pass-through, so the cells drifted to free, but the sensor may simply have failed on a dark or specular surface. The cells should have stayed unknown (or been flagged low-confidence) and the planner should have treated them cautiously, with the sensor’s limits recorded in the interface.
What’s next
Next, Module 9: modern learned perception, real-time constraints, and the capstone that builds an end-to-end pipeline.
Related content
Nothing below is required to finish this lesson.
- BeforeP8-T5: Uncertainty and Conflicting Observations
Fuse estimates with covariances and detect inconsistent sources.
- LabP8-L4: Fuse Simulated Observations with Uncertainty
Combine camera and LiDAR estimates by their covariances and reject conflicts.
Get notified when the next lesson and new labs are released.
One email per new lesson or lab.