Patent Description:
Information from the perception system may be combined with highly detailed map information in order to allow a vehicle's computer to safely maneuver the vehicle in various environments. This highly detailed map information may describe expected conditions of the vehicle's environment such as the shape and location of roads, traffic signals, and other objects. In this regard, the information from the perception system and detailed map information may be used to assist a vehicle's computer in making driving decisions involving intersections and traffic signals.

<CIT> discloses an automatic stop control apparatus and system which implements control which stops a vehicle automatically at an intersection near side when it is determined that the vehicle will not escape the intersection before a traffic signal goes red.

One aspect of the disclosure provides a method according to independent claim <NUM>.

In one example, the method also includes, when the estimated location of the vehicle is determined not to be at least a threshold distance past the starting point, determining that the vehicle should stop at or before the starting point. In another example, the method also includes identify a time when a traffic signal light turned from green to yellow, identifying a length of time that the traffic signal light will remain yellow, and identifying the time when the traffic signal light will turn from yellow to red is based on the time when a traffic signal light turned from green to yellow and a length of time that the traffic signal light will remain yellow. In this example, identifying the length of time include calculating the length of time based on a speed limit of a roadway on which the vehicle is traveling. Alternatively, identifying the length of time includes retrieving a default value. In another alternative, identifying the length of time includes accessing a plurality of lengths of times for various traffic signal lights and retrieving a value corresponding to the traffic signal light. In another example, the method also includes, after determining that the vehicle should go through the intersection, estimating, a second location of the vehicle at the time that the traffic signal will turn red, and determining whether the estimated second location of the vehicle will be at least a second threshold distance past the starting point. In this example, the second threshold distance is less than the threshold distance. In another example, the estimated location of the vehicle corresponds to an estimated location of a portion of the vehicle proximate to the rear of the vehicle. In another example, identifying the time when the traffic signal light will turn from yellow to red is based on information received from a device remote from the vehicle.

Other aspects of the disclosure include a computer program according to claim <NUM> and a system according to claim <NUM>.

The technology relates to determining whether an autonomous vehicle, or a vehicle driving in an autonomous mode, should proceed through or stop in response to a yellow traffic light. The case of a yellow light can be especially difficult to address. For example, simply braking for all yellow lights may not be a good decision; if there are other vehicles in the vicinity, in particular those behind the autonomous vehicle, such other vehicles may not expect a sudden stop when there is still time to pass through the light. This could then lead to accidents. Other factors which can complicate determining a response may include whether there are other vehicles in front of the autonomous vehicle which are moving slowly, but have already reached an intersection when the traffic signal turns yellow. In such a case, proceeding through the intersection may cause the autonomous vehicle to drive into the intersection when the traffic signal is actually red. Accordingly, the features described herein address how a computer can determine whether the autonomous vehicle should continue through a traffic intersection when a traffic signal has turned red.

An autonomous vehicle's one or more computing devices may identify the state of a traffic signal using any known techniques. For example, using a combination of sensor data and detailed map information, the computers may estimate an approximate location of a traffic signal. Then using templates, image matching color detection in images, etc. the computers may determine the state of a traffic signal (red, yellow, or green). Alternatively, this information may be received from another device, such as a transmitter associated with a traffic signal light and/or from another vehicle which has made the determination. As such, the computers may also determine when the traffic signal turns from green to yellow using any of the examples above.

In one aspect the decision on whether to stop at a yellow traffic signal may be based on how much braking the vehicle would need to exercise, in order to come to a stop before the intersection. For example, if the required deceleration to stop the vehicle in a given distance to a traffic intersection is larger than a threshold, the vehicle's computers may determine that the vehicle should continue through the intersection. If not, the vehicle's computers may stop the vehicle before the intersection. While such logic works reasonably well for many scenarios, it can fail in situations when the autonomous vehicle (<NUM>) is already braking (and thus braking a bit more would allow the autonomous vehicle to come to a stop), (<NUM>) is accelerating (and thus changing to hard braking is unreasonable), or (<NUM>) the light turns red well before reaching the intersection, but the autonomous vehicle decided to go through based on the above logic.

In order to address such issues, additional factors may be taken into consideration. For example, when approaching a traffic signal, the autonomous vehicle's computers may identify a time when the traffic signal will turn red. For example, this time may be estimated by the computer by access pre-stored information regarding the length of time a yellow traffic signal will remain yellow. This information may be a default estimation value, a measured value for the particular traffic signal or intersection, or mathematically based on a speed limit for the road on which the autonomous vehicle is currently traveling. Alternatively, this length of time or a future time when the light will turn from yellow to red may be received from another device, such as a transmitter associated with a traffic signal light and/or from another vehicle which has made the determination.

The vehicle's computers may also determine a speed profile for the vehicle. This speed profile may be determined iteratively for a brief period of time in the future using any number of constraints including, but not limited to, road speed limit, curvature along trajectory of the autonomous vehicle, minimum and maximum acceleration the autonomous vehicle can execute, smoothness of acceleration, as well as other traffic participants along the trajectory. For example, a speed profile may be determined by analyzing all constraints for every second for the next <NUM> seconds or so as cost functions, where each cost function would be a lower value if the autonomous vehicle is in a desirable state and a higher value otherwise. By summing each of the cost function values, the computers may select the speed profile having the lowest total cost value. Non-linear optimization may allow for the determination of a solution in a short period of time. In addition, a speed profile computed in a previous iteration of the decision logic may also be used to determine a current speed profile. This can save time for making the decision more quickly as the speed profile usually does only change little if the overall traffic situation does not change abruptly.

Using the speed profile, the computers may estimate a future location of the autonomous vehicle at the time when the traffic signal will change from yellow to red. This time may be determined using the information regarding the length of time a yellow traffic signal will remain yellow as well as the time when the computers determined that the traffic signal changed from green to yellow. Then using this length of time and the speed profile, the computers may estimate where the autonomous vehicle will be located when the traffic signal light will change from yellow to red. Alternatively, if the vehicle's computer receives information identifying a future time when a traffic signal light will turn from yellow to red from another device, this future time may be used to estimate where the autonomous vehicle will be located when the traffic signal light will change from yellow to red.

The estimated future location may be determined using a reference location relative to the autonomous vehicle. For example, this reference location may be a most rear facing point on the autonomous vehicle, a point in the center of a rear axle of the autonomous vehicle, point or plane of a rear bumper of the autonomous vehicle, etc. In some examples, the reference may be selected based upon a legal requirement, such as a requirement that a vehicle's rear wheels be within an intersection before a traffic signal turns red. In such an example, the point or reference may include a point on one of the rear tires or a plane extending between the rear tires.

Using the estimated future location, the computers may determine whether the reference location will reach a certain location within the intersection when the traffic signal will change from yellow to red. For example, the detailed map information may define locations where the intersection starts and ends as well as threshold information. Alternatively, the location of the intersection may be determined by the vehicle's computer using sensor information, such as data from a camera and/or laser, to detect typical features of an intersection such as a white stop line, the location of traffic signals, or locations at which one or more other roadways meeting with the roadway on which the vehicle is driving. This information may be used to identify a location defining a starting point for the intersection where the vehicle should stop, such as no further than the first traffic signal at an intersection. If the estimated location of the vehicle is at least a threshold distance into the intersection and from the location defining the starting point of the intersection, the autonomous vehicle may continue through the intersection. If not, the autonomous vehicle may stop.

The threshold distance may initially be a predetermined distance. However, as the vehicle moves closer to the intersection, because of the possibility of changes to the speed profile based on other factors (such as other vehicles, etc.), this threshold may actually decrease as the autonomous vehicle approaches the intersection.

The aspects described herein thus allow for the autonomous vehicle's computers to make decisions about whether to enter an intersection in response to a yellow traffic signal. Again, such aspects also allow the autonomous vehicle to comply with legal requirements that require a vehicle to have its rear-most axle within an intersection when a traffic signal turns red.

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, boats, airplanes, helicopters, lawnmowers, recreational vehicles, amusement park vehicles, farm equipment, construction equipment, trams, golf carts, trains, and trolleys. 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.

The memory <NUM> stores information accessible by the one or more processors <NUM>, including data <NUM> and instructions <NUM> that may be executed or otherwise used by the processor (s) <NUM>. The memory <NUM> may be of any type capable of storing information accessible by the processor(s), including a computing device-readable medium, or other medium that stores data that may be read with the aid of an electronic device, such as a hard-drive, memory card, ROM, RAM, DVD or other optical disks, as well as other write-capable and read-only memories.

The data <NUM> may be retrieved, stored or modified by processor(s) <NUM> in accordance with the instructions <NUM>.

The one or more processors <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, such as a field programmable gate array (FPGA). Although <FIG> functionally illustrates the processor(s), 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. For example, 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 have 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, a small LCD touch-screen or any other electrical device that is operable to display information). In this example, the vehicle includes an internal electronic display <NUM>. 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 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 as needed in order to control the vehicle in fully autonomous (without input from a driver) as well as semiautomonus (some input from a driver) driving modes.

As an example, <FIG> depicts an interior design of a vehicle having autonomous, semiautonomous, and manual (continuous input from a driver) driving modes. In this regard, the autonomous vehicle may include all of the features of a non-autonomous vehicle, for example: a steering apparatus, such as steering wheel <NUM>; a navigation display apparatus, such as navigation display <NUM> (which may be a part of electronic display <NUM>); and a gear selector apparatus, such as gear shifter <NUM>. The vehicle may also have various user input devices <NUM> in addition to the foregoing, such as touch screen <NUM> (again, which may be a part of electronic display <NUM>), or button inputs <NUM>, for activating or deactivating one or more autonomous driving modes and for enabling a driver or passenger <NUM> to provide information, such as a navigation destination, to the computing device <NUM>.

Returning to <FIG>, when engaged, computer <NUM> may control some or all of these functions of vehicle <NUM> and thus be fully or partially autonomous. It will be understood that although various systems and computing device <NUM> are shown within vehicle <NUM>, these elements may be external to vehicle <NUM> or physically separated by large distances.

In this regard, computing device <NUM> may be in communication various systems of vehicle <NUM>, such as deceleration system <NUM>, acceleration system <NUM>, steering system <NUM>, signaling system <NUM>, navigation system <NUM>, positioning system <NUM>, and perception system <NUM>, such that one or more systems working together may control the movement, speed, direction, etc. of vehicle <NUM> in accordance with the instructions <NUM> stored in memory <NUM>. 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>.

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 identifying the shape and elevation of roadways, lane lines, intersections, crosswalks, speed limits, traffic signals, buildings, signs, real time traffic information, vegetation, or other such objects and information.

<FIG> is an example of detailed map information <NUM> for a section of roadway including an intersection <NUM>. In this example, the detailed map information <NUM> includes information identifying the shape, location, and other characteristics of lane lines <NUM>, <NUM>, <NUM>, traffic signals <NUM>, <NUM>, <NUM>, <NUM>, crosswalks <NUM>, <NUM>, <NUM>, <NUM>. Although the examples herein relate to a simplified three-light, three-state traffic signals (e. g, a green light state indicating that a vehicle can proceed through an intersection, a yellow light state indicating a transition state where the vehicle can proceed with caution but may need to stop at an intersection, and a red light state indicating that the vehicle should stop before the intersection, etc.), other types of traffic signals, such as those for right or left turn only lanes may also be used.

In addition, the detailed map information includes a network of rails <NUM>, <NUM>, <NUM>, which provide the vehicle's computer with guidelines for maneuvering the vehicle so that the vehicle follows the rails and obeys traffic laws. As an example, a vehicle's computer may maneuver the vehicle from point A to point B (two fictitious locations not actually part of the detailed map information) by following rail <NUM>, transitioning to rail <NUM>, and subsequently transitioning to rail <NUM> in order to make a left turn at intersection <NUM>.

The detailed map information <NUM> may also include a number of markers <NUM>, <NUM>, <NUM>, and <NUM> which indicate the beginning of a traffic intersection or the point by which the vehicle must be stopped if traffic signal corresponding to the vehicle's current lane were to be signaling a red light. For simplicity, additional details, such as additional traffic signals and rails, of the intersection <NUM> are not shown. Although the example herein is shown pictorially for a right-lane drive location, the detailed map information may be stored in any number of different ways including databases, roadgraphs, etc. and may include maps of left-lane drive locations as well.

Positioning system <NUM> may be used by computing device <NUM> in order to determine the vehicle's relative or absolute position on a map or on the earth. For example, the position system <NUM> may include a GPS receiver to determine the device's latitude, longitude and/or altitude position. Other location systems such as laser-based localization systems, inertial-aided GPS, or camera-based localization may also be used to identify the location of the vehicle. The location of the vehicle may include an absolute geographical location, such as latitude, longitude, and altitude as well as relative location information, such as location relative to other cars immediately around it which can often be determined with less noise that absolute geographical location.

The positioning system <NUM> may also include other devices in communication with computing device <NUM>, such as an accelerometer, gyroscope or another direction/speed detection device to determine the direction and speed of the vehicle or changes thereto. By way of example only, an acceleration device may determine its pitch, yaw or roll (or changes thereto) relative to the direction of gravity or a plane perpendicular thereto. The device may also track increases or decreases in speed and the direction of such changes. The device's provision of location and orientation data as set forth herein may be provided automatically to the computing device <NUM>, other computing devices and combinations of the foregoing.

The perception system <NUM> also includes one or more components for detecting and performing analysis on 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 lasers, sonar, radar, one or more cameras, or any other detection devices which record data which may be processed by computing device <NUM>. In the case where the vehicle is a small passenger vehicle such as a car, the car may include a laser mounted on the roof or other convenient location as well as other sensors such as cameras, radars, sonars, and additional lasers. The computing device <NUM> may control the direction and speed of the vehicle by controlling various components. By way of example, if the vehicle is operating completely autonomously, computing device <NUM> may navigate the vehicle to a location using data from the detailed map information and navigation system <NUM>. Computing device <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 device <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 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>).

<FIG> is an example external view of vehicle <NUM> described above. As shown, various components of the perception system <NUM> may be positioned on or in the vehicle <NUM> in order to better detect external objects while the vehicle is being driven. In this regard, one or more sensors, such as laser range finders <NUM> and <NUM> may be positioned or mounted on the vehicle. As an example, the one or more computing devices <NUM> (not shown) may control laser range finder <NUM>, e.g., by rotating it <NUM> degrees. In addition, the perception system may include one or more cameras <NUM> mounted internally on the windshield of vehicle <NUM> to receive and analyze various images about the environment. In addition to the laser range finder <NUM> is positioned on top of perception system <NUM> in <FIG>, and the one or more cameras <NUM> mounted internally on the windshield, other detection devices, such as sonar, radar, GPS, etc., may also be positioned in a similar manner.

The one or more computing devices <NUM> may also include features such as transmitters and receivers that allow the one or more devices to send and receive information to and from other devices. For example, the one or more computing devices may determine information about the current status of a traffic signal light as well as information about when the status of the traffic signal light changes (from green to yellow to red to green). The one or more computing devices may send this information to other computing devise associated with other vehicles. Similarly, the one or more computing devices may receive such information from other computing devices. For example, the one or more computing devise may receive information about the current status of a traffic signal light as well as information about when the status of the traffic signal light changes from one or more other computing devices associated with other autonomous or non-autonomous vehicles. As another example, the one or more computing devices may receive such information with devices associated with the traffic signal lights. In this regard, some traffic signal lights may include transmitters that send out information about the current status of a traffic signal light as well as information about when the status of the traffic signal light changes.

This information may be sent and received via any wireless transmission method, such as radio, cellular, 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. Such communication may be facilitated by any device capable of transmitting data to and from other computers, such as modems and wireless interfaces.

As noted above, a vehicle's one or more computing devices may maneuver the vehicle using the various systems described above. For example, <FIG> depicts a section of roadway <NUM> including an intersection <NUM>. Vehicle <NUM> is approaching intersection <NUM> and may be controlled, for example by one or more computing device <NUM> in an autonomous driving mode as described above.

In this example, intersection <NUM> corresponds to the intersection <NUM> of the detailed map information <NUM>. In this regard, lane lines <NUM>, <NUM>, and <NUM> correspond to the shape, location, and other characteristics of lane lines <NUM>, <NUM>, and <NUM>, respectively. Similarly crosswalks <NUM>, <NUM>, <NUM>, and <NUM> correspond to the shape, location, and other characteristics of crosswalks <NUM>, <NUM>, <NUM>, and <NUM>, respectively and traffic signal <NUM> corresponds to the shape, location, and other characteristics of traffic signal <NUM>. For simplicity, only a single traffic signal <NUM> is shown, though other traffic signals corresponding to the shape, location, and other characteristics of traffic signals <NUM>, <NUM>, and <NUM> may also exist.

An autonomous vehicle's one or more computing devices may identify the state of a traffic signal using any known techniques. For example, using a combination of sensor data and the expected location of traffic signals in the detailed map information, the computers may estimate an approximate location of a traffic signal related to the location of a vehicle. For example, returning to <FIG>, when a vehicle is at point A (corresponding to the location of vehicle <NUM> in <FIG>), the vehicle's computer may access the detailed map information in order to determine that traffic signals <NUM>, <NUM>, <NUM>, and <NUM> are all relevant to the position of the vehicle <NUM>. Thus, all other traffic signals, such as those that would be relevant to a vehicle positioned at points B or C in <FIG> (two additional fictitious locations not actually part of the detailed map information) may be ignored. Then using templates, image matching color detection in images, etc. the computers may determine the state of these traffic signals (red light, yellow light, or green light). Alternatively, the locations of traffic signals may be estimated solely from the sensor data, and without reference to detailed map information. As another example, the locations of traffic signals may be received from another device, such as a transmitter associated with a traffic signal light and/or from another vehicle which has made the determination.

The one or more computing devices <NUM> may also identify when the traffic signals change state. For example, the vehicle's one or more computing devices <NUM> may monitor the state of these traffic signals over a brief period of time to determine when the traffic signal changes state. In the example of <FIG>, the vehicle's one or more computing devices may estimate a time when the traffic signal changes states based on the information used to identify the state of the traffic signals. For example, using timestamp information associated with the images captured by the vehicle's cameras several times per second, the vehicle's one or more computing devices may estimate a time when a traffic signal changes state from one light color to another, such as from a green light state to a yellow light state (green to yellow). This information may then be used to determine whether to stop the vehicle (because the traffic signal light may eventually turn red) or continue through the intersection without stopping. Alternatively, the time when a traffic signal changes state from one light color to another may be received from another device, such as a transmitter associated with a traffic signal light and/or from another vehicle which has made the determination.

The vehicle's one or more computing devices may determine whether to continue through or to stop at an intersection when a relevant traffic signal is in the yellow light state based on how much braking power would be required to stop the vehicle by the intersection. For example returning to <FIG>, if "d" is the remaining distance between point A and marker <NUM> (which indicates the beginning of intersection <NUM>), and "v" is the current speed of vehicle <NUM> then the required deceleration "a" to stop is given as a = <NUM> v^<NUM> / d. In this example, if v is in meters per second and d is in meters, then the deceleration a will be in meters per second squared. The vehicle's one or more computing devices <NUM> may compare the deceleration a to a threshold value to determine whether the vehicle should go through the intersection. The threshold value may be selected based upon a comfortable breaking power for a passenger of the vehicle. Too much deceleration may be scary for a passenger (e.g. it would be as if a driver were to "slam" on the breaks in order to stop at an intersection). Thus, if this deceleration a is larger than the threshold, the vehicle's one or more computing devices <NUM> may allow the vehicle to continue through the intersection, and if not, the vehicle's one or more computing devices may stop the vehicle.

In other examples, additional factors may be taken into consideration when the vehicle's one or more computing devices are determining whether to continue through an intersection when a relevant traffic signal is in a yellow light state. For example, when approaching a traffic signal, the autonomous vehicle's one or more computing devices <NUM> may identify a time when the traffic signal light will change from the yellow light state to the red light state (yellow to red).

In one instance, the computer may first identify a length of time that a traffic signal will remain in the yellow light state. This may include accessing information regarding the length of time a yellow traffic signal will remain yellow. This information may be a default estimation value (e.g., always <NUM> seconds), a measured value for the particular traffic signal or intersection (e.g., specific to traffic signal <NUM>), or mathematically based on a speed limit for the road on which the vehicle <NUM> is currently traveling. As an example, on a <NUM> mile per hour road, traffic signal lights may have a period yellow light on the order of less than <NUM> seconds, whereas on a <NUM> mile per hour road, the traffic signal lights may have a longer period yellow light, such as <NUM> or more seconds. Alternatively, this information may be received from another device, such as a transmitter associated with a traffic signal light and/or from another vehicle which has made the determination.

Based on the identified length of time, the vehicle's one or more computing devices may identify a time when the traffic signal will turn from the yellow light state to a red light state (yellow to red). This may be done by simply adding the identified length of time to the estimated time when the traffic signal turned from the green light state to the yellow light state. Alternatively, a future time when the traffic signal will turn from the yellow light state to a red light state may be received from another device, such as a transmitter associated with a traffic signal light and/or from another vehicle which has made the determination.

The vehicle's one or more computing devices may also determine a speed profile for the vehicle. A speed profile may describe an expected future speed and in some cases an expected future acceleration and deceleration for a plurality of different times in the future. As noted above, this speed profile may be determined iteratively for a brief period of time (e.g., every second, or more or less, for the next <NUM> seconds, or more or less). As an example of a simple speed profile which ignores more complex factors, the vehicle's one or more computing devices may assume that the vehicle's current speed will continue (e.g., there will be no acceleration or deceleration) over the brief period or use the vehicle's current speed and acceleration and deceleration to estimate the vehicle's future speed.

A speed profile may also be determined using any number of additional constraints including, but not limited to, road speed limit, curvature along trajectory of the autonomous vehicle, minimum and maximum acceleration the autonomous vehicle can execute, smoothness of acceleration, as well as other traffic participants along the trajectory. For example, a speed profile may be determined by analyzing all such constraints for every second for the next <NUM> seconds or so as cost functions, where each cost function would be a lower value if the autonomous vehicle is in a desirable state and a higher value otherwise. By summing each of the cost function values, the computers may select the speed profile having the lowest total cost value. Non-linear optimization may allow for the determination of a solution in a short period of time.

In addition, a speed profile computed in a previous iteration of the decision logic may also be used to determine a current speed profile. This can save time for making the decision more quickly as the speed profile usually does only change little if the overall traffic situation does not change abruptly.

Using the speed profile, the vehicle's one or more computing devices may estimate a future location of the autonomous vehicle at the time when the traffic signal will change from the yellow light state to the red light state. For example, using the simplest speed profile (where the speed of the vehicle does not change) the future location may be determined by multiplying the speed of the vehicle by the difference between the current time and the estimated time when the traffic signal will change from the yellow light state to the red light state. Alternatively, if the vehicle's computer receives information identifying a future time when a traffic signal light will turn from yellow to red from another device, this future time may be used to estimate where the autonomous vehicle will be located when the traffic signal light will change from yellow to red.

Of course, where the speed profile is more complex, estimating the future location may be simplified by finding the vehicle's average speed until the time when the traffic signal will change from the yellow light state to the red light state and multiplying this value by the difference between the current time and the estimated time when the traffic signal will change from the yellow light state to the red light state. Again, if the vehicle's computer receives information identifying a future time when a traffic signal light will turn from yellow to red from another device, this future time may be used to estimate where the autonomous vehicle will be located when the traffic signal light will change from yellow to red. <FIG> is an example of an estimated future location of vehicle <NUM> (shown in dashed line as it is an estimate) at the time when traffic signal <NUM> changes from the yellow light state to the red light state relative to the section of roadway <NUM>.

The estimated future location may be determined using a reference location relative to the autonomous vehicle. For example, this reference location may be a most rear facing point on the vehicle <NUM>, a point in the center or along a plane of a rear axle of the vehicle as indicated by arrow <NUM>, point or plane of a rear bumper of the vehicle as indicated by arrow <NUM>, etc. In some examples, the reference may be selected based upon a legal requirement, such as a requirement that a vehicle's rear wheels be within an intersection before a traffic signal turns red. In such an example, the point or reference may include a point on one of the rear tires or a plane extending between the rear tires as indicated by arrow <NUM>.

The vehicle's one or more computing devices may also identify a starting point of an intersection associated with the relevant traffic signal. For example, as noted above, the detailed map information may include markers that define locations where the intersection starts and ends as well as threshold information. The relevant marker for an intersection may be the marker that the vehicle will pass before an intersection along a particular rail. Returning to <FIG>, when traveling along rail <NUM> from point <NUM> towards intersection <NUM>, the vehicle will first pass through marker <NUM>. Thus, marker <NUM> may be the relevant marker for intersection <NUM>.

Alternatively, the location of the intersection may be determined by the vehicle's computer using sensor information, such as data from a camera and/or laser, to detect typical features of an intersection such as a white stop line, the location of traffic signals, or locations at which one or more other roadways meeting with the roadway on which the vehicle is driving. This information may be used to identify a location defining a starting point for the intersection where the vehicle should stop, such as no further than the first traffic signal at an intersection.

The vehicle's one or more computing devices may determine whether the vehicle, and in some cases the reference location of the vehicle, will be at least a threshold distance passed the starting point when the traffic signal will change from the yellow light state to the red light state. For example, the threshold distance may initially be a predetermined distance, such as <NUM> meters or more or less, selected based upon the stopping power of the vehicle as in the example described above. For example, <FIG> is another example of the detailed map information <NUM> but includes reference point <NUM> indicating a threshold distance Th along the rail <NUM> passed marker <NUM>.

Based on whether the estimated future location of the vehicle is determined to be at least the threshold distance past the starting point, the vehicle's one or more computing devices, may determine whether the vehicle should continue through the intersection. If the estimated future location is at least a threshold distance passed the location of the relevant marker (or at least a threshold distance into the intersection) the vehicle's one or more computing devices <NUM> may allow the vehicle to continue through the intersection. If not, the one or more computing devices <NUM> may stop the vehicle by the location of the marker.

For example, <FIG> is an example of the section of roadway <NUM> including the future estimated location of vehicle <NUM> at the time when traffic signal <NUM> changes from the yellow light state to the red light state. However, this example also includes the location of marker <NUM> and reference point <NUM> of <FIG>. Here, the future estimated location of vehicle <NUM> (even relative to the planes of arrows <NUM> and <NUM>) is passed the reference point <NUM>. In this regard, the vehicle's one or more computing devices may allow the vehicle to continue through the intersection. Similarly, if vehicle <NUM> were to not pass the location of reference point <NUM> by the time that the when traffic signal <NUM> changes from the yellow light state to the red light state, the vehicle's one or more computing devices may being the vehicle to a atop at or before the location of marker <NUM>.

As the vehicle becomes closer to the intersection, because of the possibility of changes to the speed profile based on other factors (such as other vehicles, etc.), the threshold may actually decrease. For example, as shown in <FIG>, as vehicle <NUM> approaches the intersection <NUM>, the threshold distance Th may decrease to Th'. Thus, when vehicle <NUM> moves from the location of point E to the location of point F, the reference point <NUM> may be relocated to the location of reference point <NUM>. Thus, as the vehicle <NUM> moves closer to the intersection <NUM>, the vehicle need not be as far into the intersection <NUM> in order for the vehicle's one or more computing devices to allow the vehicle to continue through the intersection.

<FIG> is an example flow diagram <NUM> which depicts some of the aspects described above which may be performed by one or more computing devices such as one or more computing devices <NUM> of vehicle <NUM>. In this example, the information identifying a time when a traffic signal light turned from green to yellow is received at block <NUM>. A length of time that the traffic signal light will remain yellow is identified at block <NUM>. A time when the traffic signal light will turn from yellow to red based on the time when a traffic signal light turned from green to yellow and a length of time that the traffic signal light will remain yellow is estimated at block <NUM>. A location of a vehicle at the estimated time that the traffic signal light will turn from yellow to red is estimated at block <NUM>. A starting point of an intersection associated with the traffic signal light based on detailed map information is identified at block <NUM>. Whether the estimated location of the vehicle will be at least a threshold distance past the starting point is determined at block <NUM>. When the estimated location of the vehicle is determined to be at least a threshold distance past the starting point, the vehicle should continue through the intersection is determined at block <NUM>.

In some examples, the traffic signal light may turn red before the estimated time that the traffic signal light will turn from red to yellow. This may be for various reasons such as a misclassification of the light color when determining the status of a traffic signal light, incorrectly identifying a length of time that a traffic signal will remain in the yellow light state, or simply because the timing of the particular traffic signal light includes some anomaly. In such a case, the vehicle's computing device may make the direct computation of whether the vehicle can be stopped in time without going too far into the intersection (e.g., not more than <NUM> meter or more or less for safety reasons), for example, using the braking power example described above.

Unless otherwise stated, the foregoing alternative examples are not mutually exclusive, but may be implemented in various combinations to achieve unique advantages. As these and other variations and combinations of the features discussed above can be utilized without departing from the subject matter defined by the claims, the foregoing description of the embodiments should be taken by way of illustration rather than by way of limitation of the subject matter defined by the claims. In addition, the provision of the examples described herein, as well as clauses phrased as "such as," "including" and the like, should not be interpreted as limiting the subject matter of the claims to the specific examples; rather, the examples are intended to illustrate only one of many possible embodiments. Further, the same reference numbers in different drawings can identify the same or similar elements.

Claim 1:
A computer-implemented method comprising:
identifying (<NUM>), by one or more computing devices internal to a vehicle, a time when a traffic signal light will turn from yellow to red;
estimating (<NUM>), by the one or more computing devices, a location of a vehicle at the identified time that a traffic signal light will turn from yellow to red;
identifying (<NUM>), by the one or more computing devices, a starting marker (<NUM>) at an intersection associated with a traffic signal light;
determining (<NUM>), by the one or more computing devices, whether the estimated location of the vehicle will be at least a threshold distance past the starting marker into the intersection;
the method characterised by comprising:
when the estimated location of the vehicle is determined to be within the intersection and at least a threshold distance past the starting marker into the intersection, determining (<NUM>), by the one or more computing devices, that the vehicle should continue through the intersection.