M8-T3 — Frontier Exploration

Learning objectives

After this lesson, you should be able to:

• Define a frontier on an occupancy grid and find the frontier cells and clusters.
• Score frontiers with a utility that balances expected information against the cost of the trip.
• Explain why the cost must be a path length through known space, and what committing to a target prevents.
• State when exploration is finished and list what a finished map can still get wrong.

The intuition

Walk into a dark building with a torch. The torch lights the walls and floor within a few metres. What you know is a bright island; what you do not know is everything else. The sensible next step is to walk to the edge of the bright island, where the unlit floor begins, and shine the torch there. That edge is the frontier.

The rule “go to the nearest edge” is easy to follow and works surprisingly well. It has two weaknesses. It may choose a small edge, a corner nobody cares about, over a big doorway just a little further away. And “nearest” has to mean nearest along the way you can really drive: an edge on the other side of a wall is close for a bird and far for a robot.

So the choice is a trade. Each frontier promises some new knowledge and costs some driving. The explorer picks the one with the best balance, drives there, looks, and repeats until no promising edge is left.

The mathematics

Detecting frontiers

The map has three kinds of cells: unknown, free and occupied. A cell is a frontier cell if it is free and at least one of its neighbours is unknown. Frontier cells that touch (8-connected) are grouped into a frontier, or cluster. Yamauchi (1997) found them with an edge detector on the occupancy grid and a connected-component search, and discarded frontiers too small for the robot to pass.

Scoring a frontier

f

a candidate frontier (a cell, or the centre of a cluster)

I(f)

expected information gain from looking there

D(f)

cost of reaching it: the length of the shortest path through known free cells

λ

weight that trades information against driving

Information gain is measured in several ways. The cheapest counts the unknown cells the sensor could see from f. A sounder measure uses entropy: the entropy of an occupancy probability p is

so an unknown cell (p = 0.5) is worth a full bit and a cell that is already nearly certain is worth almost nothing. The gain of a viewpoint is the expected drop in the total entropy of the cells in the sensor footprint. Two common utilities combine gain and cost:

The loop

1. Update the occupancy map from the sensors.
2. Find frontier cells, cluster them, drop clusters that are too small or unreachable.
3. Score each remaining cluster with a utility, using path length through known free cells.
4. Send the best one to the navigation stack as a goal, and keep it until it is reached, blocked or no longer a frontier.
5. Stop when no reachable frontier has enough gain.

Greedy is not optimal

Choosing the best frontier now ignores what comes after. It can leave a pocket behind and return to it later, and choosing the order of frontiers is itself a route-ordering problem (lesson M8-T1). Lookahead planners and information-theoretic planners improve on greedy choice at higher cost; for most indoor work a greedy utility with commitment is a strong baseline. With several robots the same score is used to assign different frontiers to different robots (Burgard and others, 2005).

A worked example

Three frontiers. Scout stands in a corridor of the unmapped east wing. It has found three frontier clusters. The lab’s utility is the number of unknown cells in a 5 × 5 window around the frontier (gain) minus half the path length in steps:

With the straight-line distance, F3 wins (18.5) and Scout drives to the wall, finds there is no way through, and has to go the 19 steps around through the door anyway. With the real path length, F2 wins (15.0) and F3 drops to last. This is stage 2 of lab M8-L3; the starter measures straight-line distance and the fix is a breadth-first search.

The same frontiers with the discounted form and λ = 0.1 per step: F1 14 · e^−0.4 = 9.38, F2 18 · e^−0.6 = 9.88, F3 21 · e^−1.9 = 3.14. The order is the same here (F2, F1, F3), but the discounted form punishes a far frontier much harder than the linear one. Which form is better depends on how costly Scout’s time is against the value of the map.

How much can one look reveal? A sensor with a 4-cell range sees at most the 49 cells within a disc of radius 4. A frontier with 14 unknown cells in its window is therefore a modest promise, and one with 21 is almost a full disc. At 1 bit per unknown cell, the first view of a fresh wing is worth tens of bits and the last look at a half-known doorway only a few.

Engineering implications and limitations

Commit to a target

Two frontiers of nearly equal score make a greedy explorer dither: each step changes the map slightly, the better frontier flips, and the robot oscillates between them. Keep the chosen target until it is reached, becomes unreachable, or is no longer a frontier, and only then re-evaluate. A small bonus for the current target (hysteresis) does the same thing more smoothly.

Filter noise

Sensor noise creates thin “frontiers” along walls and tiny gaps. Require a minimum cluster size (at least about the robot’s width), a minimum gain, and a minimum distance from the robot, and ignore frontiers that were just visited and found empty. Blacklist a goal that the navigation stack failed to reach so that the explorer does not retry it for ever.

Reachability decides the end

Exploration ends when no reachable frontier remains. A frontier next to unknown space seen through a window, or one enclosed by obstacles, can never be visited; counting it makes the explorer run until its battery dies (stage 3 of the lab). Add a time or battery limit, and a return-to-base when either is hit.

A finished map is not a correct map

Exploration is complete when there is nothing left to look at, not when the building is mapped. Glass looks like a gap or like nothing, a closed door looks like a wall and hides a wing, a cart in the corridor becomes a permanent obstacle. Compare the result with the building’s plan, mark doors as doors (lesson M2-T5) so that they can be revisited, and watch the pose uncertainty: exploration that drives into new space with a poor pose builds a distorted map (active SLAM, which trades exploring against keeping localization good).

Safety while exploring

The map is least reliable exactly where the robot is going. Drive slower into unknown space, keep the speed limit tied to the sensed free distance (lesson M7-T1), and treat unknown as non-traversable for planning, with the frontier as the only place it is allowed to approach.

Common misconceptions

Engineering takeaways

1. A frontier is a free cell with an unknown neighbour; connected frontier cells form a frontier cluster.
2. Score frontiers by expected information gain against the cost of the trip, for example I − λD or I·exp(−λD).
3. The cost must be the path length through known free space, not the straight-line distance.
4. Commit to a target and filter small or noisy frontiers to avoid dithering and wasted trips.
5. Stop when no reachable frontier is left, and then check the map against the building: a finished exploration is not a verified map.

References and further reading

The frontier paper, the next-best-view paper, a multi-robot extension and a recent survey on exploring while localizing.

• B. Yamauchi, “A frontier-based approach for autonomous exploration”, IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA), 1997.
• H. H. González-Baños and J.-C. Latombe, “Navigation strategies for exploring indoor environments”, International Journal of Robotics Research 21(10–11), 2002.
• W. Burgard, M. Moors, C. Stachniss and F. E. Schneider, “Coordinated multi-robot exploration”, IEEE Transactions on Robotics 21(3), 2005.
• C. Stachniss, G. Grisetti and W. Burgard, “Information gain-based exploration using Rao-Blackwellized particle filters”, Robotics: Science and Systems, 2005.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: when several robots share the floor, they have to plan together: multi-robot path finding.

Related content

Nothing below is required to finish this lesson.

• Before
  M8-T2: Coverage Path Planning

  Cover a floor with boustrophedon sweeps and handle obstacles, overlap and turn cost.

• Lab
  M8-L3: Explore by Frontiers

  Map an unknown wing by always driving to the best frontier, and stop when nothing is left.