This paper presents algorithms for building maps of road scenes using an active range and reflectance sensor and for using the maps to traverse a portion of the world already explored. Using an active sensor has some attractive advantages: It is independent of the illumination conditions, it does not require complex calibration in order to transform observed features to the vehicle’s reference frame, and it provides 3-D terrain models as well as road models. Using the map built from sensor data facilitates navigation in two respects: The vehicle may navigate faster since less perception processing is necessary, and the vehicle may follow a more accurate path since the navigation system does not rely entirely upon inaccurate visual data. We present a complete system that includes road following, map building, and map-based navigation using the ERIM laser range finder. We report on experimentation of the system both on the CMU NAVLAB and the Martin Marietta ALV.