Aspects of the disclosure relate to generating map data. For instance, data generated by a perception system of a vehicle may be received. This data corresponds to a plurality of observations including observed positions of a passenger of the vehicle as the passenger approached the vehicle at a first location. The data may be used to determine an observed distance traveled by a passenger to reach a vehicle. A road edge distance between an observed position of an observation of the plurality of observations and a nearest road edge to the observed position may be determined. An inconvenience value for the first location may be determined using the observed distance and the road edge distance. The map data is then generated using the inconvenience value.