Frontier-Based Exploration
To map a place it has never seen, a robot needs to decide where to look next. Frontier-based exploration, introduced by Brian Yamauchi in 1997, picks the boundary between explored free space and unexplored space, drives there, looks around, and repeats until no frontiers remain.
Frontiers
A frontier cell is a known free cell that touches at least one unknown cell. Neighboring frontier cells are grouped, and the robot heads for a good group, here simply the closest reachable one:
Real systems also weigh how much new area each frontier is likely to reveal and how far away it is.
What to notice
The map grows in bursts: each time the robot reaches a frontier, its sensor reveals a new patch, which creates new frontiers further on. With a short sensor range, the robot has to visit many more places. Choosing only the nearest frontier is simple but can make the robot zigzag between rooms, coming back later for corners it skipped. Exploration ends when no reachable frontiers are left.