This paper describes a method to build grid-based maps from sonar data.  The sonars used are the polaroid sensors which have a broad beam of 30 degrees.  The authors note that a sonar sensor tells us that the area closer than the distance reading is empty with high probability, but the sonar does not reveal where the obstacle is, only its distance and that it must lie within the beam of the sensor.  The problem this paper addresses is how to build high resolution maps from these data.

The basic approach of the paper is to interpret a sonar reading as asserting probabilities that certain areas of space are empty and other areas occupied.  This distribution for a single sonar reading is combined with prior estimates of a cell being occupied or empty. The probabilities of being empty and being occupied are maintained for each cell; a map is created from these probabilities by taking the most probable state (occupied or empty).

The authors describe several techniques to improve the raw sonar data used as input to this algorithm: discarding readings beyond a certain maximum and below a certain minimum, averaging several readings at each posititon, and clustering (i.e. recognizing clusters in a set of readings and treating each as a separate datum).

This paper also addresses matching two maps produced by this method, which can be used for robot localization.  They address several improvements to correlation (such as correlating only occupied cells and creating multi-resolution maps) which decreases the running time from ``a good fraction of an hour of Vax time'' to under a second. They also remark that blurring was necessary to make the matching process work in practice.