Frontier-based exploration
How it works
1) Occupancy grid: the robot maintains an occupancy grid with free, occupied, and unknown cells, updated from sensors (lidar, depth camera, sonar), usually alongside a SLAM system that localizes the robot. 2) Frontier detection: the algorithm finds free cells adjacent to at least one unknown cell — these are frontier cells. 3) Clustering: adjacent frontier cells are merged into connected regions (frontiers); regions that are too small are discarded as noise. 4) Goal selection: one goal is chosen among the regions — classically the centroid of the nearest region; extended variants use a cost/utility function combining distance with expected information gain. 5) Navigation: a path planner computes a route to the goal and the robot drives it, continuously updating the map. 6) Loop: on arrival (or when new data arrives) frontiers are recomputed and the cycle repeats. 7) Termination: when no frontiers remain, all reachable space has been mapped and exploration stops.
Problem solved
It answers the "where to go next?" question while mapping an unknown environment. Without such a strategy a robot would have to explore at random or know the layout in advance, which is slow and leaves gaps in the map. Frontier Exploration gives a simple, greedy heuristic that guarantees steady information gain: heading to frontiers always moves toward undiscovered space, until the reachable area is fully mapped.
Components
A grid of cells classified as free, occupied, or unknown; the base representation of the robot's knowledge of its surroundings.
Module that finds free cells adjacent to unknown ones and clusters them into frontier regions.
Rule that picks the next goal among frontier regions — classically the nearest region, in variants a cost/utility function (distance vs. information gain).
Computes a feasible route from the robot's current pose to the chosen frontier goal, avoiding obstacles.
The drive-map-recompute-frontiers cycle repeated until all frontiers disappear.
Implementation
Naively scanning the whole grid every iteration scales poorly for large, high-resolution maps.
Always heading to the nearest frontier causes unnecessary backtracking and lengthens the total exploration path.
Sensor noise and SLAM artifacts create tiny, false frontiers that waste exploration time.
Evolution
Brian Yamauchi publishes "A Frontier-Based Approach for Autonomous Exploration" (IEEE CIRA '97), defining frontiers on an occupancy grid and the greedy "go to the nearest frontier" strategy.
Yamauchi extends the approach to teams of robots sharing a common map ("Frontier-Based Exploration Using Multiple Robots", AGENTS '98), laying the groundwork for coordinated multi-robot exploration.
Hyperparameters (configurable axes)
How frontiers are found: full grid scan vs. wavefront/incremental methods (e.g., WFD, FFD).
Cell-count threshold below which a frontier region is discarded as noise.
Goal-selection criterion: nearest frontier vs. a weighted combination of distance and expected information gain.
Lidar/depth-camera range; affects discovery rate and frontier layout.
How often frontiers and the goal are recomputed while driving.
Computational complexity
Time complexity: O(C) na iterację detekcji granic. Space complexity: O(C).
Hardware requirements
A classical grid- and graph-search algorithm; it runs efficiently on a robot's standard onboard CPU without needing GPU acceleration.
Modest compute requirements let it run on a wide range of embedded platforms.