Aspects of the disclosure relate to detecting unmapped drivable road surfaces. In one instance, sensor data captured by a sensor of an autonomous vehicle may be projected onto a grid having a plurality of cells. The plurality of cells may be classified by generating a label for each of the plurality of cells. Each label may identifies whether or not a corresponding cell contains a drivable surface. Ones of the plurality of cells may be clustered based on the labels to form a cluster of cells. An area of the cluster of cells may be compared to a map. Whether the area of the cluster of cells is an unmapped drivable road surface may be determined based on the comparison.