Aspects of the disclosure provide systems and methods for recognizing an assigned passenger. For instance, dispatching instructions to pick up a passenger at a pickup location are received. The instructions include authentication information for authenticating a client computing device associated with the passenger. A vehicle is maneuvered in an autonomous driving mode towards the pickup location. The client device is then authenticated. After authentication, a set of pedestrians within a predetermined distance of the vehicle are identified from sensor information generated by a sensor of the vehicle and location information is received over a period of time from the client device. The received location information is used to estimate a velocity of the passenger. This estimated velocity is used to identify a subset of set of pedestrians that is likely to be the passenger. The vehicle is stopped to allow the passenger to enter the vehicle based on the subset.