Disclosed herein are methods and apparatus for controlling autonomous vehicles utilizing maps that include visibility information. A map is stored at a computing device associated with a vehicle. The vehicle is configured to operate in an autonomous mode that supports a plurality of driving behaviors. The map includes information about a plurality of roads, a plurality of features, and visibility information for at least a first feature in the plurality of features. The computing device queries the map for visibility information for the first feature at a first position. The computing device, in response to querying the map, receives the visibility information for the first feature at the first position. The computing device selects a driving behavior for the vehicle based on the visibility information. The computing device controls the vehicle in accordance with the selected driving behavior.