This chapter describes the map-building algorithms which were designed and implemented in this research. Figure 7.1 shows that the sonar readings (as described in Chapter 6) and knowledge of ARNE's position are combined to generate a sequence of feature-based representations and a free-space map.

The sensor model that was developed in Chapter 6 showed that positional uncertainty in the sonar returns could be decreased by grouping multiple returns from the same viewpoint. But uncertainty, especially angular uncertainty, still remains. The objective of the algorithms in this chapter is to reduce the uncertainty further and build an accurate representation of the environment.

More value can be derived from a sensor reading by examining it in the context of preexisting information about the world. This information comes from two sources; either the latest map or sensor data which has not yet contributed to the map. As an example of the first type, imagine that the current map shows that there is a wall directly in front of the robot. If a sensor reading is then obtained which is consistent with a sonar reflection from that wall, the range reading can be used to update the estimated position of the wall. The uncertainty due to beam width has been eliminated and the new range reading can be averaged with the existing knowledge to limit the impact of unpredictable errors.

Unfortunately map-building is not quite this simple. First, there is the ‘bootstrap’ problem of gathering enough initial information so that sensor readings can be matched with known objects.