Distribution decision trees

• US 9,187,088 B1
• Filed: 12/30/2014
• Issued: 11/17/2015
• Est. Priority Date: 08/15/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ogale, Abhijit, Ferguson, David Ian Franklin
• Primary Examiner(s): Anwari, Maceeh
• Application Number:
  US14/585,681
• Time in Patent Office: 322 Days
• Field of Search: 701/23
• US Class Current: 1/1
• CPC Class Codes: B60K 2360/175 Autonomous driving
• CPC Class Codes: B60K 2370/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, from a computing device coupled to an autonomous vehicle, 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;

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, (i) a probability that the particular input value is above the threshold value and (ii) a probability that the particular input value is below the threshold value based on the particular input value and the 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, providing instructions executable by the computing device to control the autonomous vehicle.

2. The method of claim 1, wherein determining, for the given split decision, (i) the probability that the particular input value is above the threshold value and (ii) the probability that the particular input value is below the threshold value comprises:

determining, for the given split decision, a cumulative distribution function based on the threshold value and the variance value corresponding to the particular input value, wherein the cumulative distribution function indicates a probability that a certain input value is less than or equal to the threshold value;

determining, for the given split decision, the probability that the particular input value is above the threshold value associated with the given split decision using the determined cumulative distribution function; and

determining, for the given split decision, the probability that the particular input value is below the threshold value associated with the given split decision using the determined cumulative distribution function.

3. The method of claim 1, wherein determining the one or more likelihoods comprises:

determining one or more compound probabilities, wherein a given compound probability corresponds to the given outcome, and wherein the given compound probability corresponds to a product of the determined probabilities associated with the combination of split decisions indicated by the given outcome;

receiving one or more weightings, wherein a given weighting corresponds to the given outcome; and

determining the one or more likelihoods based on the corresponding one or more compound probabilities and the corresponding one or more weightings.

4. The method of claim 3, wherein determining the one or more likelihoods based on the corresponding one or more compound probabilities and the corresponding one or more weightings comprises:

determining one or more linear combinations of the one or more compound probabilities and the corresponding one or more weightings;

determining one or more sums of the one or more compound probabilities; and

determining the one or more likelihoods as a quotient of a given linear combination and a given sum.

5. The method of claim 1, wherein providing instructions executable by the computing device to control the autonomous vehicle comprises:

determining whether the attributes of the object within the threshold distance of the autonomous vehicle indicate that the object is moving toward a particular location based on the determined one or more likelihoods; and

based on determining that the attributes of the object indicate that the object is moving toward the particular location, providing instructions executable by the computing device to control the autonomous vehicle.

6. The method of claim 1, wherein providing instructions executable by the computing device to control the autonomous vehicle comprises:

providing instructions executable by the computing device to control at least one of a speed and a direction of the autonomous vehicle to avoid a collision with the object.

7. The method of claim 1, further comprising:

receiving training data that includes a plurality of input values corresponding to an attribute of the object within the threshold distance; and

determining the threshold value associated with the given split decision based on the received training data.

8. 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 training data indicative of a plurality of samples, wherein the samples include sets of feature values and respective labels associated with the sets of feature values, wherein a given set of feature values indicates attributes of an object within a threshold distance of the autonomous vehicle, and wherein a given label indicates whether or not the object performed a particular action;

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 feature value associated with the given attribute is above or below a threshold value associated with the given split decision;

determining subsets of the plurality of samples associated with respective outcomes, wherein at least two of the subsets share at least one common sample;

determining likelihoods associated with respective outcomes, wherein a given likelihood indicates that the object is performing a particular action, and wherein the given likelihood associated with a given outcome is determined based on the labels of the samples in the subset associated with the given outcome;

determining a particular outcome from the plurality of outcomes that corresponds to a set of input value measurements, wherein the set of input value measurements indicates attributes of the object within the threshold distance of the autonomous vehicle; and

providing instructions executable by the computing device to control the autonomous vehicle based on the likelihood associated with the particular outcome.

9. The non-transitory computer-readable medium of claim 8, wherein determining subsets of the plurality of samples associated with respective outcomes comprises:

determining, for a given split decision, a first subset of samples and a second subset of samples from the plurality of samples, wherein the first subset includes samples from the plurality of samples with a particular feature value that is less than a first threshold, wherein the second subset includes samples from the plurality of samples that with the particular feature value that exceeds a second threshold, and wherein the first threshold is greater than the second threshold.

10. The non-transitory computer-readable medium of claim 9, further comprising:

determining variances for respective attributes based on the received training data, wherein a given variance indicates an uncertainty associated with a given attribute; and

determining the first threshold and the second threshold based on the determined variances.

11. The non-transitory computer-readable medium of claim 8, further comprising:

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

12. The non-transitory computer-readable medium of claim 8, wherein the particular outcome indicates that the object is moving toward the autonomous vehicle, and wherein the provided instructions control the autonomous vehicle to avoid coming in contact with the object.

13. The non-transitory computer-readable medium of claim 8, wherein providing instructions executable by the computing device to control the autonomous vehicle comprises:

providing instructions executable by the computing device to control at least one of a speed and a direction of the autonomous vehicle to avoid a collision with the object.

14. A system comprising:

an autonomous vehicle;

at least one sensor configured to determine attributes of an object within a threshold distance of the autonomous vehicle;

a computing device comprising at least one processor; and

a non-transitory computer-readable medium having stored thereon instructions that, upon execution by the at least one processor, cause the computing device to perform functions comprising;

receiving, from the computing device, input values that indicate the attributes of the object within the 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 corresponds to a combination of split decisions, wherein a given split decision indicates whether a particular input value meets a criterion associated with the given split decision;

determining, for the given split decision, (i) a probability that the particular input value meets the criterion and (ii) a probability that the particular input value does not meet the criterion;

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, providing instructions executable by the computing device to control the autonomous vehicle.

15. The system of claim 14, wherein determining the one or more likelihoods comprises:

determining, for the given split decision of the given outcome, whether the probability that the particular input value meets the criterion exceeds a threshold probability; and

based on the determined probability being below the threshold probability, determining the given likelihood associated with the given outcome as the determined probability that the particular input value meets the criterion.

16. The system of claim 14, wherein the criterion associated with the given split decision indicates (i) whether the corresponding input value is above a first threshold value associated with the given split decision and (ii) whether the corresponding input value is below a second threshold value associated with the given split decision.

17. The system of claim 16, wherein the first threshold value is greater than the second threshold value.

18. The system of claim 14, wherein the functions further comprise:

receiving a request to maneuver the autonomous vehicle to a particular location;

determining whether the attributes of the object within the threshold distance of the autonomous vehicle indicate that the object will be within a threshold distance of the particular location within a particular range of time based on the determined one or more likelihoods; and

based on determining that the attributes of the object within the threshold distance of the autonomous vehicle indicate that the object will not be within the threshold distance of the particular location within the particular range of time, providing instructions executable by the computing device to move the autonomous vehicle to the particular location.

19. The system of claim 14, wherein providing instructions executable by the computing device to control the autonomous vehicle comprises:

determining whether the attributes of the object within the threshold distance of the autonomous vehicle indicate that the object is moving toward a particular location based on the determined one or more likelihoods; and

based on determining that the attributes of the object indicate that the object is not moving toward a particular location, providing instructions executable by the computing device to control the autonomous vehicle.

20. The system of claim 14, wherein the functions further comprise:

determining a length of time since providing the instructions executable by the computing device to control the autonomous vehicle; and

based on the length of time exceeding a threshold length of time, repeating the functions of (i) receiving the input values and the variance values, (ii) determining the probability that the particular input value meets the criterion and the probability that the particular input value does not meet the criterion, (iii) determining the one or more likelihoods, and (iv) providing the instructions executable by the computing device to control the autonomous vehicle.