How should a mobile robot explore its environment in order to build a high-quality world model as efficiently as possible? We address this question through experimentation with a sonar-equipped mobile robot. The robot is taken to be a delivery robot, such as could be used in an office, hospital or home. Its objective is to execute efficient collision-free paths between user-specified locations. A grid-based free-space map is generated for this purpose. This map is derived from a feature-based map, built using techniques similar to those of (Leonard and Durrant-Whyte 1992).