Using segmented cones for fast, conservative assessment of collision risk

• US 7,831,391 B2
• Filed: 06/12/2007
• Issued: 11/09/2010
• Est. Priority Date: 06/12/2007
• Status: Active Grant

• Current Assignee: Uatc, LLC (Uber Technologies, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Greene, Daniel H., Reich, James E., Liu, Juan
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Holwerda, Stephen
• Application Number:
  US11/818,191
• Publication Number:
  US 20080312833A1
• Time in Patent Office: 1,246 Days
• Field of Search: 340/436, 340/903, 340/435, 701/301, 701/1, 701/211, 701/216, 342/70, 382/103, 382/104, 382/107, 382/154, 348/148, 700/245
• US Class Current: 701/301
• CPC Class Codes: G06V 20/58 Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads
• CPC Class Codes: G08G 1/165 for passive traffic, e.g. including static obstacles, trees
• CPC Class Codes: G08G 1/166 for active traffic, e.g. moving vehicles, pedestrians, bikes

Abstract

One embodiment of the present invention provides a system that facilitates assessment of collision between a primary principal and a non-primary principal for early warning. During operation, the system receives information which indicates a state of the primary principal and a state of the non-primary principal. The system divides future time into a number of time intervals, and estimates a number of possible future states of the primary and non-primary principals, wherein each future state corresponds to a time interval. The system further represents the possible future states of the primary or non-primary principal as one or more geometric objects in a space of which at least one dimension indicates the time. In addition, the system determines a probability of collision between the primary and non-primary principals based on the geometric objects.

Claims

1. A method for facilitating assessment of collision between a primary principal and a non-primary principal for early warning, the method comprising:

receiving information which indicates a state of the primary principal and a state of the non-primary principal;

dividing future time into a number of time intervals;

estimating a number of possible future states of the primary and non-primary principals, wherein each future state corresponds to a time interval;

representing the possible future states of the primary or non-primary principal as one or more 3-dimensional geometric objects in a space of which at least one dimension indicates the time, wherein a 3-dimensional geometric object indicates a location where the principal may be at a given time interval; and

determining a probability of collision between the primary and non-primary principals, which involves determining whether 3-dimensional geometric objects for the primary and non-primary principals intersect.

2. The method of claim 1,

wherein a projection of the 3-dimensional geometric object on the X-Y plane indicates the location of the principal;

and

wherein the Z-position of the 3-dimensional geometric object indicates the future time at which the principal is within the location corresponding to the geometric object.

3. The method of claim 1,

wherein a geometric object comprises a bounding box that covers possible future locations of a principal at one or more future times.

4. The method of claim 1,

wherein a geometric object comprises a prismatoid;

wherein the bottom of the prismatoid corresponds to the possible location of the primary or non-primary principal at the beginning of a time interval; and

wherein the top of the prismatoid corresponds to the possible location of the primary or non-primary principal at the end of the time interval.

5. The method of claim 1,

wherein determining the probability of collision between the primary and non-primary principals comprises determining an overlap between two geometric objects which correspond to the primary and non-primary principals respectively and which correspond to the same time interval.

6. The method of claim 1,

wherein determining the probability of collision between the primary and non-primary principals comprises estimating a respective bounding box which encloses the geometric object representing a future state of the primary or non-primary principal;

and

wherein the method further comprises determining whether any of the bounding boxes for the primary and non-primary principals intersect.

7. The method of claim 6,

wherein if two bounding boxes intersect, the method further comprises determining whether the geometric objects within the two bounding boxes intersect.

8. The method of claim 6,

wherein the probability of collision is computed based on the amount of overlap between the bounding boxes.

9. The method of claim 1,

wherein determining the probability of collision between the primary and non-primary principals comprises estimating a respective overall bounding box in the logical 3D space which encloses a plurality of geometric objects representing a plurality of future states of the primary or non-primary principal;

and

wherein the method further comprises determining whether the overall bounding boxes for the primary and non-primary principals intersect.

10. The method of claim 1, further comprising determining a time of collision between the primary and non-primary principals.

11. The method of claim 10,

wherein determining the time of collision comprises determining the time when the geometric objects for the primary and non-primary principals first intersect.

12. The method of claim 10, further comprising determining a safe time to warn a user based on the time of collision and at least one of:

a user reaction time and a safe time to stop.

13. The method of claim 1, further comprising evaluating a collision severity.

14. The method of claim 13, further comprising initializing a probability-based assessment process based on the collision severity.

15. A system for facilitating assessment of collision between a primary principal and a non-primary principal for early warning, the system comprising:

a receiving mechanism configured to receive information which indicates a state of the primary principal and a state of the non-primary principal;

a time-division mechanism configured to divide future time into a number of time intervals;

a computation mechanism configured to estimate a number of possible future states of the primary and non-primary principals, wherein each future state corresponds to a time interval;

a representation mechanism configured to represent the possible future states of the primary or non-primary principal as one or more 3-dimensional geometric objects in a space of which at least one dimension indicates the time, wherein a 3-dimensional geometric object indicates a location where the principal may be at a given time interval; and

a decision mechanism configured to determine a probability of collision between the primary and non-primary principals, which involves determining whether 3-dimensional geometric objects for the primary and non-primary principals intersect.

16. The system of claim 15,

wherein a projection of the 3-dimensional geometric object on the X-Y plane indicates the location of the principal;

and

wherein the Z-position of the 3-dimensional geometric object indicates the future time at which the principal is within the location corresponding to the geometric object.

17. The system of claim 15,

wherein a geometric object comprises a bounding box that covers possible future locations of a principal at one or more future times.

18. The system of claim 15,

wherein a geometric object comprises a prismatoid;

wherein the bottom of the prismatoid corresponds to the possible location of the primary or non-primary principal at the beginning of a time interval; and

wherein the top of the prismatoid corresponds to the possible location of the primary or non-primary principal at the end of the time interval.

19. The system of claim 15,

wherein while determining the probability of collision between the primary and non-primary principals, the decision mechanism is configured to determine an overlap between two geometric objects which correspond to the primary and non-primary principals respectively and which correspond to the same time interval.

20. The system of claim 15,

wherein while determining the probability of collision between the primary and non-primary principals, the decision mechanism is configured to estimate a respective bounding box which encloses the geometric object representing a future state of the primary or non-primary principal;

and

wherein the decision mechanism is further configured to determine whether any of the bounding boxes for the primary and non-primary principals intersect.

21. The system of claim 20,

wherein if two bounding boxes intersect, the decision mechanism is further configured to determine whether in the geometric objects within the two bounding boxes intersect.

22. The system of claim 20,

wherein the probability of collision is computed based on the amount of overlap between the bounding boxes.

23. The system of claim 15,

wherein while determining the probability of collision between the primary and non-primary principals, the decision mechanism is configured to:

estimate a respective overall bounding box in the logical 3D space

which encloses a plurality of geometric objects representing a plurality of future states of the primary or non-primary principal; and

to determine whether the overall bounding boxes for the primary and non-primary principals intersect.

24. The system of claim 15,

wherein the decision mechanism is further configured to determine a time of collision between the primary and non-primary principals.

25. The system of claim 24,

wherein while determining the time of collision, the decision mechanism is configured to determine the time when the geometric objects for the primary and non-primary principals first intersect.

26. The system of claim 24,

wherein the decision mechanism is configured to determine a safe time to warn a user based on the time of collision and at least one of:

a user reaction time and a safe time to stop.

27. The system of claim 15, further comprising an evaluation mechanism configured to evaluate a collision severity.

28. The system of claim 27, further comprising an initialization mechanism configured to initialize a probability-based assessment process based on the collision severity.

29. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for facilitating assessment of collision between a primary principal and a non-primary principal for early warning, the method comprising:

receiving information which indicates a state of the primary principal and a state of the non-primary principal;

dividing future time into a number of time intervals;

estimating a number of possible future states of the primary and non-primary principals, wherein each future state corresponds to a time interval;

representing the possible future states of the primary or non-primary principal as one or more 3-dimensional geometric objects in a space of which at least one dimension indicates the time, wherein a 3-dimensional geometric object indicates a location where the principal may be at a given time interval; and

determining a probability of collision between the primary and non-primary principals, which involves determining whether 3-dimensional geometric objects for the primary and non-primary principals intersect.