A map of cells

What a map has to do for a robot, why a grid is the usual answer, and what a cell costs.

U8.1MappingUniversity25 min

U7 took the map as given. Every particle predicted a reading by working out its distance to a wall the program already knew about, and the whole filter rested on that. This module asks where the wall came from.

What a map is for

A map is whatever lets the robot answer two questions:

1. Can I go there? The planner in U9 needs this, cell by cell, and it needs an answer for places the robot has never been.
2. What would I see from there? The localiser in U7 needs this, because a measurement model is a prediction of a reading from a pose.

Those two questions are what separates a map from a pile of sensor readings. A log of scans is a record of the past. A map is a thing you can ask questions of.

Two families

Feature maps hold a list of things: the corners, the tags, the walls, each with a position and a covariance. They are compact, they suit a Kalman filter, and they are the classical answer. Their weakness is that they only contain what the feature detector recognised, and they say nothing at all about the space between features.

Occupancy grids chop the world into cells and hold one number per cell: how likely it is that something is in the way there. They are stupid, they use far more memory, and they win almost every time, because they represent free space explicitly. "Nothing is there" is the statement a planner needs most and a feature map cannot make.

This module builds grids.

Resolution

A cell size is a trade, and it is not a subtle one.

The rule of thumb is a cell rather smaller than the smallest gap the robot must fit through, and rather larger than the sensor's noise. On this mat, 5 cm.

Memory grows as the square in two dimensions and as the cube in three, which is why 3D work uses octrees (the standard library is OctoMap) rather than a dense array. Knowing the name is enough for now.

Indexing

The whole of grid arithmetic is two lines. From a world position in centimetres to a cell:

col = int(x / CELL)
row = int(y / CELL)

and back to the centre of that cell:

x = col * CELL + CELL / 2
y = row * CELL + CELL / 2

Round down, not to nearest, or the cells nearest the origin end up half the size of the others. Check the bounds every time, because a reading that lands off the mat will otherwise wrap round to the far side of the array and put a wall where there is none.

from bugbot import *
connect()

CELL, W = 5.0, 40
print("a", W, "by", W, "grid is", W * W, "cells")

d = distance()
X0, Y0 = 100.0, 50.0          # where the robot is standing on the mat
hx, hy = X0, Y0 + d           # facing straight up the mat, so the hit is d further up
print("reading", round(d, 1), "lands at", (round(hx, 1), round(hy, 1)))
print("which is cell", (int(hx / CELL), int(hy / CELL)))

Run this in the simulator

The pose is assumed known here

Every task in this module gives the robot its true pose, from position() and heading(), which in the lab is the overhead camera. That is deliberate. Mapping with known poses is a solved and tidy problem, and it is the right thing to learn first.

Doing both at once, building the map while localising against the map you are building, is SLAM, and the reason it is hard is exactly that the two errors feed each other. Split the problem, learn each half, then put them back together.

Task: which cell did that reading land in?

The robot stands at (100, 50) on the mat facing straight up it. Print cells:, how many cells a 5 cm grid needs for this mat, and hit col: and hit row:, the cell the reading ahead lands in.

from bugbot import *
connect()

CELL = 5.0
W = 40

Challenges

1. Work out how much memory a 1 cm grid of this mat needs if each cell is a 4 byte float.
2. Print the centre of the hit cell in centimetres. How far is it from the point the reading actually gave?
3. At what cell size would a 20 cm doorway be at risk of closing up?