Change detection using curve alignment

• US 10,627,816 B1
• Filed: 10/31/2017
• Issued: 04/21/2020
• Est. Priority Date: 08/29/2014
• Status: Active Grant

• Current Assignee: Waymo LLC (Alphabet Inc.)
• Original Assignee: Waymo LLC (Alphabet Inc.)
• Inventors: Silver, David Harrison, Ferguson, David I.
• Primary Examiner(s): Lonsberry, Hunter B
• Assistant Examiner(s): Martinez Borrero, Luis A
• Application Number:
  US15/799,304
• Time in Patent Office: 903 Days
• Field of Search: 701 23, 701301, 701408, 701409
• CPC Class Codes: B60W 30/0956 the prediction being responsive to traffic or environmental parameters
• CPC Class Codes: B60W 30/10 Path keeping cruise control for automatically following a preceding vehicle B60W30/165
• CPC Class Codes: B60W 30/18159 Traversing an intersection
• CPC Class Codes: B60W 60/0016 of the vehicle or its occupants
• CPC Class Codes: B62D 6/00 Arrangements for automatically controlling steering depending on driving conditions sensed and responded to, e.g. control circuits means for initiating a change in direction B62D1/00; steering valves B62D5/06; combined with means for inclining the vehicle body or wheels on bends B62D9/00
• CPC Class Codes: G01C 21/32 Structuring or formatting of map data
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0214 in accordance with safety or protection criteria, e.g. avoiding hazardous areas monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13
• CPC Class Codes: G08G 1/16 Anti-collision systems road vehicle drive control systems for predicting or avoiding probable or impending collision otherwise than by control of a particular sub-unit B60W30/08

Abstract

Aspects of the disclosure relate to determining whether a feature of map information. For example, data identifying an object detected in a vehicle'"'"'s environment and including location coordinates is received. This information is used to identify a corresponding feature from pre-stored map information based on a map location of the corresponding feature. The corresponding feature is defined as a curve and associated with a tag identifying a type of the corresponding object. A tolerance constraint is identified based on the tag. The curve is divided into two or more line segments. Each line segment has a first position. The first position of a line segment is changed in order to determine a second position based on the location coordinates and the tolerance constraint. A value is determined based on a comparison of the first position to the second position. This value indicates a likelihood that the corresponding feature has changed.

Claims

1. A computer-implemented method comprising:

receiving, by one or more computing devices, data identifying a lane line detected in a vehicle'"'"'s environment, the data including location coordinates for the lane line;

identifying, by the one or more computing devices, a related feature used to define the lane line from pre-stored map information based on the location coordinates and a map location of the related feature, the related feature being associated with a tag identifying a type of the related feature;

identifying, by the one or more computing devices, at least one tolerance constraint based on the tag, the at least one tolerance constraint limiting an amount the type of the related feature can be changed;

aligning, by the one or more computing devices, the related feature with the location coordinates for the lane line by repositioning the related feature;

generating, by the one or more computing devices, a probability value that the related feature has moved based on a comparison of location coordinates for the repositioned related feature and the location coordinates for the related feature; and

using, by the one or more computing devices, the probability value and the at least one tolerance constraint to maneuver the vehicle in an autonomous driving mode.

2. The computer-implemented method of claim 1, further comprising:

dividing, by the one or more computing devices, the related feature into two or more line segments;

aligning, by the one or more computing devices, each line segment of the two or more line segments with location coordinates of corresponding portions of the lane line, by repositioning each line segment of the two or more line segments of the related feature; and

generating, by the one or more computing devices, a probability value that the related feature has moved based on a comparison of location coordinates for each repositioned line segment of the two or more line segments of the related feature and the location coordinates for each line segment of the two or more line segments of the related feature.

3. The computer-implemented method of claim 1, wherein the related feature is identified based on whether a distance between the location coordinates and the map location satisfies a threshold.

4. The computer-implemented method of claim 1, further comprising comparing the probability value to one or more threshold values to determine whether the related feature no longer exists.

5. The computer-implemented method of claim 1, further comprising comparing the probability value to one or more threshold values to determine that the lane line has been newly added to the vehicle'"'"'s environment and does not have a related feature identified from the pre-stored map information.

6. The computer-implemented method of claim 5, wherein characteristics of the newly added lane line are determined from characteristics of another lane line having different location coordinates stored in the pre-stored map information.

7. The computer-implemented method of claim 5, wherein the newly added lane line is used to determine that an object in a vicinity of the newly added lane line is a new object that does not have a related feature identified from the pre-stored map information.

8. The computer-implemented method of claim 1, further comprising comparing the probability value to one or more threshold values to determine whether the related feature has been shifted in a lateral manner.

9. The computer-implemented method of claim 1, wherein the at least one tolerance constraint is a soft constraint associated with a penalty applied to a segment when it rotates or shifts greater than a predetermined threshold.

10. A system comprising one or more computing devices, each having one or more processors configured to:

receive data identifying a lane line detected in a vehicle'"'"'s environment, the data including location coordinates for the lane line;

identify a related feature used to define the lane line from pre-stored map information based on the location coordinates and a map location of the related feature, the related feature being associated with a tag identifying a type of the related feature;

identify, by the one or more computing devices, at least one tolerance constraint based on the tag, the at least one tolerance constraint limiting an amount the related feature can be changed;

align the related feature with the location coordinates for the lane line by repositioning the related feature;

generate a probability value that the related feature has moved based on a comparison of location coordinates for the repositioned related feature and the location coordinates for the related feature; and

use the probability value and the at least one tolerance constraint to maneuver the vehicle in an autonomous driving mode.

11. The system of claim 10, wherein the one or more processors is further configured to:

divide the related feature into two or more line segments;

align each line segment of the two or more line segments with location coordinates of corresponding portions of the lane line, by repositioning each line segment of the two or more line segments of the related feature; and

generate a probability value that the related feature has moved based on a comparison of location coordinates for each repositioned line segment of the two or more line segments of the related feature and the location coordinates for each line segment of the two or more line segments of the related feature.

12. The system of claim 10, wherein the related feature is identified based on whether a distance between the location coordinates and the map location satisfies a threshold.

13. The system of claim 10, wherein the one or more processors is further configured to compare the probability value to one or more threshold values to determine whether the related feature no longer exists.

14. The system of claim 10, wherein the one or more processors is further configured to compare the probability value to one or more threshold values to determine that the lane line has been newly added to the vehicle'"'"'s environment and does not have a related feature identified from the pre-stored map information.

15. The system of claim 14, wherein characteristics of the newly added lane line are determined from characteristics of another lane line having different location coordinates stored in the pre-stored map information.

16. The system of claim 14, wherein the newly added lane line is used to determine that an object in a vicinity of the newly added lane line is a new object that does not have a related feature identified from the pre-stored map information.

17. The system of claim 10, wherein the one or more processors is further configured to compare the probability value to one or more threshold values to determine whether the related feature has been shifted in a lateral manner.

18. The system of claim 10, further comprising the vehicle.

19. The system of claim 10, wherein the at least one tolerance constraint is a soft constraint associated with a penalty applied to a segment when it rotates or shifts greater than a predetermined threshold.

20. A non-transitory, tangible computer readable medium on which instructions are stored, the instructions, when executed by one or more processors cause the one or more processors to perform a method, the method comprising:

receiving, by one or more computing devices, data identifying a lane line detected in a vehicle'"'"'s environment, the data including location coordinates for the lane line;

identifying a related feature used to define the lane line from pre-stored map information based on the location coordinates and a map location of the related feature, the related feature being associated with a tag identifying a type of the related feature;

identifying, by the one or more computing devices, at least one tolerance constraint based on the tag, the at least one tolerance constraint limiting an amount the related feature can be changed;

aligning the related feature with the location coordinates for the lane line by repositioning the related feature;

generating a probability value that the related feature has moved based on a comparison of location coordinates for the repositioned related feature and the location coordinates for the related feature; and

using the probability value and the at least one tolerance constraint to maneuver the vehicle in an autonomous driving mode.

21. The medium of claim 20, further comprising:

dividing the related feature into two or more line segments;

aligning each line segment of the two or more line segments with location coordinates of corresponding portions of the lane line, by repositioning each line segment of the two or more line segments of the related feature; and

generating a probability value that the related feature has moved based on a comparison of location coordinates for each repositioned line segment of the two or more line segments of the related feature and the location coordinates for each line segment of the two or more line segments of the related feature.

22. The medium of claim 20, wherein the related feature is identified based on whether a distance between the location coordinates and the map location satisfies a threshold.

23. The medium of claim 20, wherein the at least one tolerance constraint is a soft constraint associated with a penalty applied to a segment when it rotates or shifts greater than a predetermined threshold.