Distribution decision trees

• US 10,173,673 B1
• Filed: 01/05/2017
• Issued: 01/08/2019
• Est. Priority Date: 08/15/2014
• Status: Active Grant

• Current Assignee: Waymo LLC (Alphabet Inc.)
• Original Assignee: Waymo LLC (Alphabet Inc.)
• Inventors: Ferguson, David Ian Franklin, Ogale, Abhijit
• Primary Examiner(s): Anwari, Maceeh
• Application Number:
  US15/399,613
• Time in Patent Office: 733 Days
• Field of Search: 701 27
• CPC Class Codes: B60K 2360/175 Autonomous driving
• CPC Class Codes: B60K 35/28 characterised by the type of the output information, e.g. video entertainment or vehicle dynamics information; characterised by the purpose of the output information, e.g. for attracting the attention of the driver
• CPC Class Codes: B60W 2420/403 Image sensing, e.g. optical camera
• CPC Class Codes: B60W 2420/408 Radar; Laser, e.g. lidar
• CPC Class Codes: B60W 2554/00 Input parameters relating to objects
• CPC Class Codes: B60W 2554/4029 Pedestrians
• CPC Class Codes: B60W 2554/80 Spatial relation or speed relative to objects
• CPC Class Codes: B60W 2554/806 Relative heading
• CPC Class Codes: B60W 2720/10 Longitudinal speed
• CPC Class Codes: B60W 2720/24 Direction of travel
• CPC Class Codes: B60W 30/00 Purposes of road vehicle drive control systems not related to the control of a particular sub-unit, e.g. of systems using conjoint control of vehicle sub-units
• CPC Class Codes: B60W 30/08 Active safety systems predicting or avoiding probable or impending collision or attempting to minimise its consequences
• CPC Class Codes: B60W 30/09 Taking automatic action to avoid collision, e.g. braking and steering
• CPC Class Codes: B60W 30/095 Predicting travel path or likelihood of collision
• CPC Class Codes: B60W 60/00274 considering possible movement changes
• CPC Class Codes: G05D 1/0055 with safety arrangements
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

The present disclosure is directed to autonomous vehicle having a vehicle control system. The vehicle control system includes a processing system that receives input values that indicate attributes of an object within a threshold distance of the autonomous vehicle and variance values indicating uncertainty associated with the input values. The processing system also provides a plurality of outcomes that are associated with combinations of split decisions. A given split decision indicates whether a particular input value is above or below a threshold value associated with the given split decision. The processing system further determines (i) a probability that the particular input value is above a threshold value and (ii) a probability that the particular input is below the threshold value for a given split decision. Additionally, the processing system determines one or more likelihoods associated with a given outcome. Further, the processing system provides instructions to control the autonomous vehicle.

Claims

1. A method comprising:

receiving, at a computing system of an autonomous vehicle, input values that indicate attributes of a vehicle positioned in a given lane within a threshold distance of the autonomous vehicle and variance values indicating uncertainty associated with the input values;

providing a plurality of outcomes, wherein a given outcome is associated with a combination of split decisions, wherein a given split decision indicates whether a particular input value from among the input values is above or below a threshold value associated with the given split decision;

determining, for the given split decision, a probability that the particular input value is above the threshold value and a probability that the particular input value is below the threshold value based on the particular input value and a variance value associated with the particular input value;

determining one or more likelihoods associated with the given outcome, wherein a given likelihood is determined based on the determined probabilities associated with the combination of split decisions indicated by the given outcome; and

based on the determined one or more likelihoods, executing instructions to cause the autonomous vehicle to change position into the given lane.

2. The method of claim 1, wherein the input values that indicate attributes of the vehicle positioned in the given lane include respective input values that indicate a distance of the vehicle from a center of the given lane and an orientation of the vehicle relative to the autonomous vehicle.

3. The method of claim 2, wherein determining one or more likelihoods associated with the given outcome comprises:

determining a likelihood that the vehicle positioned in the given lane is changing lanes based on the respective input values that indicate the distance of the vehicle from the center of the given lane and the orientation of the vehicle relative to the autonomous vehicle.

4. The method of claim 3, wherein based on the determined one or more likelihoods, executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

based on the determined likelihood that the vehicle positioned in the given lane is changing lanes, executing instructions to cause the autonomous vehicle to change position into the given lane after the vehicle completes changing lanes.

5. The method of claim 3, wherein based on the determined one or more likelihoods, executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

based on the determined likelihood that the vehicle positioned in the given lane is changing lanes, executing instructions to cause the autonomous vehicle to refrain from changing position into the given lane.

6. The method of claim 1, wherein executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

executing instructions to control at least a speed or direction of the autonomous vehicle to avoid a collision with the vehicle.

7. The method of claim 1, further comprising:

determining that the vehicle is not moving toward the autonomous vehicle based on the determined likelihood not exceeding a predetermined threshold likelihood.

8. The method of claim 7, wherein executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

executing instructions to cause the autonomous vehicle to change position into the given lane based on determining that the vehicle is not moving toward the autonomous vehicle.

9. A system comprising:

an autonomous vehicle;

at least one sensor configured to determine attributes of a vehicle positioned in a given lane within a threshold distance of the autonomous vehicle;

a module configured to;

receive input values that indicate attributes of a vehicle positioned in a given lane within a threshold distance of the autonomous vehicle and variance values indicating uncertainty associated with the input values;

provide a plurality of outcomes, wherein a given outcome is associated with a combination of split decisions, wherein a given split decision indicates whether a particular input value from among the input values is above or below a threshold value associated with the given split decision;

determine, for the given split decision, a probability that the particular input value is above the threshold value and a probability that the particular input value is below the threshold value based on the particular input value and a variance value associated with the particular input value;

determine one or more likelihoods associated with the given outcome wherein a given likelihood is determined based on the determined probabilities associated with the combination of split decisions indicated by the given outcome; and

based on the determined one or more likelihoods, execute instructions to cause the autonomous vehicle to change position into the given lane.

10. The system of claim 9, wherein the input values that indicate attributes of the vehicle positioned in the given lane includes respective input values that indicate a speed and orientation of the vehicle relative to the autonomous vehicle.

11. The system of claim 10, wherein determining one or more likelihoods associated with the given outcome comprises:

determining a likelihood that the vehicle positioned in the given lane is moving toward a particular location based at least in part on the respective input values that indicate the speed and orientation of the vehicle relative to the autonomous vehicle.

12. The system of claim 11, wherein executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

based on the determined likelihood that the vehicle positioned in the given lane is moving toward the particular location, executing instructions to cause the autonomous vehicle to change position into the given lane after the vehicle reaches the particular location.

13. The system of claim 11, wherein executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

based on the determined likelihood that the vehicle positioned in the given lane is moving toward the particular location, executing instructions to cause the autonomous vehicle to refrain from changing position into the given lane.

14. The system of claim 9, wherein executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

executing instructions to control at least a speed or direction of the autonomous vehicle to avoid a collision with the vehicle.

15. A non-transitory computer-readable medium having stored thereon instructions that, upon execution by at least one processor of a computing device coupled to an autonomous vehicle, cause the computing device to perform functions comprising:

receiving input values that indicate attributes of a vehicle positioned in a given lane within a threshold distance of the autonomous vehicle and variance values indicating uncertainty associated with the input values;

providing a plurality of outcomes, wherein a given outcome is associated with a combination of split decisions, wherein a given split decision indicates whether a particular input value from among the input values is above or below a threshold value associated with the given split decision;

determining, for the given split decision, a probability that the particular input value is above the threshold value and a probability that the particular input value is below the threshold value based on the particular input value and a variance value associated with the particular input value;

determining one or more likelihoods associated with the given outcome wherein a given likelihood is determined based on the determined probabilities associated with the combination of split decisions indicated by the given outcome; and

based on the determined one or more likelihoods, executing instructions to cause the autonomous vehicle to change position into the given lane.

16. The non-transitory computer-readable medium of claim 15, wherein the input values that indicate attributes of the vehicle positioned in the given lane include respective input values that indicate a distance of the vehicle from a center of the given lane and an orientation of the vehicle relative to the autonomous vehicle.

17. The non-transitory computer-readable medium of claim 16, wherein determining one or more likelihoods associated with the given outcome comprises:

determining a likelihood that the vehicle positioned in the given lane is changing lanes based on the respective input values that indicate the distance of the vehicle from the center of the given lane and the orientation of the vehicle relative to the autonomous vehicle.

18. The non-transitory computer-readable medium of claim 17, wherein the function of executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

based on the determined likelihood that the vehicle positioned in the given lane is changing lanes, executing instructions to cause the autonomous vehicle to change position into the given lane after the vehicle changes lanes.

19. The non-transitory computer-readable medium of claim 17, wherein the function of executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

based on the determined likelihood that the vehicle positioned in the given lane is changing lanes, executing instructions to cause the autonomous vehicle to refrain from changing position into the given lane.

20. The non-transitory computer-readable medium of claim 15, wherein the function of executing instructions to cause the autonomous vehicle to change position into the given lane comprises:

executing instructions to control at least a speed or direction of the autonomous vehicle to cause the autonomous vehicle to pass the vehicle before changing position into the given lane.