10 Spatial Coverage & Exploration · #44 of 46

Frontier Exploration

Always drive toward the edge of what you don't know

The Curiosity rover's high-resolution self-portrait on the surface of Mars, the unexplored landscape stretching out behind it. — Curiosity, parked at the edge of its known world. Every kilometre it drives is somewhere no machine has ever been. · NASA / JPL-Caltech / MSSS, public domain

Drop a robot into a building it has never seen and tell it to map the whole thing. Where should it go next?

The wrong answers are obvious: wandering randomly, or circling back over carpet it already knows. The right answer is almost too simple. Drive to the border of the unknown.

That border has a name, the frontier, and pointing your robot at it is one of those rare ideas that is both trivially intuitive and provably efficient. It is how Mars rovers decide where to crawl, how search-and-rescue robots sweep a collapsed building, and how a vacuum cleaner eventually learns the shape of your living room.

An early circular iRobot Roomba robotic vacuum cleaner sitting on a hardwood floor. — The Roomba put autonomous coverage in millions of living rooms: a low-cost robot quietly working out the shape of a floor it has never seen, the everyday face of the exploration problem. · Larry D. Moore, CC BY 4.0

The cave problem

You're spelunking with a headlamp in a pitch-black cave, sketching a map as you go. You face a choice every few steps:

Backtrack into mapped tunnels? You learn nothing; that ink is already dry.
Push into the dark? Every footstep adds new cave to the map.

Put that way, it isn't a choice at all. The only places worth visiting are the ragged edges where your lit, known space rubs against the dark. Those edges are the frontiers: the boundary cells between what you've mapped and what you haven't. Stand on a frontier and take one step, and you are guaranteed to convert unknown into known. That is the whole trick: maximize information gained per step by always heading to the edge of your map.

A small six-wheeled sidewalk delivery robot rolling along a pavement past buildings it has never mapped before. — A sidewalk delivery robot lives on the frontier: every block it rolls onto is fresh, its mapped world ending a few metres ahead. The job is to keep steering at that ragged edge where known pavement meets the unmapped street. · Phillip Pessar, CC BY 2.0

Watch the map breathe

Picture an occupancy grid filling in as a robot rolls through a floorplan, and the whole strategy plays out as a kind of inward collapse:

The map grows from the inside out. Sensed cells flip from "unknown" to "free" or "occupied," and the gray fog of the unexplored retreats from the outside in.
Frontiers live on the rim. A cell is a frontier if it is known-free but at least one neighbor is still unknown. String those cells together and you get the coastlines of your knowledge.
Each robot heads for its nearest frontier. With several robots, this fans the team out automatically: they peel off toward different coastlines instead of bunching up over the same patch.
That's why it crushes random search. A random walk re-treads old ground and leaves stubborn holes; aiming at a frontier means every move expands the map. The unknown region can only ever shrink.

The grid doing all this work has its own origin story. The occupancy grid was first proposed by Hans Moravec and Alberto Elfes in 1985, in a paper with the wonderfully blunt title "High resolution maps from wide angle sonar." Their robot had no fancy laser, just cheap, noisy sonar that returns a fat, uncertain arc rather than a clean point. The trick they introduced was to stop pretending each cell was simply "wall" or "not wall" and instead store a probability that it was occupied, then fold every new ping into that estimate. Four decades on, that same grid is the canvas the frontier is drawn on.

Greedy, and proud of it

There's an elegant honesty to frontier exploration: it is greedy. It doesn't plan a grand tour of the building. It just asks, over and over, "where can I learn the most right now?" and goes there. The sensing footprint around a candidate point overlaps some chunk of still-unknown territory; the bigger that overlap, the better the point. Drive, sense, recompute the frontiers, repeat, until there are no frontiers left, which is precisely the moment the map is complete.

The math: information gain, frontier detection, and assignment

Information gain. The value of visiting a point $p$ is how much new area its sensor would reveal: the overlap between its sensing footprint $U(p)$ and the still-unknown region:

$I(p) = \text{Area}\big(U(p) \cap \text{Unknown}\big)$

Pick the $p$ that maximizes this and you are, by definition, learning as fast as possible per move.

Frontier detection. A point $p$ is on the frontier if it is explored but borders something that isn't. Formally, some neighbor $q$ in its neighborhood $N(p)$ is still unknown:

$\exists\, q \in N(p) : \text{Explored}(p) \;\land\; \neg\,\text{Explored}(q)$

In practice this is one cheap pass over the occupancy grid: flag every known cell that touches an unknown one, then cluster the flags into frontier regions.

Assignment. With one robot you just take the nearest frontier. With a team, the simplest rule assigns robot $i$ to the frontier minimizing travel:

$f^* = \arg\min_{f \in \text{Frontiers}} \lVert p_i - f \rVert$

Naive nearest-frontier can send two robots to the same edge; smarter coordination (auction-style bidding, so no two robots claim the same frontier) fixes the redundancy and is where most modern multi-robot work lives.

fn frontier_exploration_step(agents: &mut [Agent], map: &OccupancyGrid) {
    let frontiers = detect_frontiers(map);

    for agent in agents.iter_mut() {
        if frontiers.is_empty() { continue; }

        // Find nearest frontier
        let mut nearest = None;
        let mut min_dist = f32::INFINITY;

        for &frontier in &frontiers {
            let dist = agent.pos.distance(frontier);
            if dist < min_dist {
                min_dist = dist;
                nearest = Some(frontier);
            }
        }

        if let Some(target) = nearest {
            agent.target = target;
        }
    }
}

There is a subtler version of the same question lurking underneath all of this. "Which frontier is nearest?" is the easy form. The hard form is "from everywhere I could possibly stand, which spot would teach me the most?" Roboticists call that the next-best-view problem, and it shows up far beyond mapping: a 3D scanner deciding where to point next, a drone choosing its next photo. Nearest-frontier is just a fast, good-enough answer to a question that is genuinely expensive to answer well.

Next-best-view, entropy, and why the robot's own position is part of the map

The version of exploration baked into SLAM is called Active SLAM: not just "where is the unknown space," but "which move will most reduce my total uncertainty?" The catch is that a robot building a map while lost is uncertain about two things at once, where the walls are and where it is. Driving toward a frontier reveals new space, but driving back past a familiar landmark can sharpen your own position, which retroactively cleans up the whole map. The greedy frontier rule ignores that second prize entirely.

The standard way to weigh both is to score candidate moves by how much they shrink the entropy $H$ of the robot's belief, the mathematical measure of "how spread out and unsure am I." A move's value is the expected drop:

$\text{value}(a) = H(\text{now}) - \mathbb{E}\big[H(\text{after action } a)\big]$

Pick the action with the biggest expected drop. Plain frontier-seeking is the special case where you only count entropy in the map and assume your own position is already nailed down. In sparse-sensing regimes, like a robot feeling its way by touch alone, you cannot make that assumption, and the "go re-localize" move can beat the "go explore" move outright. That is also exactly where multi-robot SLAM gets thorny: every robot is editing a shared map while unsure of where it stands relative to the others.

Key takeaways

A frontier is the boundary between mapped-free space and the unknown. Standing on one and stepping out is guaranteed to reveal something new.
Frontier exploration is greedy information maximization: always move where you'll learn the most, and the unknown region can only shrink.
Assign each robot to its nearest frontier so a team fans out instead of crowding; coordinate the assignment to avoid two robots chasing the same edge.
It beats random wandering because every move expands the map. Yamauchi's 1997 method maps a building far faster than aimless coverage.

Every robot that maps an unknown place is solving the same restless problem: there is a line between what it knows and what it doesn't, and the only way forward is to walk straight at that line until it disappears.

The frontier always recedes as you approach it, which is the point. A robot that keeps chasing the edge of its own ignorance eventually runs out of edge. And then, quietly, the map is whole.