Frontier-based Exploration

A robot repeatedly drives toward the boundary between known open space and unknown territory, mapping as it goes.

Proposed by Brian Yamauchi of the U.S. Naval Research Laboratory in 1997 (IEEE CIRA conference), this method answers: in an unfamiliar environment, where should the robot go next to gain the most new information? The approach finds ‘frontiers’ on an occupancy grid map (space divided into cells labeled free, occupied, or unknown) — free cells adjacent to unknown cells — clusters neighboring frontier cells into regions, picks one (the original paper picks the nearest) and navigates there, updates the map with sensor readings on arrival, then finds new frontiers, repeating until no frontiers remain. It's simple, makes no assumptions about wall orientation or room shape, and remains a common baseline for autonomous mapping and object-goal navigation in mobile robotics today; later work has replaced ‘nearest’ with information gain, or had a vision-language model score frontiers (as in VLFM).

ExampleA quadruped robot placed inside an office building with no pre-existing map builds an occupancy grid with lidar SLAM while repeatedly driving to the nearest frontier; once every hallway and room has been explored, no frontiers remain and exploration ends.

Also called

Frontier Exploration

Related

Active Exploration · Occupancy Grid Map · Simultaneous Localization and Mapping · Object-Goal Navigation · VLFM · Next-Best-View Planning

Sources

Yamauchi, A Frontier-Based Approach for Autonomous Exploration (IEEE CIRA 1997)