A vehicle can be controlled in a first autonomous mode of operation by at least navigating the vehicle based on map data. Sensor data can be obtained using one or more sensors of the vehicle. The sensor data can be indicative of an environment of the vehicle. An inadequacy in the map data can be detected by at least comparing the map data to the sensor data. In response to detecting the inadequacy in the map data, the vehicle can be controlled in a second autonomous mode of operation and a user can be prompted to switch to a manual mode of operation. The vehicle can be controlled in the second autonomous mode of operation by at least obtaining additional sensor data using the one or more sensors of the vehicle and navigating the vehicle based on the additional sensor data.