ALGORITHM AND INFRASTRUCTURE FOR ROBUST AND EFFICIENT VEHICLE LOCALIZATION

• US 20180143647A1
• Filed: 11/23/2016
• Published: 05/24/2018
• Est. Priority Date: 11/23/2016
• Status: Active Grant

• Current Assignee: Baidu USA LLC (Baidu Incorporated)
• Original Assignee: Baidu USA LLC (Baidu Incorporated)
• Inventors: WANG, Quan, ZHAI, Jing
• Granted Patent: US 10,579,065 B2
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3848 Data obtained from both position sensors and additional sensors
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01S 13/86 Combinations of radar systems with non-radar systems, e.g. sonar, direction finder
• CPC Class Codes: G01S 17/06 Systems determining position data of a target
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G01S 7/4808 Evaluating distance, position or velocity 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/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Location of an autonomous driving vehicle (ADV) is determined with respect to a high definition map. On-boards sensors of the ADV obtain a 3D point cloud of objects surrounding the ADV. The 3D point cloud is organized into an ADV feature space of cells. Each cell has a median intensity value and a variance in elevation. To determine the ADV location, a coarse search of a subset of cells in the ADV feature space performed with respect to the high definition map, using a similarity metric that is based on the median intensity and variance in elevation of the candidate cell. When similarity of the first candidate cell is determined, a lookup table of similarity scores is generated and used for determining the similarity score for subsequent candidate cells. Then a fine search is performed on a small subset of candidate cells surrounding the highest similarity score cell.

Claims

1. A computer-implemented method of operating an autonomous driving vehicle (ADV), comprising:

determining a first set of a plurality of candidate cells of an ADV feature space of cells surrounding the ADV, each candidate cell in the plurality of candidate cells having a median intensity and a variance in elevation;

for each candidate cell in the plurality of candidate cells, determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and a map feature space, using a similarity metric, wherein the similarity metric is based at least in part of the candidate cell median intensity and candidate cell variance in elevation; and

determining a location of the ADV with respect to the map feature space based at least in part on a candidate cell having a highest similarity score among the first set of candidate cells.

2. The method of claim 1, wherein the first set of a plurality of candidate cells comprise every other cell of a predetermined grid of cells surrounding the ADV.

3. The method of claim 1, wherein, for a first candidate cell in the first set of a plurality of candidate cells, determining a similarity score comprises computing a similarity score using a first candidate median intensity and first candidate cell variance in elevation, and the method further comprises:

using information obtained from computing the similarity score of the first candidate cell to generate a lookup table of similarity scores.

4. The method of claim 3, wherein the lookup table is indexed by a range of mean intensity values and a range of variance in elevation values.

5. The method of claim 3, wherein for the second candidate cell, and subsequent candidate cells in the plurality of candidate cells, determining a similarity score for the candidate cell comprises looking up the similarity score in the lookup table using the median intensity and variance in elevation of the candidate cell.

6. The method of claim 1, further comprising, after determining the highest similarity score for a candidate cell:

determining second set of a plurality of fine search candidate cells surrounding the candidate cell having the highest similarity score of the first set of a plurality of candidate cells; and

for each fine search candidate cell in the second set of a plurality of fine search candidate cells;

determining a similarity score between a subset of the ADV feature space that surrounds the fine search candidate cell, and the map feature space, using the similarity metric;

determining a highest similarity for a fine search candidate cell in the plurality of fine search candidate cells; and

wherein determining the location of the ADV location within the map feature space is further based at least in part on the fine search candidate cell having the highest similarity score.

7. The method of claim 6, wherein determining the similarity score comprises computing the similarity score for each of the plurality of fine search candidate cells.

8. The method of claim 6, wherein determining the location of the ADV within the map feature space further comprises determining an offset between the ADV and the fine search candidate cell having the highest similarity score to the map feature space.

9. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations, the operations comprising:

determining a first set of a plurality of candidate cells of an ADV feature space of cells surrounding the ADV, each candidate cell in the plurality of candidate cells having a median intensity and a variance in elevation;

for each candidate cell in the plurality of candidate cells, determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and a map feature space, using a similarity metric, wherein the similarity metric is based at least in part of the candidate cell median intensity and candidate cell variance in elevation; and

determining a location of the ADV with respect to the map feature space based at least in part on a candidate cell having a highest similarity score among the first set of candidate cells.

10. The medium of claim 9, wherein the first set of a plurality of candidate cells comprise every other cell of a predetermined grid of cells surrounding the ADV.

11. The medium of claim 9, wherein, for a first candidate cell in the first set of a plurality of candidate cells, determining a similarity score comprises computing a similarity score using a first candidate median intensity and first candidate cell variance in elevation, and the operations further comprise:

using information obtained from computing the similarity score of the first candidate cell to generate a lookup table of similarity scores.

12. The medium of claim 11, wherein the lookup table is indexed by a range of mean intensity values and a range of variance in elevation values.

13. The medium of claim 11, wherein for the second candidate cell, and subsequent candidate cells in the plurality of candidate cells, determining a similarity score for the candidate cell comprises looking up the similarity score in the lookup table using the median intensity and variance in elevation of the candidate cell.

14. The medium of claim 9, further comprising, after determining the highest similarity score for a candidate cell:

determining a second set of plurality of fine search candidate cells surrounding the candidate cell having the highest similarity score of the first set of a plurality of candidate cells; and

for each fine search candidate cell in the second set of a plurality of fine search candidate cells;

determining a similarity score between a subset of the ADV feature space that surrounds the fine search candidate cell, and the map feature space, using the similarity metric;

determining a highest similarity for a fine search candidate cell in the plurality of fine search candidate cells; and

wherein determining the location of the ADV location within the map feature space is further based at least in part on the fine search candidate cell having the highest similarity score.

15. The medium of claim 14, wherein determining the similarity score comprises computing the similarity score for each of the plurality of fine search candidate cells.

16. The medium of claim 14, wherein determining the location of the ADV within the map feature space further comprises determining an offset between the ADV and the fine search candidate cell having the highest similarity score to the map feature space.

17. A data processing system, comprising:

a processor; and

a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations, the operations including;

determining a first set of a plurality of candidate cells of an ADV feature space of cells surrounding the ADV, each candidate cell in the plurality of candidate cells having a median intensity and a variance in elevation;

for each candidate cell in the plurality of candidate cells, determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and a map feature space, using a similarity metric, wherein the similarity metric is based at least in part of the candidate cell median intensity and candidate cell variance in elevation; and

determining a location of the ADV with respect to the map feature space based at least in part on a candidate cell having a highest similarity score among the first set of candidate cells.

18. The data processing system of claim 17, wherein the first set of a plurality of candidate cells comprise every other cell of a predetermined grid of cells surrounding the ADV.

19. The data processing system of claim 17, wherein, for a first candidate cell in the first set of a plurality of candidate cells, determining a similarity score comprises computing a similarity score using a first candidate median intensity and first candidate cell variance in elevation, and the operations further comprise:

using information obtained from computing the similarity score of the first candidate cell to generate a lookup table of similarity scores.

20. The data processing system of claim 19, wherein the lookup table is indexed by a range of mean intensity values and a range of variance in elevation values.

21. The data processing system of claim 19, wherein for the second candidate cell, and subsequent candidate cells in the plurality of candidate cells, determining a similarity score for the candidate cell comprises looking up the similarity score in the lookup table using the median intensity and variance in elevation of the candidate cell.

22. The data processing system of claim 17, the operations further comprising, after determining the highest similarity score for a candidate cell:

determining a second set of a plurality of fine search candidate cells surrounding the candidate cell having the highest similarity score of the first set of a plurality of candidate cells; and

for each fine search candidate cell in the second set of a plurality of fine search candidate cells;

determining a similarity score between a subset of the ADV feature space that surrounds the fine search candidate cell, and the map feature space, using the similarity metric;

determining a highest similarity for a fine search candidate cell in the plurality of fine search candidate cells; and

wherein determining the location of the ADV location within the map feature space is further based at least in part on the fine search candidate cell having the highest similarity score.

23. The data processing system of claim 22, wherein determining the similarity score comprises computing the similarity score for each of the plurality of fine search candidate cells.

24. The data processing system of claim 22, wherein determining the location of the ADV within the map feature space further comprises determining an offset between the ADV and the fine search candidate cell having the highest similarity score to the map feature space.