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:
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.
