Autonomous vehicle localization based on walsh kernel projection technique

Patent metadata

Field	Value
Publication number	US-10380890-B2
Application number	US-201715427973-A
Country	US
Kind code	B2
Filing date	Feb 8, 2017
Priority date	Feb 8, 2017
Publication date	Aug 13, 2019
Grant date	Aug 13, 2019

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. A set of candidate cells that surround the ADV is determined. For each candidate, a set of cells of the ADV feature space that surround the candidate cell is projected onto the map feature space using kernel projection, for one or more dimensions. Kernels can be Walsh-Hadamard vectors. Candidates having insufficient similarity are rejected. When a threshold number of non-rejected candidates remain, candidate similarity can be determined using a similarity metric. The coordinates of the most similar candidate cell are used to determine the position of the vehicle with respect to the map.

First claim

What is claimed is:

1. A computer-implemented method of determining a location of an autonomous driving vehicle (ADV) with respect to a high definition (HD) map and navigating the ADV, the method comprising:
determining a first sub-set of a plurality of candidate cells of an ADV feature space of cells surrounding the ADV, the ADV feature space derived from a three-dimensional (3D) point cloud of sensor data obtained by sensors of the ADV;
for each candidate cell in the first sub-set of the plurality of candidate cells:
determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell and an HD map feature space, by projecting the subset of the ADV feature space onto the map feature space using a first dimension projection kernel;
in response to determining that the similarity score is less than a threshold amount, marking the candidate cell as rejected, otherwise storing the similarity score in association with the candidate cell;

determining a location of the ADV with respect to the HD map feature space based at least in part on a candidate cell in the plurality of candidate cells having a highest similarity score among the plurality of candidate cells; and
navigating the ADV along a planned route, the navigating based at least in part on the determined location of the ADV with respect to the HD map.

2. The method of claim 1 , wherein determining the location of the ADV with respect to the map feature space comprises:
determining the coordinates of the candidate cell having the highest similarity score among the plurality of candidate cells that are not rejected.

3. The method of claim 1 , wherein the first sub-set of the plurality of candidate cells comprises all of the plurality of candidate cells.

4. The method of claim 1 , further comprising:
in response to the candidate cell not being marked as rejected, determining a second similarity score between the candidate cell and the map feature space by projecting the subset of the ADV feature space onto the map feature space using a second dimension projection kernel, wherein the first dimension projection kernel captures a larger portion of the similarity of the ADV feature space surrounding the candidate cell to the HD map feature space than the second dimension projection kernel captures; and
determining an updated similarity score by using the stored similarity score for the candidate cell and the second similarity score; and
in response to determining that the updated similarity score is less than the threshold amount, marking the candidate cell as rejected, otherwise storing the updated similarity score in association with the candidate cell.

5. The method of claim 4 , wherein the first and second dimension projection kernels comprise an ordered sequence of Gray-Code kernels.

6. The method claim 1 , further comprising:
determining a second sub-set of the plurality of candidate cells comprising, each candidate cell in the second subset of the plurality of candidate cells not having been rejected and not having had a similarity score stored in association with the candidate cell, and each candidate cell in the second sub-set having a median intensity and a variance in elevation;
for each candidate cell in the second sub-set:
determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and the map feature space, using the median intensity and variance in elevation.

7. The method of claim 6 , wherein determining the second sub-set is performed in response to one of:
determining that a count of candidate cells in the plurality of candidate cells, each candidate cell in the count not having been rejected and not having had a similarity score stored in association with the candidate cell, is less than a threshold number of candidate cells; or
determining that a maximum number of dimensions of projection kernels has been reached.

8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for determining a location of an autonomous driving vehicle (ADV) with respect to a high definition (HD) map, the operations comprising:
determining a first sub-set of a plurality of candidate cells of an ADV feature space of cells surrounding the ADV, the ADV feature space derived from a three-dimensional (3D) point cloud of sensor data obtained by sensors of the ADV;
for each candidate cell in the first sub-set of the plurality of candidate cells:
determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and an HD map feature space, by projecting the subset of the ADV feature space onto the map feature space using a first dimension projection kernel; and
in response to determining that the similarity score is less than a threshold amount, marking the candidate cell as rejected, otherwise storing the similarity score in association with the candidate cell;

determining a location of the ADV with respect to the HD map feature space based at least in part on a candidate cell in the plurality of candidate cells having a highest similarity score among the plurality of candidate cells; and
navigating the ADV along a planned route, the navigating based at least in part on the determined location of the ADV with respect to the HD map.

9. The medium of claim 8 , wherein determining the location of the ADV with respect to the map feature space comprises:
determining the coordinates of the candidate cell having the highest similarity score among the plurality of candidate cells that are not rejected.

10. The medium of claim 8 , wherein the first sub-set of the plurality of candidate cells comprises all of the plurality of candidate cells.

11. The medium of claim 8 , further comprising:
in response to the candidate cell not being marked as rejected, determining a second similarity score between the candidate cell and the map feature space by projecting the subset of the ADV feature space onto the map feature space using a second dimension projection kernel, wherein the first dimension projection kernel captures a larger portion of the similarity of the ADV feature space surrounding the candidate cell to the HD map feature space than the second dimension projection kernel captures; and
determining an updated similarity score by using the stored similarity score for the candidate cell and the second similarity score; and
in response to determining that the updated similarity score is less than the threshold amount, marking the candidate cell as rejected, otherwise storing the updated similarity score in association with the candidate cell.

12. The medium of claim 11 , wherein the first and second dimension projection kernels comprise an ordered sequence of Gray-Code kernels.

13. The medium claim 8 , the operations further comprising:
determining a second sub-set of the plurality of candidate cells comprising, each candidate cell in the second subset of the plurality of candidate cells not having been rejected and not having had a similarity score stored in association with the candidate cell, and each candidate cell in the second sub-set having a median intensity and a variance in elevation;
for each candidate cell in the second sub-set:
determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and the map feature space, using the median intensity and variance in elevation.

14. The medium of claim 13 , wherein determining the second sub-set is performed in response to one of:
determining that a coun

Assignees

• Baidu Usa Llc

Inventors

• Wang Quan

Classifications

• G01S19/45

  by combining measurements of signals from the satellite radio beacon positioning system with a supplementary measurement · CPC title

• G01S17/06

  Systems determining position data of a target · CPC title

• G01S5/16

  using electromagnetic waves other than radio waves · CPC title

• G01C21/30 Primary

  Map- or contour-matching · CPC title

• G01S17/89

  for mapping or imaging · CPC title