Map representations

A map is a model of the environment that a robot can use to localize itself, plan paths and reason about what it will meet. There is no single best map. A floor-cleaning robot, a warehouse robot, an underwater vehicle and a self-driving car need very different maps, because they use them for different purposes and have different sensors, memory and computing budgets. Choosing the representation is one of the first and most consequential design decisions in a mobile robot system, because it determines which localization and SLAM algorithms are possible, how much memory the map takes, how well it handles change, and how easy it is for people to inspect and edit. This lesson surveys the main families: metric grids, point clouds, voxel and octree maps, signed distance fields, feature (landmark) maps, topological maps and semantic maps.

What a map must do

Before choosing a representation, list what the map is for. For localization, the map must let the robot predict what its sensors should see from any candidate pose, so that measurements can be scored. For path planning, it must say which places are free, which are occupied and which are unknown. For human interaction, it should carry labels people understand, such as 'loading dock 3' or 'kitchen'. For long-term operation, it must be updatable as furniture moves, pallets come and go, and doors open and close. A good map is also compact enough to store and share, and its accuracy should match the task: a warehouse robot needs centimeters, a delivery drone meters.

Occupancy grids

An occupancy grid divides the plane into square cells of fixed size, typically 2 to 10 cm, and stores for each cell the probability that it is occupied. Unknown cells start at 0.5. As the robot moves, each laser beam lowers the probability of the cells it passes through and raises the probability of the cell where it ends. Hans Moravec and Alberto Elfes introduced the idea in the mid-1980s, and it remains the most widely used map in indoor robotics: ROS map_server stores grids as a PGM image plus a YAML file giving the resolution, origin and thresholds, and the Nav2 navigation stack plans on them. Lesson 4 derives the update in detail.

Grids are simple, handle arbitrary shapes, distinguish free space from unknown space, and give constant-time lookup. Their weakness is memory: a 2-D grid's size grows with the area covered divided by the square of the resolution, whether or not anything interesting is there, and a 3-D grid grows with the cube.

Point clouds

A point cloud is simply a set of 3-D points, usually from a lidar or depth camera, registered into a common frame. It preserves fine geometry and is the natural input to scan matching (lesson 9) and to inspection and surveying, where the cloud itself is the product. But a point cloud says nothing about free space: the absence of points in a region could mean it is empty, or simply that the sensor never looked there. Clouds are also large, millions of points for a single building floor, and are usually downsampled with a voxel filter (keeping one point per cube of a chosen size) before use, as in ROB-330 lesson 8. Many lidar SLAM systems keep their map as a set of keyframe clouds or a downsampled global cloud, and localize new scans against it with ICP or NDT.

Voxel grids and octrees

For robots that move in 3-D, such as drones, or manipulators that reach into shelves, a 2-D grid is not enough. A voxel grid extends the occupancy grid to 3-D cubes, but memory grows with the cube of the resolution. Octrees solve this by subdividing space only where needed: each node covers a cube, and only cubes that contain something are split into eight children. Large empty or uniformly occupied regions stay as single big nodes. OctoMap (Hornung and colleagues, 2013) is the standard probabilistic octree for robotics: it stores log-odds occupancy in each leaf, distinguishes free, occupied and unknown space, supports multi-resolution queries, and is widely used with ROS for 3-D collision checking and exploration.

Signed distance fields

A signed distance field (SDF) stores, in each voxel, the distance to the nearest surface: positive in free space, negative inside objects and zero exactly on the surface. Truncated SDFs (TSDFs) store the distance only near surfaces and are the representation behind KinectFusion (Newcombe and colleagues, 2011), which fused depth camera frames into smooth, accurate surfaces in real time. Euclidean signed distance fields (ESDFs) store the distance everywhere and are prized by planners, because the distance to the nearest obstacle, and its gradient, come straight from a lookup, which is exactly what a trajectory optimizer needs to push a path away from obstacles. Voxblox (2017) and its successors build ESDFs incrementally for drones and mobile manipulators.

Feature maps

A feature map, or landmark map, keeps only a list of distinctive landmarks with their estimated positions and uncertainties: corners and poles detected in laser scans, visual keypoints with descriptors, fiducial markers, or reflectors on a wall. It throws away most of the sensor data, which makes it compact and lets the estimator track the correlations between landmarks explicitly. EKF-SLAM (lesson 6) and FastSLAM (lesson 7) were built on feature maps, and visual SLAM systems such as ORB-SLAM (lesson 10) keep a map of 3-D keypoints. The cost is that the robot depends on detecting and recognizing the same landmarks reliably, which requires the environment to have enough of them and the data association to be right.

Topological and hybrid maps

A topological map is a graph: nodes are distinctive places (rooms, junctions, doors, docking stations) and edges are routes between them, labeled with how to travel. It captures the structure people use when giving directions (go down the corridor, turn left at the lift) and scales to very large areas, because its size grows with the number of places, not with the area. It cannot by itself support precise obstacle avoidance. Many systems are therefore hybrid: a topological graph for long-range routing whose nodes each hold a small local metric map. Multi-floor buildings are naturally hybrid, with one grid per floor connected through lift and stair nodes.

Semantic maps

A semantic map adds meaning: object classes and instances (chairs, shelves, pallets, people), area labels (aisle 12, kitchen, charging zone) and relations (the mug is on the table). Semantic labels come from the learned perception of ROB-330 lessons 9 and 10, projected into the map. They let a robot accept commands such as 'fetch the red bin from shelf B4', reason about which objects are likely to move, and ignore dynamic objects when localizing. Open-vocabulary 3-D scene graphs built with vision-language models were a fast-moving research area at the time of writing. Semantic maps inherit the errors of perception, so production systems usually keep a reliable geometric map underneath and treat semantics as an annotation layer that can be corrected.

import numpy as np
# Compare memory for three representations of the same 40 m x 30 m floor
W, H, res = 40.0, 30.0, 0.05
cells = int(W / res) * int(H / res)
grid_bytes = cells * 1                        # one byte per occupancy cell
wall_len = 2 * (W + H) + 6 * 20.0             # outer walls plus six 20 m racks
pts = int(wall_len / 0.01) * 16               # 1 cm spacing, 16 lidar rings hitting walls
cloud_bytes = pts * 3 * 4                     # x, y, z as 32-bit floats
landmarks = 400                               # corners, pillars, reflectors
lm_bytes = landmarks * (2 * 8 + 3 * 8)        # 2-D position + 2x2 covariance (3 unique)
for name, b in [("occupancy grid", grid_bytes), ("raw point cloud", cloud_bytes),
                ("landmark map", lm_bytes)]:
    print("%-16s %10.2f MB" % (name, b / 1e6))

occupancy grid         0.48 MB
raw point cloud        4.99 MB
landmark map           0.02 MB

Choosing a representation

In practice the choice follows from the sensors, the task and the scale. A 2-D lidar indoors points to an occupancy grid for both localization and planning, which is why that combination is the default in ROS 2 Nav2. A 3-D lidar outdoors often means a point-cloud or voxel map for localization plus a 2-D or 2.5-D cost map (an elevation map storing the height of the ground in each cell) for driving. A camera-only robot naturally builds a feature map for localization and may add a depth-based grid for obstacles. A drone in a cluttered building needs a 3-D occupancy or distance field. Very large areas call for hybrid topological-metric maps, or for splitting the map into tiles or submaps that are loaded as the robot moves. Most real systems keep several layers, built from the same SLAM output, each serving a different consumer.