Methods, systems, and apparatus, including computer programs encoded on non-transitory computer storage medium(s), are directed to improving completeness of map information and data related to maps created through sensor data. Map completeness can be improved by determining object completeness and coverage completeness of a generated map and reducing amount of unknown areas of the generated map.