Frontier-Based Exploration
Detecting
frontiers
We use evidence
grids as our spatial representation. Evidence grids are Cartesian grids
containing cells, and each cell stores the probability that the corresponding
region in space is occupied. Each time a sensor reading is obtained from the
robot's sonar, infrared, or laser rangefinders, a sensor model is used to
update the grid.
Initially all of the cells are set to the prior probability of occupancy, which is a rough estimate of the overall probability that any given location will be occupied. To detect frontiers, the occupancy probabilities are thresholded, and each cell is placed into one of three classes:
- open: having an occupancy probability < prior probability
- unknown: having an occupancy probability = prior probability
- occupied: having an occupancy probability > prior probability
A process analogous to edge
detection and region extraction in computer vision is used to find the
boundaries between open space and unknown space. Any open cell adjacent to an
unknown cell is labeled a frontier edge cell. Adjacent edge cells are grouped
into frontier regions using an image segmentation technique known as blob
coloring. Any frontier region above a certain minimum size is considered a
frontier.
The figure above shows a simplified example of frontier edge detection. The robot's location is marked with an R. Cells known to be occupied are black; cells known to be unoccupied are white; and cells whose occupancy is unknown are shaded gray. The (open) cells marked with Xs are the frontier edge cells.
The images above show an evidence grid built by a real robot in a hallway adjacent to two open doors. The left image shows the evidence grid alone. The center image shows the frontier edge segments detected in the grid. The right image shows the regions extracted using blob detection. All of the edge segments with the same color belong to the same region. The centroids of regions larger than the minimum frontier size are marked by crosshairs. Three of those frontier regions were detected. Frontier 0 and frontier 1 correspond to open doorways, while frontier 2 is the unexplored hallway.