The combined problems of sensor error modelling and the exploration of unknown environments are fundamental aspects of autonomous robotics. We consider these problems in the context of mapping an unknown closed environment with a sonar sensor. This leads to three issues at different levels of abstraction: modelling the characteristics of the sensor, dealing with the unavoidable anomalies in the data obtained, and constructing a long-term representation of the environment. An important aspect of this partitioning of the problem is that it takes us from local quantitative descriptions to large-scale symbolic ones. This paper presents algorithms for extracting obstacle contours from sonar data, that accounts for the properties of sonar modelled in our previous work. This work is then related to work on the high-level problem of constructing a map of an unknown environment. Our model of sonar range sensing for robot navigation accounts for multiple reflections of the sonar signal between transmission and reception. This gives more realistic results than previous models. This controlled data-acquisition methodology can be subsequently used to compare techniques for the interpretation of the acquired data. From this model of sonar sensing itself, a new model for inferring coherent reflecting surfaces is developed, based on an assumption of coherent smooth surfaces in the world. This is accomplished by using an ``energy based minimization'' algorithm to reject sonar measurements that are not consistent with an {\it a priori} world model. Finally, we briefly discuss a representation for large scale structure of the environment that is based only on the topological interrelation between places of interest and the paths connecting them.