Frontier-Based Exploration


Simplified Example

In the figure to the left, open space is white; space occupied by obstacles is black; and unknown space is gray. The robot is represented by the black circle, and the robot's line-of-sight is represented by the blue line. The red zone represents the frontier at the boundary between the open space seen by the robot and the hidden territory beyond.

The robot has moved to the first frontier. The robot can now see into the rooms on the right side of the image, so these are added into the mapped territory. The robot discovers a new wall (black) on the left side of the image, and this wall blocks the space (gray) in the lower right corner - so a new frontier (red) exists between the mapped territory and the hidden space.

The robot has moved to the second frontier. It can now see into the space in the lower right corner and add it to the map. At this point, the robot has mapped all of the space in this simple environment, so the exploration is complete.

The real world is much more complex than the environment above. Typically, the robot will be able to see multiple frontiers from any given viewpoint. In that case, the robot tries to plan a path from its current position to the nearest frontier. If no such path exists, then the robot tries to plan a path to the second nearest frontier, and so on. Since the robot's map contains all previously visited locations, the robot can always navigate back to explore frontiers that it has previously seen, but not yet visited.

Frontier-Based Exploration