The previous work in robotic map building has revolved around two themes: occupancy or certainty grids, and feature-based methods. Feature-based methods such as demonstrated by Rencken [11] works by locating features in the environment, localizing them, and then using them as known landmarks by which to localize the robot as it searches for the next landmarks. Occupancy grid mapping, as pioneered by Moravec and Elfes [9] [5] is a technique that divides the environment into a discrete grid, and assigns each grid location a value related to the probability that the location is occupied by an obstacle. We selected the occupancy grid approach due to its simplicity, robustness and adaptability to dynamic environments.
In the occupancy grid method, the robot's environment is tessellated into a discrete grid. Each grid location is assigned a value that represents the probability that it is occupied by an obstacle. Initially, all grid values are set to a 50% probability. This represents the ``unknown'' case. The grid locations that fall within the region of uncertainty about each sensed obstacle point have their values increased, while locations between the robot and the obstacle have their probabilities decreased.
Several strategies exist for updating grid location values. We selected
the simplest, which is to increment or decrement location values with
each reading. Each grid location value could vary from 
.
The increment/decrement step-size is a tunable parameter. A high value
allows the map to adapt quickly to new data, but makes it less reliable
in the presence of noise.
We chose a value of 30. This is rather high, but our stereo sensing
provides reliable, consistent data to the degree that this was acceptable.
A sample occupancy grid map is shown in Figure 7.
In this figure, black represents 100% certain obstacles while white
represents clear space.
