Patent Description:
Autonomous vehicles, for instance, vehicles that do not require a human driver, can be used to aid in the transport of passengers or items from one location to another. Such vehicles may operate in a fully autonomous mode where passengers may provide some initial input, such as a pickup or drop-off location, and the vehicle maneuvers itself to that location.

When a person (or user) wants to be physically transported between two locations via a vehicle, they may use any number of transportation services. To date, these services typically involve a human driver who is given dispatch instructions to a location to pick up the user. In many cases, the location may have a queue for picking up or dropping off passengers. For example, a human driver would likely know that locations such as airports and train stations typically have a queue for picking up or dropping off passengers. Further, a human driver typically knows from experience the common practices and rules of such queues, and could intuitively respond to queuing behaviors of other vehicles. As such, a human driver may be able to determine how to best reduce inconvenience to other drivers in and around the queue. This is not readily achievable in the case of autonomous vehicles which do not have a human driver.

<CIT> discloses generating a speed plan for an autonomous vehicle. As an example, a vehicle is maneuvered in an autonomous driving mode along a route using pre-stored map information. This information identifies a plurality of keep clear regions where the vehicle should not stop but can drive through in the autonomous driving mode. Each keep clear region of the plurality of keep clear regions is associated with a priority value. A subset of the plurality of keep clear regions is identified based on the route. A speed plan for stopping the vehicle is generated based on the priority values associated with the keep clear regions of the subset. The speed plan identifies a location for stopping the vehicle. The speed plan is used to stop the vehicle in the location.

The matter for protection is set out in the appended claims.

The present disclosure provides a method of queuing by an autonomous vehicle according to claim <NUM>.

Determining that a queue exists at the location may be based on traffic patterns observed from the sensor data. Determining that a queue exists at the location may be based on changes in traffic patterns observed using a time series of the sensor data. Determining that a queue exists at the location may be based on signs detected using the sensor data, wherein the signs are within a predetermined distance of the traffic patterns.

The method may further comprise determining, by the one or more processors based on the sensor data, whether the vehicle would block traffic if the vehicle joins the queue; wherein determining whether to join the queue may be based on whether the vehicle would block traffic if the vehicle joins vehicle joins the queue. The method may further comprise determining, by the one or more processors based on the sensor data, whether the vehicle would interfere with loading or unloading by another vehicle if the vehicle joins the queue; wherein determining whether to join the queue may be based on whether the vehicle would interfere with the loading or unloading by another vehicle if the vehicle joins the queue.

The method may further comprise determining, by the one or more processors based on the sensor data, a designated spot in the queue for loading and unloading passengers, and controlling, by the one or more processors, the vehicle to move along in the queue to reach the designated spot. The method may further comprise determining, by the one or more processors based on the sensor data, that loading or unloading outside the designated spot is tolerated by other vehicles in the queue, and controlling, by the one or more processors, the vehicle to perform pickup or drop-off outside the designated spot. The method may further comprise determining, by the one or more processors based on the sensor data, that the queue has multiple lanes; and controlling, by the one or more processors, the vehicle to shift to a lane closest to the designated spot.

The method may further comprise predicting, by the one or more processors based on the sensor data, an expected wait-time for the vehicle to reach the designated spot in the queue; and sending, by the one or more processors, a message to a client computing device of the passenger indicating that the vehicle is waiting in the queue to pick up the passenger at the designated spot, the message including the expected wait-time. The method may further comprise predicting, by the one or more processors based on the sensor data, an expected wait-time for the vehicle to reach the designated spot in the queue; and providing, by the one or more processors based on the sensor data, a message to the passenger to wait for the vehicle to reach the designated spot before getting out of the vehicle, the message including the expected wait-time.

The method may further comprise predicting, by the one or more processors based on the sensor data, an expected wait-time for the vehicle to reach the designated spot in the queue; and predicting, by the one or more processors, an estimated arrival time for a passenger requesting pickup at the location to reach the designated spot; wherein determining whether to join the queue may be based on a comparison between the expected wait-time and the estimated arrival time. The method may further comprise determining, by the one or more processors based on the comparison between the expected wait-time and the estimated arrival time, to wait in a waiting area prior to joining the queue; and controlling, by the one or more processors, the vehicle to park in the waiting area prior to joining the queue.

The method may further comprise determining, by the one or more processors upon reaching the designated spot in the queue, an amount of time to wait for the passenger at the designated spot based on a level of difficulty for exiting and re-joining the queue; and controlling, by the one or more processors, the vehicle to exit the queue after waiting the amount of time. The method may further comprise determining, by the one or more processors upon reaching the designated spot in the queue, an amount of time to wait for the passenger at the designated spot based on whether the vehicle is blocking traffic at the designated spot; and controlling, by the one or more processors, the vehicle to exit the queue after waiting the amount of time.

The method may further comprise determining, by the one or more processors upon reaching the designated spot in the queue, an estimated arrival time for the passenger to reach the designated spot; based on the estimated arrival time, controlling the vehicle to exit the queue; predicting, by the one or more processors, an expected wait-time to reach the designated spot after exiting the queue; determining, by the one or more processors to return to the queue after exiting the queue based on a comparison between the estimated arrival time and the expected wait-time; and controlling, by the one or more processors, the vehicle to drive to return to the queue after exiting the queue. The method may further comprise sending, by the one or more processors, a message to a user device of the passenger indicating that the vehicle is returning to an end of the queue, the message including the expected wait-time. The method may further comprise determining, by the one or more processors based on the comparison between the estimated arrival time and the expected wait-time, to wait in a waiting area prior to returning to the queue; and controlling, by the one or more processors, the vehicle to park in the waiting area prior to returning to the queue.

The method may further comprise determining, by the one or more processors that the location has a plurality of designated pickup or drop-off areas; selecting, by the one or more processors, one of the designated pickup or drop-off areas; and controlling, by the one or more processors, the vehicle to drive to the selected designated pickup or drop-off area. Selecting one of the designated pickup or drop-off areas may be based on feedback received from a user device, the feedback associated with the passenger identifying a preferred spot for pickup or drop-off.

The technology relates to an autonomous vehicle's behaviors for queuing into a line of vehicles in order to perform a pickup or drop-off of goods and/or passengers. As noted above, autonomous vehicles do not have intuition to recognize and respond to queuing behaviors, and thus likely to behave in a manner that inconvenience or annoy other road users. For instance, if there is a designated spot in the queue (such as front of the queue) for picking up passengers, it may cause inconvenience or annoyance to the passenger and other road users if the autonomous vehicle performs the pickup at another spot in the queue (such as the middle of the queue). For another instance, if the vehicle waits too long at the designated pickup spot in the queue, or re-queues many times before the passenger arrives, this may slow down the queue and therefore inconvenience other vehicles in the queue. Such inappropriate behaviors by the autonomous vehicle may cause traffic congestion or even unsafe conditions for other road users, and thus need to be addressed.

One option is to have an autonomous vehicle request assistance from remote operators. For instance, the remote operators may provide instructions to the vehicle to indicate whether and how the autonomous vehicle should enter a queue to wait for a passenger. Once in the queue, a remote operator may indicate where in the queue should the vehicle pickup the passenger, and if the passenger is not there, whether the vehicle should continue to wait in the queue or leave and re-queue, etc. The remote operator may do so by reviewing the vehicle's surroundings and then direct the vehicle based on considerations for the passenger and other road users. However, this back-and-forth with the remote operator can take time, which can cause further annoyance and inconvenience to the passenger and other road users. To reduce or even eliminate the need for the autonomous vehicles to call a remote operator in such situations, the vehicle's computing devices may determine various circumstances of the queue and control the vehicle accordingly.

In this regard, the vehicle may receive a request to pickup or drop off a passenger at a location. In response, the vehicle controls itself in order to maneuver to the location using map information (for example including GPS coordinates). While doing so, the vehicle's computer receives sensor data from the perception system in order to detect, identify and respond to objects including road users (vehicles, bicycles, and passengers), barriers, and signs.

The vehicle's computing devices may determine whether the location is likely to have a queue. For example, the vehicle's computing devices may determine, based on map information indicating that the location is an airport or a stadium with a scheduled sporting event, that the location is likely to have a queue for passenger pickup and/or drop-off. If so, the vehicle's computing devices may activate processes to determine if a queue actually exists at the time, and to determine appropriate queuing behaviors for the queue.

If the vehicle's computing devices determine that the location is likely to have a queue, as the vehicle approaches the location, the vehicle's computing devices uses sensor data from the perception system to determine whether there is a queue for pickups or drop-offs at the location. For instance, by identifying traffic patterns and changes in these traffic patterns over time from the sensor data, the vehicle's computing devices may then determine whether a queue actually exists at the location. In order to allow the vehicle's computing devices to quickly assess these traffic patterns, a model may be trained to receive the sensor data described above as input, and output whether any traffic pattern is identified as a queue. The model may be trained by using sensor data generated by a vehicle's perception system with labeled instances of when a queue is identified.

Once a queue for pickups or drop-offs is identified at the location, the vehicle's computing devices may determine whether to join the queue. For instance, the vehicle's computing devices may determine based on sensor data whether entering the queue would inconvenience other road users, such as blocking a sideway or roadway. For another instance, in particular for pickups, the vehicle's computing devices may determine an expected wait-time of the queue and an expected arrival time for the passenger, and determine whether to enter the queue so as to avoid inconveniencing the other road users, such as avoiding the need to re-queue. As such, the sensor data may be used to track progresses of vehicles in the queue. The aforementioned model may be further trained to receive the sensor data as input, and output an expected wait-time.

Once it is determined that entering the queue would not inconvenience other road users, the vehicle's computing devices control the vehicle in order to join the queue. For example, the vehicle's computing devices may control the vehicle to drive towards the queue, stop behind the last vehicle in the queue, and/or move along with the queue.

In some instances, based on the sensor data, the vehicle's computing devices may also determine whether the queue has a designated spot for loading and unloading passengers. For example, the sensor data may indicate that vehicles in a queue momentarily stops at the front of the queue before speeding off, based on which the vehicle's computing devices may determine that the designated loading or unloading spot is the front of the queue. The vehicle's computing devices may control the vehicle to move along with the queue until the vehicle reaches the designated spot, and then control the vehicle to stop at the designated spot to perform pickup or drop-off. In this regard, the aforementioned model may be further trained to output a location of the designated spot. Further, the expected wait-time of the queue may be the time required for the vehicle to reach the designated spot in the queue.

If the passenger requesting pickup is at or near the designated spot when the vehicle arrives, the vehicle's computing devices may pick up the passenger at the designated spot. Alternatively, the vehicle's computing devices may allow the passenger to enter the vehicle before reaching the designated spot, for example based on determining whether loading or unloading outside the designated spot is tolerated.

If the passenger is not at or near the designated spot in the queue when the vehicle arrives, the vehicle's computing devices may determine an amount of time to wait for the passenger at the designated spot, and exit the queue after waiting the amount of time. The vehicle's computing devices may determine the amount of time to wait based on the map information, such as the type of the location. The vehicle's computing devices may also determine the amount of time to wait based on the sensor data, such as whether the vehicle would block traffic. In some examples, the vehicle's computing devices may determine an updated estimated arrival time for the passenger to reach the designated spot, and determine to exit the queue before waiting the amount of time. The vehicle's computing devices may control the vehicle to exit the queue and re-queue at a later time.

If the vehicle exits the queue before the passenger arrives, for example based on the updated estimated arrival time, the vehicle's computing devices may determine an expected wait-time to re-queue and reach the designated spot. Further, based on a comparison between the updated estimated arrival time and the expected wait-time to re-queue, the vehicle's computing devices may determine when to re-queue.

The vehicle's computing devices may be configured to communicate with the passenger. For example, to keep the passenger apprised of the vehicle's whereabouts while the vehicle waits in the queue, the vehicle's computing devices may be configured to send a message to a user device of the passenger indicating that the vehicle is waiting in the queue and the expected wait-time. For another example, the vehicle's computing devices may send a message to the passenger when the passenger should enter or exit the vehicle, such as when fully stopped a designated spot for loading or unloading. For yet another example, the vehicle's computing devices may send a message to the user device of the passenger indicating that the vehicle is returning to the end of the queue along with the expected wait-time to re-queue.

The features described above may enable autonomous vehicles to make independent determinations when queues exist for picking up and dropping off passengers at a location. This may reduce or even eliminate the need for remote operators to make these decisions while also reducing the time it takes for the vehicle to react to such situations. At the same time, by allowing the vehicle to automatically determine nuanced circumstances or rules of the queue, such as whether there is a designated spot for loading or unloading in the queue and whether the queue is fast-moving or slow-moving, the vehicle may be more responsive to its environment and less likely to block, inconvenience, and in some cases, annoy, the passenger or other road users.

As shown in <FIG>, a vehicle <NUM> in accordance with one aspect of the disclosure includes various components. While certain aspects of the disclosure are particularly useful in connection with specific types of vehicles, the vehicle may be any type of vehicle including, but not limited to, cars, trucks, motorcycles, busses, recreational vehicles, etc. The vehicle may have one or more computing devices, such as computing device <NUM> containing one or more processors <NUM>, memory <NUM> and other components typically present in general purpose computing devices.

As an example, data <NUM> of memory <NUM> may store predefined scenarios. A given scenario may identify a set of scenario requirements including a type of object, a range of locations of the object relative to the vehicle, as well as other factors such as whether the autonomous vehicle is able to maneuver around the object, whether the object is using a turn signal, the condition of a traffic light relevant to the current location of the object, whether the object is approaching a stop sign, etc. The requirements may include discrete values, such as "right turn signal is on" or "in a right turn only lane", or ranges of values such as "having an heading that is oriented at an angle that is <NUM> to <NUM> degrees offset from a current path of vehicle <NUM>. " In some examples, the predetermined scenarios may include similar information for multiple objects.

The one or more processor <NUM> may be any conventional processors, such as commercially available CPUs. Alternatively, the one or more processors may be a dedicated device such as an ASIC or other hardware-based processor. Although <FIG> functionally illustrates the processor, memory, and other elements of computing device <NUM> as being within the same block, it will be understood by those of ordinary skill in the art that the processor, computing device, or memory may actually include multiple processors, computing devices, or memories that may or may not be stored within the same physical housing. As an example, internal electronic display <NUM> may be controlled by a dedicated computing device having its own processor or central processing unit (CPU), memory, etc. which may interface with the computing device <NUM> via a high-bandwidth or other network connection. In some examples, this computing device may be a user interface computing device which can communicate with a user's client device. Similarly, the memory may be a hard drive or other storage media located in a housing different from that of computing device <NUM>. Accordingly, references to a processor or computing device will be understood to include references to a collection of processors or computing devices or memories that may or may not operate in parallel.

Computing device <NUM> may all of the components normally used in connection with a computing device such as the processor and memory described above as well as a user input <NUM> (e.g., a mouse, keyboard, touch screen and/or microphone) and various electronic displays (e.g., a monitor having a screen or any other electrical device that is operable to display information). In this example, the vehicle includes an internal electronic display <NUM> as well as one or more speakers <NUM> to provide information or audio visual experiences. In this regard, internal electronic display <NUM> may be located within a cabin of vehicle <NUM> and may be used by computing device <NUM> to provide information to passengers within the vehicle <NUM>. In addition to internal speakers, the one or more speakers <NUM> may include external speakers that are arranged at various locations on the vehicle in order to provide audible notifications to objects external to the vehicle <NUM>.

In one example, computing device <NUM> may be an autonomous driving computing system incorporated into vehicle <NUM>. The autonomous driving computing system may capable of communicating with various components of the vehicle. For example, computing device <NUM> may be in communication with various systems of vehicle <NUM>, such as deceleration system <NUM> (for controlling braking of the vehicle), acceleration system <NUM> (for controlling acceleration of the vehicle), steering system <NUM> (for controlling the orientation of the wheels and direction of the vehicle), signaling system <NUM> (for controlling turn signals), navigation system <NUM> (for navigating the vehicle to a location or around objects), positioning system <NUM> (for determining the position of the vehicle), perception system <NUM> (for detecting objects in the vehicle's environment), and power system <NUM> (for example, a battery and/or gas or diesel powered engine) in order to control the movement, speed, etc. of vehicle <NUM> in accordance with the instructions <NUM> of memory <NUM> in an autonomous driving mode which does not require or need continuous or periodic input from a passenger of the vehicle. Again, although these systems are shown as external to computing device <NUM>, in actuality, these systems may also be incorporated into computing device <NUM>, again as an autonomous driving computing system for controlling vehicle <NUM>.

The computing device <NUM> may control the direction and speed of the vehicle by controlling various components. By way of example, computing device <NUM> may navigate the vehicle to a drop-off location completely autonomously using data from the map information and navigation system <NUM>. Computing devices <NUM> may use the positioning system <NUM> to determine the vehicle's location and perception system <NUM> to detect and respond to objects when needed to reach the location safely. In order to do so, computing devices <NUM> may cause the vehicle to accelerate (e.g., by increasing fuel or other energy provided to the engine by acceleration system <NUM>), decelerate (e.g., by decreasing the fuel supplied to the engine, changing gears, and/or by applying brakes by deceleration system <NUM>), change direction (e.g., by turning the front or rear wheels of vehicle <NUM> by steering system <NUM>), and signal such changes (e.g., by lighting turn signals of signaling system <NUM>). Thus, the acceleration system <NUM> and deceleration system <NUM> may be a part of a drivetrain that includes various components between an engine of the vehicle and the wheels of the vehicle. Again, by controlling these systems, computing devices <NUM> may also control the drivetrain of the vehicle in order to maneuver the vehicle autonomously.

As an example, computing device <NUM> may interact with deceleration system <NUM> and acceleration system <NUM> in order to control the speed of the vehicle. Similarly, steering system <NUM> may be used by computing device <NUM> in order to control the direction of vehicle <NUM>. For example, if vehicle <NUM> configured for use on a road, such as a car or truck, the steering system may include components to control the angle of wheels to turn the vehicle. Signaling system <NUM> may be used by computing device <NUM> in order to signal the vehicle's intent to other drivers or vehicles, for example, by lighting turn signals or brake lights when needed.

Navigation system <NUM> may be used by computing device <NUM> in order to determine and follow a route to a location. In this regard, the navigation system <NUM> and/or data <NUM> may store map information, e.g., highly detailed maps that computing devices <NUM> can use to navigate or control the vehicle. As an example, these maps may identify the shape and elevation of roadways, lane markers, intersections, crosswalks, speed limits, traffic signal lights, buildings, signs, real time or historical traffic information, vegetation, or other such objects and information. The lane markers may include features such as solid or broken double or single lane lines, solid or broken lane lines, reflectors, etc. A given lane may be associated with left and right lane lines or other lane markers that define the boundary of the lane. Thus, most lanes may be bounded by a left edge of one lane line and a right edge of another lane line. As noted above, the map information may store known traffic or congestion information and/or and transit schedules (train, bus, etc.) from a particular pickup location at similar times in the past. This information may even be updated in real time by information received by the computing devices <NUM>.

<FIG> is an example of map information <NUM> for a location <NUM>. For this example, map information <NUM> depicts a portion of the map information that includes information identifying a type of the location <NUM>. For example, the type of the location <NUM> may be airport, train station, stadium, school, church, hospital, apartment building, house, etc. In this regard, the type of the location <NUM> may be collected from administrative records, such as county records, or manually labeled by a human operator after reviewing aerial images.

The map information <NUM> may include real-time information (not shown) about the location <NUM>. For example, if the location <NUM> is an airport, the real-time information may include flight schedules. For another example, if the location <NUM> is a stadium, the real-time information may include event schedules. In this regard, the map information <NUM> may be flagged or otherwise linked with an online database, for instance at storage system <NUM> discussed further below, where such real-time information is available. As an alternative, once a vehicle's computing devices have identified a queue, the vehicle's computing devices may automatically request real time information from a remote server computing device and/or database. In addition or alternatively, a server computing device, such as server computing devices <NUM>, may automatically send the real-time information based on information received from vehicle <NUM> about the vehicle's current location. In this regard, the vehicle may automatically receive the real-time information when the vehicle is within a certain area and/or a certain distance of a location likely to have a queue. In some instances, this information may be stored with the map information <NUM>.

In addition, the map information <NUM> may include information about infrastructure available around the location <NUM>. As shown, the map information <NUM> includes the shape, location, and other characteristics of road <NUM> and road <NUM> around the location <NUM>. For example, the map information <NUM> may include an indication that road <NUM> has two way traffic, and road <NUM> has one way traffic. For another example, map information <NUM> may include lane markers or lane lines <NUM> and <NUM> for road <NUM>. The lane lines may also define various lanes <NUM>, <NUM>, <NUM>. As alternative to lane lines or markers, lanes may also be inferred by the width of a road. The map information <NUM> may also include information that identifies the direction of traffic and speed limits for each lane as well as information that allows the computing devices <NUM> to determine whether the vehicle has the right of way to complete a particular type of maneuver (i.e. complete a turn, cross a lane of traffic or intersection, etc.).

In addition to these features, the map information <NUM> may further include signs and markings on the roads at or near the location <NUM> with various characteristics and different semantic meanings. As shown, map information <NUM> includes sign <NUM> with the text "LOAD" which may indicate a location for loading passengers and/or cargo. Map information <NUM> also includes marking <NUM> in lane <NUM>, with the text "LOAD ONLY" which may indicate a location for loading passengers and/or cargo with respect to text in the roadway. Map information <NUM> also includes marking for pedestrian crosswalk <NUM> in lanes <NUM>, <NUM>, and <NUM>. The map information <NUM> may additionally include other features such as curbs, waterways, vegetation, etc..

The map information <NUM> may also store predetermined stopping areas including pickup and drop-off areas. Pickup areas may refer to areas where the autonomous vehicle stops to wait to pick up a passenger for a trip. Drop-off areas may refer to areas where the autonomous vehicle stops to allow for a passenger to exit the vehicle after a trip. In this regard, such areas may be hand-selected by a human operator or learned by a computing device over time. For example, the pickup and/or drop-off areas are typically at or near an entrance of a location. In this regard, map information <NUM> may additionally store locations of entrances and/or exits for the location <NUM>, such as entrance <NUM>. As shown, a portion of lane <NUM>, being closest to entrance <NUM> of location <NUM> and/or associated with the aforementioned "LOAD ONLY" marking <NUM> in lane <NUM>, may be labeled as a pickup and/or drop-off area for location <NUM>.

Other stopping locations may include waiting areas, such as those where the vehicle can stop and wait for a passenger to arrive. For example, for a location that is a point of interest such as airport or school, there may be a waiting area for the location. As shown, parking lot <NUM>, being behind the location <NUM>, may be labeled as a waiting area. In this regard, such waiting areas may be selected through some manual or automated analysis of the characteristics of each location.

The map information may further include GPS coordinates (not shown) of the location <NUM>, and various other infrastructure at the location <NUM> as described above, such as roads <NUM> and <NUM>, lanes <NUM>, <NUM>, <NUM>, and parking lot <NUM>.

Although the detailed map information is depicted herein as an image-based map, the map information need not be entirely image based (for example, raster). For example, the detailed map information may include one or more roadgraphs or graph networks of information such as roads, lanes, intersections, and the connections between these features. Each feature may be stored as graph data and may be associated with information such as a geographic location and whether or not it is linked to other related features, for example, a stop sign may be linked to a road and an intersection, etc. In some examples, the associated data may include grid-based indices of a roadgraph to allow for efficient lookup of certain roadgraph features.

The perception system <NUM> also includes one or more components for detecting objects external to the vehicle such as other vehicles, obstacles in the roadway, traffic signals, signs, trees, etc. For example, the perception system <NUM> may include one or more LIDAR sensors, sonar devices, radar units, cameras and/or any other detection devices that record data which may be processed by computing devices <NUM>. The sensors of the perception system may detect objects and their characteristics such as location, orientation, size, shape, type (for instance, vehicle, pedestrian, bicyclist, etc.), heading, and speed of movement, etc. The raw data from the sensors and/or the aforementioned characteristics can be quantified or arranged into a descriptive function, vector, and or bounding box and sent for further processing to the computing devices <NUM> periodically and continuously as it is generated by the perception system <NUM>. As discussed in further detail below, computing devices <NUM> may use the positioning system <NUM> to determine the vehicle's location and perception system <NUM> to detect and respond to objects when needed to reach the location safely.

For instance, <FIG> is an example external view of vehicle <NUM>. In this example, roof-top housing <NUM> and dome housing <NUM> may include a LIDAR sensor as well as various cameras and radar units. In addition, housing <NUM> located at the front end of vehicle <NUM> and housings <NUM>, <NUM> on the driver's and passenger's sides of the vehicle may each store a LIDAR sensor. For example, housing <NUM> is located in front of driver door <NUM>. Vehicle <NUM> also includes housings <NUM>, <NUM> for radar units and/or cameras also located on the roof of vehicle <NUM>. Additional radar units and cameras (not shown) may be located at the front and rear ends of vehicle <NUM> and/or on other positions along the roof or roof-top housing <NUM>. Vehicle <NUM> also includes many features of a typical passenger vehicle such as doors <NUM>, <NUM>, wheels <NUM>, <NUM>, etc..

Once a nearby object is detected, computing devices <NUM> and/or perception system <NUM> may determine the object's type, for example, a traffic cone, pedestrian, a vehicle (such as a passenger car, truck, bus, etc.), bicycle, etc. Objects may be identified by various models which may consider various characteristics of the detected objects, such as the size of an object, the speed of the object (bicycles do not tend to go faster than <NUM> miles per hour or slower than <NUM> miles per hour), the heat coming from the bicycle (bicycles tend to have rider that emit heat from their bodies), etc. In addition, the object may be classified based on specific attributes of the object, such as information contained on a license plate, bumper sticker, or logos that appear on the vehicle.

In one example, computing devices <NUM> may be operable to identify queuing behaviors of other vehicles from sensor data provided by the perception system <NUM>, for example, by looking for and identifying a line of vehicles stopped in a lane near an entrance or exit of a point of interest. However, memory <NUM> may also store behavior models trained to recognize queuing behaviors. The behavior models may include machine learning models, such as a deep neural network. A model may be trained by using sensor data generated by perception system <NUM> with labeled instances of when a queue is identified. These labels may be generated, for instance, based on the aforementioned determinations made by remote operators. The sensor data may include all of the data generated by the perception system <NUM>, or more streamlined information, such as the pose, velocity, acceleration and similar data for each road user detected by the perception system over some period of time.

As described in detail below with respect to example situations, such labeled instances of queues may include images of a line of vehicles formed in a lane next to a point of interest, or next to certain signs or markings. To further discriminate between traffic patterns, the behavior models may be trained with time-sequenced series of data. Such time correlation may allow the behavior models to recognize changes in traffic patterns over time, and based on such changes, distinguish queuing behaviors from other behaviors that may resemble queuing behavior in a snapshot (such as a traffic jam).

Optionally, the behavior models may be trained to use sensor data from perception system <NUM> as input, and output additional information about an identified queue. For example, as described in detail below with respect to example situations, the behavior models may be trained to recognize a designated spot in the queue for loading and/or unloading passengers. For another example, also described in detail below with respect to example situations, the behavior models may be trained to predict an expected wait-time to reach the designated spot in the queue.

The one or more computing devices <NUM> of vehicle <NUM> may also receive or transfer information to and from other computing devices, for instance using wireless network connections <NUM>. The wireless network connections may include, for instance, BLUETOOTH (R), Bluetooth LE, LTE, cellular, near field communications, etc. and various combinations of the foregoing. <FIG> and <FIG> are pictorial and functional diagrams, respectively, of an example system <NUM> that includes a plurality of computing devices <NUM>, <NUM>, <NUM>, <NUM> and a storage system <NUM> connected via a network <NUM>. System <NUM> also includes vehicle <NUM>, and vehicle 100A which may be configured similarly to vehicle <NUM>. Although only a few vehicles and computing devices are depicted for simplicity, a typical system may include significantly more.

The network <NUM>, and intervening nodes, may include various configurations and protocols including short range communication protocols such as BLUETOOTH (R), Bluetooth LE, the Internet, World Wide Web, intranets, virtual private networks, wide area networks, local networks, private networks using communication protocols proprietary to one or more companies, Ethernet, WiFi and HTTP, and various combinations of the foregoing.

In one example, one or more computing devices <NUM> may include a server having a plurality of computing devices, e.g., a load balanced server farm, that exchange information with different nodes of a network for the purpose of receiving, processing and transmitting the data to and from other computing devices. For instance, one or more computing devices <NUM> may include one or more server computing devices that are capable of communicating with one or more computing devices <NUM> of vehicle <NUM> or a similar computing device of vehicle 100A as well as client computing devices <NUM>, <NUM>, <NUM> via the network <NUM>. For example, vehicles <NUM> and 100A may be a part of a fleet of vehicles that can be dispatched by server computing devices to various locations. In this regard, the vehicles of the fleet may periodically send the server computing devices location information provided by the vehicle's respective positioning systems and the one or more server computing devices may track the locations of the vehicles.

In addition, server computing devices <NUM> may use network <NUM> to transmit and present information to a user, such as user <NUM>, <NUM>, <NUM> on a display, such as displays <NUM>, <NUM>, <NUM> of computing devices <NUM>, <NUM>, <NUM>. In this regard, computing devices <NUM>, <NUM>, <NUM> may be considered client computing devices.

As shown in <FIG>, each client computing device <NUM>, <NUM>, <NUM> may be a personal computing device intended for use by a user <NUM>, <NUM>, <NUM>, and have all of the components normally used in connection with a personal computing device including a one or more processors (e.g., a central processing unit (CPU)), memory (e.g., RAM and internal hard drives) storing data and instructions, a display such as displays <NUM>, <NUM>, <NUM> (e.g., a monitor having a screen, a touch-screen, a projector, a television, or other device that is operable to display information), and user input devices <NUM>, <NUM>, <NUM> (e.g., a mouse, keyboard, touchscreen or microphone). A user, such as user <NUM>, <NUM>, <NUM>, may send information, such as pickup or drop-off requests, to server computing devices <NUM>, using user input devices <NUM>, <NUM>, <NUM> of computing devices <NUM>, <NUM>, <NUM>. The client computing devices may also include a camera for recording video streams, speakers, a network interface device, and all of the components used for connecting these elements to one another.

Although the client computing devices <NUM>, <NUM>, and <NUM> may each comprise a full-sized personal computing device, they may alternatively comprise mobile computing devices capable of wirelessly exchanging data with a server over a network such as the Internet. By way of example only, client computing device <NUM> may be a mobile phone or a device such as a wireless-enabled PDA, a tablet PC, a wearable computing device or system, or a netbook that is capable of obtaining information via the Internet or other networks. In another example, client computing device <NUM> may be a wearable computing system, shown as a wrist watch in <FIG>. As an example the user may input information using a small keyboard, a keypad, microphone, using visual signals with a camera, or a touch screen.

In some examples, client computing device <NUM> may be remote operator work station used by an administrator to provide remote operator services to users such as users <NUM> and <NUM>. For example, a remote operator <NUM> may use the remote operator work station <NUM> to communicate via a telephone call or audio connection with users through their respective client computing devices and/or vehicles <NUM> or 100A in order to ensure the safe operation of vehicles <NUM> and 100A and the safety of the users as described in further detail below. Although only a single remote operator work station <NUM> is shown in <FIG> and <FIG>, any number of such work stations may be included in a typical system.

Storage system <NUM> may store various types of information as described in more detail below. This information may be retrieved or otherwise accessed by a server computing device, such as one or more server computing devices <NUM>, in order to perform some or all of the features described herein. For example, the information may include user account information such as credentials (e.g., a username and password as in the case of a traditional single-factor authentication as well as other types of credentials typically used in multi-factor authentications such as random identifiers, biometrics, etc.) that can be used to identify a user to the one or more server computing devices. The user account information may also include personal information such as the user's name, contact information, identifying information of the user's client computing device (or devices if multiple devices are used with the same user account), as well as age information, health information, and user history information about how long it has taken the user to enter or exit vehicles in the past as discussed below.

The storage system <NUM> may also store routing data for generating and evaluating routes between locations. For example, the routing information may be used to estimate how long it would take a vehicle at a first location to reach a second location. In this regard, the routing information may include map information, not necessarily as particular as the detailed map information described above, but including roads, as well as information about those road such as direction (one way, two way, etc.), orientation (North, South, etc.), speed limits, as well as traffic information identifying expected traffic conditions, etc..

The storage system <NUM> may also store information which can be provided to client computing devices for display to a user. For instance, the storage system <NUM> may store predetermined distance information for determining an area at which a vehicle is likely to stop for a given pickup or drop-off location. The storage system <NUM> may also store graphics, icons, and other items which may be displayed to a user as discussed below.

As with memory <NUM>, storage system <NUM> can be of any type of computerized storage capable of storing information accessible by the server computing devices <NUM>, such as a hard-drive, memory card, ROM, RAM, DVD, CD-ROM, write-capable, and read-only memories. In addition, storage system <NUM> may include a distributed storage system where data is stored on a plurality of different storage devices which may be physically located at the same or different geographic locations. Storage system <NUM> may be connected to the computing devices via the network <NUM> as shown in <FIG> and/or may be directly connected to or incorporated into any of the computing devices <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, etc..

In addition to the systems described above and illustrated in the figures, various operations will now be described.

In one aspect, a user may download an application for requesting a vehicle to a client computing device. For example, users <NUM> and <NUM> may download the application via a link in an email, directly from a website, or an application store to client computing devices <NUM> and <NUM>. For example, client computing device may transmit a request for the application over the network, for example, to one or more server computing devices <NUM>, and in response, receive the application. The application may be installed locally at the client computing device.

The user may then use his or her client computing device to access the application and request a vehicle. As an example, a user such as user <NUM> may use client computing device <NUM> to send a request to one or more server computing devices <NUM> for a vehicle. As part of this, the user may identify a pickup location, a drop-off location, and, in some cases, one or more intermediate stopping locations anywhere within a service area where a vehicle can stop.

These pickup and drop-off locations may be predefined (e.g., specific addresses of residences or points of interest. ) or may simply be any location within a service area of the vehicles (e.g., defined by GPS coordinates). As an example, a pickup location can be defaulted to the current location of the user's client computing device, or can be input by the user at the user's client computing device. For instance, the user may enter an address or other location information or select a location on a map to select a pickup location. Once the user has selected one or more of a pickup and/or drop-off locations, such as location <NUM>, the client computing device <NUM> may send the location or locations to one or more server computing devices of the centralized dispatching system.

In response, one or more server computing devices, such as server computing device <NUM>, may select a vehicle, such as vehicle <NUM>, for instance based on availability and proximity to the user. The server computing device <NUM> may then assign the user as the passenger for the vehicle <NUM>, dispatch the selected vehicle (here vehicle <NUM>) to pick up the assigned passenger. This may include by providing computing devices <NUM> with the pickup and/or drop-off locations specified by the assigned passenger as well as information that can be used by the computing devices <NUM> of vehicle <NUM> to authenticate the client computing device, such as client computing device <NUM>.

<FIG> is an example flow diagram <NUM> that may be performed by one or more processors, such as one or more processors <NUM> of computing devices <NUM>. For example, processors <NUM> of computing devices <NUM> may receive data and make various determinations as shown in flow diagram <NUM>, and control the vehicle <NUM> based on these determinations. Referring to <FIG>, in block <NUM>, a request to pick up or drop off a passenger at a pickup and drop off spot at a location is received. In this regard, the computing device <NUM> may receive a request to pick up or drop of the passenger from the server computing device <NUM> as discussed above.

Thereafter, the computing devices <NUM> may maneuver vehicle <NUM> towards the pickup location and, after picking up the passenger, towards the drop-off location. While doing so, the computing devices <NUM> may receive sensor data from the perception system <NUM> in order to detect, identify and respond to objects including road users (vehicles, bicycles, and passengers), barriers, and signs.

In some instances, though not shown, computing devices <NUM> may determine based on the map information <NUM>, that the location <NUM> has a plurality of designated pickup or drop-off areas, and control the vehicle <NUM> to maneuver to one of the designated pickup or drop-off areas. For example, an airport may have multiple terminals and multiple doors at each terminal for pickup and/or drop-off. In such instances, computing devices <NUM> may select one of the designated pickup and/or drop-off areas. For example, computing devices <NUM> may send a message to the user device of the passenger asking the passenger for a preferred spot for pickup or drop-off at the location. Upon receiving user feedback, such as a message from the passenger indicating the preferred spot for pickup or drop-off, computing devices <NUM> may determine, based on the map information <NUM>, which of the designated pickup or drop-off areas is closest to the preferred spot for pickup or drop-off. Computing devices <NUM> may then control the vehicle <NUM> to drive to the designated pickup or drop-off area closest to the preferred spot for pickup or drop-off.

Referring back to <FIG>, in block <NUM>, it is determined whether the pickup or drop-off location is likely to have a queue for passenger pickup or drop-off. For instance, computing devices <NUM> may determine whether the location is likely to have a queue based on a type of the location. For example, if location <NUM> is selected as a pickup or drop-off location, computing devices <NUM> may determine, based on map information <NUM> indicating that the location <NUM> is an airport, that the location <NUM> is likely to have a queue for passenger pickup or drop-off. For another example, computing devices <NUM> may determine, based on map information indicating that the location <NUM> is a house, that the location <NUM> is not likely to have a queue for passenger pickup or drop-off.

For another instance, computing devices <NUM> may determine whether the location is likely to have a queue further based on real-time information, such as event schedules obtained from an online database. For example, computing devices <NUM> may determine, based on map information <NUM> indicating that the location <NUM> is a stadium with a scheduled sporting event at or around the time of the pickup or drop-off, that the location <NUM> is likely to have a queue for passenger pickup or drop-off. For another example, computing devices <NUM> may determine, based on map information <NUM> indicating that the location <NUM> is a church with no scheduled service at or around the time of the pickup or drop-off, that the location <NUM> is not likely to have a queue for passenger pickup and/or drop-off.

Referring back to <FIG>, when it is determined that the location is likely to have a queue for passenger pickup or drop-off, in block <NUM>, it is determined using sensor data from a perception system whether there is a queue at a chosen pickup or drop-off spot at the location. For example, as vehicle <NUM> approaches the location <NUM>, computing devices <NUM> may use sensor data from the perception system <NUM> to determine whether there is actually a queue for pickups or drop-offs at the location <NUM>. For example, computing devices <NUM> may receive sensor data from perception system <NUM> at the location <NUM>, input these sensor data into the behavior models described above, and receives output from the behavior models indicating whether a queue exists at the location <NUM>. As illustrated by the example situations below, the determination may be based on identifying traffic patterns, changes in these traffic patterns over time, signs, and/or markings. In this regard, there may be more than one pick-up and drop off spot for a given location, and these pick-up or drop-off spots may be predetermined (such as the pick-up and/or drop off areas described above), indicated by signage, and/or formed spontaneously, such as when other vehicles begin displaying queueing behaviors for a pick-up or drop-off spot not previously designated as such in the map information or otherwise.

<FIG> and <FIG> illustrate example situations 700A and 700B for determining whether a queue exists at a location that is likely to have a queue for passenger pickup or drop-off. Various features in <FIG> and <FIG> may generally correspond to the shape, location, and other characteristics of features shown in map information <NUM> of <FIG>, and labeled as such. Additional features in <FIG> and <FIG>, including various road users and other objects, are described in detail below. Although these examples are useful for demonstration purposes, they should not be considered limiting.

Referring to <FIG>, situation 700A shows the environment surrounding location <NUM> as vehicle <NUM> approaches location <NUM> in lane <NUM>. In addition to the features already described with respect to <FIG>, Situation 700A shows various road users, including vehicles <NUM>, 100F, and <NUM> in lane <NUM>, vehicles 100A-E in lane <NUM>, vehicle <NUM> in lane <NUM>, and vehicle 100I parked in parking lot <NUM>; as well as various pedestrians, such as users <NUM> and <NUM>.

Computing devices <NUM> receive sensor data from perception system <NUM>, which detects vehicles 100A, 100B, 100C, 100D, and 100E in lane <NUM>. Based on this sensor data, computing devices <NUM> may identify a traffic pattern, for instance, that vehicles 100A-E form a line or a queue <NUM>, and conclude that a pickup or drop-off queue exists at location <NUM>. For another example, computing devices <NUM> may further determine that lane <NUM> is the closest lane to entrance <NUM> of the location <NUM>, and conclude that the queue <NUM> formed in lane <NUM> is a pickup or drop-off queue. For still another example, computing devices <NUM> may further determine that queue <NUM> exists even though there is nothing blocking vehicle 100A in lane <NUM>, the first vehicle in queue <NUM>, and conclude that queue <NUM> is a pickup or drop-off queue.

Alternatively or additionally, changes in traffic pattern may be used to determine whether a queue exists. Referring to <FIG>, example situation 700B again shows the environment surrounding location <NUM>, but after some time has lapsed since situation 700A was captured by the perception system <NUM>. For instance, 700B may be captured a fraction of a second or a few seconds after situation 700A. As shown, each of vehicles <NUM>, 100A-H have changed their positions in 700B compared to 700A. Further, during the lapsed time, computing devices <NUM> may continue to receive sensor data from perception system <NUM>, which may capture intermediate movements of vehicles 100A-H between the situations 700A and 700B.

Based on the sensor data captured during the lapsed time, computing devices <NUM> may determine changes in the traffic pattern, including changes to queue <NUM>. For instance, computing devices <NUM> may determine that, during the lapsed time, vehicles 100A-100E moved very slowly during this time, despite there being nothing (i.e. no objects such as cones, pedestrians, other vehicles, etc.) blocking vehicle 100A. For another instance, computing devices <NUM> may determine that, after coming to a complete stop at the front <NUM> of queue <NUM>, and a brief pause, vehicle 100A leaves queue <NUM> and drives away. For still another instance, computing devices <NUM> may determine that, after vehicle 100A left the queue <NUM>, vehicle 100B drives up and stops where vehicle 100A had previously stopped, and vehicles 100C-E follows vehicle 100B in queue <NUM>. For yet another example, computing devices <NUM> may determine that, once vehicles 100C-E moves up in queue <NUM>, vehicle 100F in lane <NUM> switches to lane <NUM> and stops behind vehicle 100E, the last vehicle in queue <NUM>, instead of continuing to drive in lane <NUM>, which has fewer vehicles (and thus likely move quicker). Thus, based on identifying such changes in traffic patterns, computing devices <NUM> may distinguish a line of vehicles formed as a pickup or drop-off queue from a line of vehicles formed as a result of a traffic jam, or other traffic situations.

Additionally or alternatively, computing devices <NUM> may determine whether a queue exists based on signs and/or markings detected from sensor data, and in some instances, whether those signs are within a predetermined distance of a traffic pattern, such as <NUM> feet or more or less. For example, as shown in <FIG>, computing devices <NUM> may determine, based on sensor data indicating that a sign <NUM> with text "LOAD" is located on the sidewalk next to lane <NUM> and that queue <NUM> formed by vehicles 100A-E in the lane <NUM> is a queue for pickup or drop-off. For another example, computing devices <NUM> may determine, based on sensor data indicating that markings <NUM> with text "LOAD ONLY" is located in lane <NUM> and that queue <NUM> formed by vehicles 100A-E in the lane <NUM> is a queue for pickup or drop-off. In other examples, other texts or markings (such as a sign with a person carrying luggage, colors, text and/or shapes in lanes, etch. ) may be determined by computing devices <NUM> as indicating a queue for pickup or drop-off. Thus, based on detecting signs and/or markings, computing devices <NUM> may distinguish a line of vehicles formed as a pickup or drop-off queue from a line of vehicles formed as a result of a traffic jam, or other traffic situations.

Once a pickup or drop-off queue is identified, referring back to <FIG>, in block <NUM>, it is determined based on the sensor data whether to join the queue to avoid inconveniencing other road users. Inconveniencing other users may include, for example, blocking vehicle or pedestrian traffic, interfering with loading or unloading of other vehicles, slowing down the queue (such as by re-queueing).

For example, <FIG> shows an example situation <NUM> where computing devices <NUM> determine whether to join the queue. <FIG> shows many of the same features of <FIG>, but with differences as discussed further below. As shown, vehicle <NUM> is the last vehicle in queue <NUM> and is positioned such that it is partially blocking crosswalk <NUM>. If vehicle <NUM> enters queue <NUM> behind vehicle <NUM>, vehicle <NUM> would block the entire crosswalk <NUM>, thereby inconveniencing pedestrians who want to cross the crosswalk <NUM>, such as pedestrian <NUM>. Further, if vehicle <NUM> enters queue <NUM> behind vehicle <NUM>, vehicle <NUM> would also partially block road <NUM>, thereby inconveniencing vehicles that are exiting that road, such as vehicle <NUM>. For another example, as shown, vehicle <NUM> is in the process of loading or unloading pedestrian <NUM>, if vehicle <NUM> enters queue <NUM> behind vehicle <NUM>, pedestrian <NUM> may be inconvenienced when attempting to open a trunk of vehicle <NUM>. These examples are shown as inconvenience factors <NUM> and <NUM>, based on which adecision <NUM> is made not to enter the queue <NUM>.

If computing devices <NUM> determine not to enter the queue <NUM> to avoid inconveniencing these other road users, computing devices <NUM> may control the vehicle <NUM> in order to wait before entering the queue <NUM>. For example, computing devices <NUM> may control vehicle <NUM> to wait in lane <NUM>. While waiting, computing devices <NUM> may continue to use sensor data in order to determine whether and when to join the queue <NUM>. For example, computing devices <NUM> may determine based on sensor data that vehicle <NUM> moved forward in queue <NUM>, or finished loading or unloading, and then determine that vehicle <NUM> can join queue <NUM> without inconveniencing other road users.

<FIG> shows another example situation <NUM>, in particular for pickups, where computing devices <NUM> determine whether to join the queue. <FIG> shows many of the same features of <FIG>, but with differences as discussed further below. In situation <NUM>, computing devices <NUM> determine an expected wait-time of the queue <NUM>, based on which computing devices <NUM> may determine whether to enter the queue <NUM>.

As such, computing devices <NUM> may determine that the queue <NUM> has a designated spot <NUM> for loading and unloading passengers. For example, if the sensor data indicate that vehicles 100A-F in the queue <NUM> momentarily stops at the front of the queue <NUM> before speeding off, computing devices <NUM> may determine based on this sensor data that the designated loading or unloading spot <NUM> is at the front of the queue <NUM>. For another example, computing devices <NUM> may determine based on the sensor data including signs and markings such as the sign <NUM> with text "LOAD," that the designated spot <NUM> is where the sign <NUM> is located. For yet another example, the sensor data may indicate barriers <NUM> are positioned along the lane <NUM> where queue <NUM> is formed, the computing devices <NUM> may determine where the barrier <NUM> opens is the designated spot <NUM> for loading or unloading passengers.

Computing devices <NUM> may then predict, based on the sensor data, an expected wait-time for the vehicle <NUM> to reach the designated spot <NUM> in the queue <NUM>. In some examples, computing devices <NUM> may track the progress of vehicles in the queue using the sensor data. For instance, based on the sensor data, computing devices <NUM> may determine a total number of vehicles in the queue <NUM>, calculate an average pause time at the designated spot <NUM> for the vehicles in the queue <NUM>, and then multiply the average pause time by the total number of vehicles in the queue <NUM>. For example, as shown, computing devices <NUM> may determine that the queue <NUM> has a total of <NUM> vehicles. As shown, computing devices <NUM> may also determine that vehicle 100A had a pause time <NUM> of <NUM> seconds, and vehicle 100B had a pause time <NUM> of <NUM> seconds, and estimate that the average pause time for vehicles in queue <NUM> is approximately <NUM> seconds. Computing devices <NUM> may then multiply <NUM> seconds by <NUM> vehicles in the queue <NUM>, and estimate that, once entered into queue <NUM>, vehicle <NUM> would have an expected wait-time <NUM> of approximately <NUM> seconds, or about one and a half minutes.

In other examples, computing devices <NUM> may use predetermined pause times for different types of locations. For instance, the computing devices <NUM> may use a predetermined pause time of <NUM> seconds for loading or unloading passengers with luggage when the map information <NUM> indicate that the location <NUM> is an airport, and then multiply the predetermined pause time by the total number of vehicles in the queue <NUM> to determine the predicted wait-time. In this regard, the predetermined pause times for different types of locations may be set based on historical or statistical data, for example such data and predetermined pause times may be stored on server computing devices <NUM> and accessible by the computing devices <NUM>.

Computing devices <NUM> may also predict an estimated arrival time for the passenger to reach the designated spot <NUM>. This estimated arrival time may be based on any number of different factors, including for instance, general information about the pickup location, this specific passenger or similarly situated passengers, event specific information, etc. For instance, given the current location, for example GPS location, of a passenger's client computing devices, the arrival time may be estimated in part based on the distance from the current location to the vehicle and an estimated walking speed for a person or a model of how long it would take a passenger to walk the distance. In addition or alternatively, the estimated arrival time may be based on the passenger's specific history with arrival times, the history of all passengers at the location, the history of passengers with similar characteristics at this or any location, etc. In this regard, estimated arrival times may be estimated by clustering or pooling data. For example, passengers who are typically late, are more likely to be late. As another instance, the server computing devices <NUM> may monitor event information such as flight, train and/or event status, and such information could be used to estimate an arrival time. In addition, regarding the airport example, whether the passenger is likely to have to pick up checked baggage (it may be more likely if the passenger is or was on an international flight) as well as how long it typically takes this or other similarly situated passengers to reach the queue. As another instance, the estimated arrival time may be determined based on the type of event that has occurred or is occurring at of the type of location of the pickup location. For example, during sporting events at stadiums, passengers may take additional time to exit a stadium. As another example, at a grocery store, passengers may tend to have more variance, whereas for picking up passengers after school may be more consistent. By comparing the expected wait-time of the queue with the estimated arrival time for the passenger requesting pickup, computing devices <NUM> may determine whether the vehicle <NUM> should enter the queue <NUM>, wait a while somewhere else before queuing, or go to an alternative pickup spot.

In instances where the estimated arrival time of the passenger is greater than the expected wait-time, computing devices <NUM> may determine not to enter the queue <NUM> to reduce wait-times of other vehicles in the queue <NUM> and to avoid the need for re-queueing. In some examples, if the estimated arrival time is greater than the expected wait-time by a first predetermined threshold difference, computing devices <NUM> may control the vehicle <NUM> to park in a waiting area. The first predetermined threshold difference may be selected as any appropriate duration, for example such as <NUM> seconds, <NUM> minute, <NUM> minutes, etc. For example, as shown, computing devices <NUM> may determine that, user <NUM>, who requested the pickup, has an estimated arrival time <NUM> of <NUM> minutes to reach the designated spot <NUM> (for example based on GPS coordinates of client computing device <NUM> or a message from user <NUM>), and determine that the <NUM> minutes estimated arrival time <NUM> is greater than the expected wait-time <NUM> of <NUM> seconds by more than the first threshold difference of <NUM> minute.

In this regard, computing devices <NUM> may determine, based on the map information <NUM> about the location <NUM>, where the appropriate waiting area is at this location <NUM>. For example, as shown, computing devices <NUM> may determine based on map information <NUM>, that parking lot <NUM> is the appropriate waiting area <NUM> for the location <NUM>. Continuing from the example above, computing devices <NUM> may therefore make a decision <NUM> not to enter the queue <NUM> and to wait in parking lot <NUM> before queuing.

In instances where the estimated arrival time of the passenger is less or equal to the expected wait-time in the queue, or not greater than the expected wait-time by the first predetermined threshold difference, the computing devices <NUM> may determine to enter the queue immediately. This way, the vehicle <NUM> does not incur extra wait-time for the passenger. For example, computing devices <NUM> may determine that, user <NUM>, who requested the pickup, is <NUM> minutes away from the designated spot <NUM> (for example based on GPS coordinates of client computing device <NUM> or a message from user <NUM>), and determine that <NUM> minutes is not greater than the expected wait-time of <NUM> seconds by more than the first threshold difference of <NUM> minute. Computing devices <NUM> may thus determine to enter the queue <NUM>.

Referring back to <FIG>, in block <NUM>, the vehicle is controlled to join the queue based on the determination to join the queue. Referring to <FIG>, for example, computing devices <NUM> may control the vehicle <NUM> to drive towards the queue <NUM>, such as switching from lane <NUM> into lane <NUM>. Computing devices <NUM> may determine based on sensor data where the queue <NUM> ends, and control the vehicle <NUM> to stop behind the last vehicle in the queue <NUM>, which is vehicle 100F.

Once vehicle <NUM> enters the queue <NUM>, computing devices <NUM> may control the vehicle <NUM> to move along with vehicles in queue <NUM>, for example by following the vehicle 100F in front of it. Computing devices <NUM> may control the vehicle <NUM> to move along in queue <NUM> until the vehicle reaches the designated spot <NUM>, and then control the vehicle <NUM> to stop at the designated spot <NUM> to perform pickup or drop-off. In some examples, though not shown, where the queue includes multiple lanes, computing devices <NUM> may control the vehicle <NUM> to shift to the lane closest to the pickup or drop-off location before reaching the designated spot <NUM>.

For drop-offs and for pickups where the passenger requesting pickup is at or near the designated spot <NUM> when the vehicle <NUM> arrives, computing devices <NUM> may control vehicle <NUM> to perform the pickup or drop-off at the designated spot <NUM>. Alternatively, computing devices <NUM> may allow the passenger to enter or exit the vehicle <NUM> before reaching the designated spot <NUM>. In this regard, computing devices <NUM> may track loading and unloading events of nearby vehicles, including vehicles in queue <NUM>, and decide whether loading or unloading outside the designated spot <NUM> is tolerated. For instance, referring back to <FIG>, based on sensor data indicating that vehicle <NUM> is loading and/or unloading pedestrian <NUM>, computing devices <NUM> may determine that picking up or dropping off passengers is tolerated at locations other than the front of queue <NUM>.

To keep the passenger apprised of the vehicle's whereabouts while the vehicle <NUM> waits in queue <NUM>, the computing devices <NUM> may be configured to send a message to a client computing device of the passenger, such as client computing device <NUM> of user <NUM>, or client computing device <NUM> of user <NUM>, indicating that the vehicle is waiting in the queue <NUM>. For example, the message may include the expected wait-time for the queue <NUM>. For another example, the message may include a request for an updated arrival time of the passenger requesting pickup, or a request for the passenger's current location. For still another example, computing devices <NUM> may send a message to the passenger's client computing device indicating when the passenger should enter or exit the vehicle <NUM>, such as when vehicle <NUM> has fully stopped at the designated spot <NUM>. Similarly, computing devices <NUM> may display a message, for instance on the internal electronic display <NUM>, requesting that the passenger wait to exit the vehicle until the vehicle has reached the designated spot. This may prevent a passenger from entering and/or exiting the vehicle too early, for instance, before the vehicle has reached the designated spot.

In some instances, once the vehicle has entered the queue, computing devices of the vehicle may determine an amount of time to wait for a passenger requesting pickup at the designated spot for loading or unloading. For example, <FIG> shows an example situation <NUM> in particular for pickups, where computing devices <NUM> determine an amount of time to wait for the passenger who requested the pickup at the designated spot <NUM>. <FIG> shows many of the same features of <FIG>, but with differences as discussed further below. As shown, user <NUM>, who requested the pickup, is not at or near the designated spot <NUM> in the queue <NUM> when vehicle <NUM> arrives at the designated spot <NUM>, computing devices <NUM> may then determine an amount of time to wait for user <NUM> at the designated spot <NUM>, and exit the queue <NUM> after waiting that amount of time.

For instance, computing devices <NUM> may determine the amount of time to wait based on the map information <NUM>. For example, as shown, if the map information <NUM> indicate that the location <NUM> is an airport, computing devices <NUM> may determine the appropriate amount of time <NUM> to wait at the designated spot <NUM> before exiting the queue <NUM> is up to <NUM> minute. For another example, if the map information <NUM> indicate that the location is a school, computing devices <NUM> may determine the appropriate amount of time to wait at the designated spot <NUM> is up to <NUM> minutes before exiting the queue <NUM>.

For still another instance, computing devices <NUM> may determine the amount of time to wait further based on a level of difficulty to exit the queue and re-queue. For example, as shown, if the map information <NUM> indicate that there is a relatively simple way to exit and re-enter the queue <NUM>, such as the easy exit <NUM> provided by road <NUM>, computing devices <NUM> may determine to wait a predetermined amount of time at the designated spot <NUM>, such as <NUM> seconds or more or less, before exiting the queue <NUM>.

Computing devices <NUM> may further determine the amount of time based on the sensor data. For instance, the sensor data may indicate whether the designated spot <NUM> blocks traffic <NUM>. If the sensor data indicate that stopping at the designated spot would block ongoing traffic or otherwise inconvenience other users, such as those illustrated by situation <NUM> of <FIG>, computing devices <NUM> may reduce the amount of time determined based on the map information <NUM>. For example, if computing devices <NUM> determine to wait <NUM> minute at the designated spot <NUM> based on map information <NUM> indicating that location <NUM> is an airport, computing devices <NUM> may reduce the amount of time from <NUM> minute to a predetermined amount of time at the designated spot <NUM>, such as <NUM> seconds or more or less, when determined that stopping at the designated spot <NUM> would inconvenience other road users, such as blocking ongoing traffic or pedestrian crossings.

In some examples, computing devices <NUM> may determine an updated estimated arrival time for the passenger to reach the designated spot <NUM>, and determine to exit the queue <NUM> before waiting the amount of time. In this regard, computing devices <NUM> may send a message to the passenger if he or she is not there when the vehicle <NUM> arrived at the designated spot <NUM>, and may receive an updated estimated arrival time from the passenger. Alternatively, computing devices <NUM> may determine the updated estimated arrival time based on an updated geographical location of the passenger. Continuing from the airport example above, as shown, if the updated estimated arrival time <NUM> is <NUM> minutes when the vehicle <NUM> reached the designated spot <NUM> in the queue <NUM>, computing devices <NUM> may determine not to wait at all, since waiting the <NUM> minute would achieve nothing other than slowing down the queue <NUM>. Computing devices <NUM> thus may simply make a decision <NUM> that the vehicle <NUM> should exit the queue <NUM> and re-queue at a later time.

If the vehicle <NUM> exits the queue before the passenger arrives, for example based on the updated estimated arrival time, computing devices <NUM> may determine an expected wait-time to re-queue and reach the designated spot <NUM>. Further, based on a comparison between the updated estimated arrival time and the expected wait-time to re-queue, computing devices <NUM> may determine whether to re-queue immediately. In this regard, the process may be analogous to comparing the estimated arrival time and the expected wait-time of the queue as illustrated in <FIG>. For instance, if the updated estimated arrival time is less or equal to the expected wait-time to re-queue, computing devices <NUM> may determine to re-queue immediately. Computing devices <NUM> may also send a message to the user device of the passenger indicating that the vehicle is returning to the end of the queue <NUM> along with the expected wait-time to re-queue. Alternatively, if the updated estimated arrival time is greater than the expected wait-time to re-queue, computing devices <NUM> may control the vehicle <NUM> to park in a waiting area, such as parking lot <NUM>.

Claim 1:
A method of queuing by an autonomous vehicle, comprising:
receiving (<NUM>), by one or more processors, a request to pick up or drop off a passenger at a location (<NUM>);
determining (<NUM>), by the one or more processors and based on a type of the location, that the location is likely to have a queue for picking up and dropping off passengers;
when it is determined that the location is likely to have a queue, determining (<NUM>), by the one or more processors and based on sensor data received from a perception system of the autonomous vehicle, that a queue of vehicles exists at a chosen pick-up and drop-off spot at the location;
determining (<NUM>), by the one or more processors and based on the sensor data, whether joining the queue to pick up or drop off the passenger would inconvenience other road users; and
controlling (<NUM>), by the one or more processors, the autonomous vehicle in order to join the queue based on a determination that joining the queue would not inconvenience other road users.