Frontiers

The edge between what is known and what is not, and why a map with holes is still useful.

U8.6MappingUniversity30 min

An occupancy grid holds three kinds of cell, and the third one is the useful one.

A feature map cannot say "unknown", because absence from the list means both "not there" and "never looked". The grid distinguishes them, and that distinction is what lets a robot explore on purpose instead of wandering.

The definition

A frontier cell is a free cell with at least one unknown neighbour.

That is the whole idea, from Yamauchi in 1997, and it has survived because it is exactly right. A frontier is a place the robot can reach, since it is free, that borders on something it has not seen. Driving to a frontier is guaranteed to produce new information. When there are no frontiers left and the robot can reach everywhere, the map is finished, and the robot knows it is finished, which is a surprisingly hard property to get any other way.

for every free cell:
    if any of its four neighbours is unknown:
        it is a frontier cell

Four neighbours or eight is a matter of taste. Four gives slightly cleaner boundaries.

From cells to targets

Individual frontier cells come in thousands. The usual pipeline:

1. Group adjacent frontier cells into connected regions, with a flood fill.
2. Discard regions smaller than the robot, because a two cell frontier is usually sensor noise rather than a doorway.
3. Score each remaining region and drive to the best one.

The scoring is where the judgement lives. The classic is nearest first, which is cheap and behaves reasonably. Better schemes trade distance against expected gain:

value = expected new cells - lambda * path length

where the expected gain can be estimated by ray casting from the candidate with unknown treated as free and counting what the beams would cross. Weighting also against turning is worth doing, since a robot that reverses direction repeatedly explores slowly even when each individual choice was locally optimal.

Watching exploration saturate

from bugbot import *
import math
connect()

CELL, W = 5.0, 40
L_OCC, L_FREE, L_MAX, FAR = 0.85, -0.4, 8.0, 170.0
START_X, START_Y = 100.0, 100.0
grid = [0.0] * (W * W)

def bump(x, y, amount):
    c, r = int(x / CELL), int(y / CELL)
    if 0 <= c < W and 0 <= r < W:
        grid[r * W + c] = max(-L_MAX, min(L_MAX, grid[r * W + c] + amount))

drive(0, 0, 30)
for tick in range(90):
    px, py = position()
    x, y, h = START_X + px, START_Y + py, heading()
    for a, d in scan():
        th = math.radians(h + a)
        sx, sy = math.sin(th), math.cos(th)
        r = 0.0
        while r < min(d, FAR) - CELL:
            bump(x + r * sx, y + r * sy, L_FREE)
            r += CELL / 2
        if d < FAR:
            bump(x + d * sx, y + d * sy, L_OCC)
    plot("known", sum(1 for v in grid if abs(v) > 1.0) / float(W * W))
    wait(0.1)
stop()
print("explored", round(sum(1 for v in grid if abs(v) > 1.0) / float(W * W), 3))

Run this in the simulator

The known line climbs while the robot sweeps fresh bearings and then goes flat. Flat means the robot has seen everything it can see from this spot, and the only way to learn more is to move. A robot that watched that curve could decide for itself when to stop turning.

Shadows

Everything behind an obstacle is unknown, and the shape of that shadow is what makes exploration interesting. From one viewpoint a small post hides a wedge that widens with distance, so a tiny object can conceal a large region. Two viewpoints a little apart resolve nearly all of it, which is why exploration strategies that move a short distance sideways often beat ones that drive a long way forward.

When it goes wrong

• Frontiers that never close. A thin sliver of unknown along a wall, from a beam that just clipped it. The robot drives there, learns nothing, and comes back. Discard small regions.
• Ping-pong. Two frontiers of equal value on opposite sides, and the robot alternates. Add hysteresis: keep the current target until it is reached or it disappears.
• The map says finished, the room is not. Unknown space that is walled off from everywhere the robot can reach. The map is right and the robot cannot help it.

Task: what have I not seen?

Turn on the spot, building a grid as you go. Plot known, then print explored:, the fraction of cells that are no longer unknown, and frontier:, how many free cells have an unknown neighbour.

from bugbot import *
import math
connect()

CELL, W = 5.0, 40
L_OCC, L_FREE, L_MAX, FAR = 0.85, -0.4, 8.0, 170.0
START_X, START_Y = 100.0, 100.0
grid = [0.0] * (W * W)

Challenges

1. Group your frontier cells into connected regions with a flood fill and print how many regions there are.
2. Print the centre of the nearest region bigger than three cells.
3. Work out how wide the shadow of the post is at the far wall, and check it against your map.