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.