Navigable boundary generation for autonomous vehicles

Patent metadata

Field	Value
Publication number	US-11428536-B2
Application number	US-201916721516-A
Country	US
Kind code	B2
Filing date	Dec 19, 2019
Priority date	Dec 19, 2018
Publication date	Aug 30, 2022
Grant date	Aug 30, 2022

Abstract

A system accesses a three-dimensional map of a geographic region and generates a two-dimensional projection of the road based on the three-dimensional map. The two-dimensional projection comprises a plurality of points along the road and each point is assigned a score measuring a navigability of the point. Based on the navigability score of each point and history of vehicle positions on the road, the system identifies a plurality of navigable points on the two-dimensional projection of the road. Based on the plurality of navigable points, the system determines a navigable surface corresponding to a physical area over which a vehicle may safely navigate and navigable surface boundaries surrounding that area. The navigable surface area and boundaries on the two-dimensional projection are converted into a three-dimensional representation, which the system uses to generate an updated three-dimensional map of the geographic region.

First claim

What is claimed is:

1. One or more non-transitory computer readable storage media storing instructions that, in response to being executed by one or more processors, cause a system to perform operations, the operations comprising:
receiving high definition (HD) map data comprising a three-dimensional representation of a road and one or more structures around the road;
generating a projection of the road from the HD map data comprising a plurality of points along the road and the structures around the road, wherein each point is assigned a navigability score measuring a navigability of the point;
identifying, based on the navigability score assigned to each point, a plurality of navigable points on the projection of the road;
determining, based on the plurality of navigable points, a navigable surface boundary corresponding to a physical area that lies outside the road such that a vehicle may safely navigate within the physical area;
storing updated HD map data of the road overlaid with a projection of the navigable surface boundary; and
causing a vehicle to perform one or more driving operations based on the navigable surface boundary included in the updated HD map data.

2. The one or more non-transitory computer readable storage media of claim 1 , wherein the projection of the road is a grid, each point on the grid mapping two a three-dimensional voxel of the HD map data.

3. The one or more non-transitory computer readable storage media of claim 1 , wherein generating a projection of the road from the HD map data comprises:
for each point on the projection,
identifying one or more neighboring points within a threshold distance;
determining a normal vector based on the one or more neighboring points; and
determining the navigability score assigned to the point based on a difference between the determined normal vector for the point and a height vector of the point.

4. The one or more non-transitory computer readable storage media of claim 1 , wherein each navigable point represents a historical position of a vehicle on the road.

5. The one or more non-transitory computer readable storage media of claim 1 , wherein identifying the plurality of navigable points on the projection comprises:
accessing a history of traffic navigating along the road of the HD map data, wherein the history of traffic comprises a plurality of vehicles positioned along the road;
aligning each position of a vehicle with the projection of the road; and
identifying, from the accessed history, points on the road over which a vehicle navigated, the identified points labeled as a navigable surface and each remaining point labeled as a non-navigable surface.

6. The one or more non-transitory computer readable storage media of claim 1 , wherein determining the navigable surface boundary comprises:
for each navigable point of the plurality of navigable points on the projection,
identifying a plurality of points neighboring the navigable point;
identifying, from the plurality of neighboring points, a first set of navigable points and a second set of non-navigable points;
determining a region of navigable space within the projection of the road based on the first set of navigable points; and
generating a closed contour around the navigable space to define the navigable surface boundary.

7. The one or more non-transitory computer readable storage media of claim 1 , wherein the navigable surface boundary is determined based on one or more of the following:
a type of vehicle; or
a height of an object suspended over the road.

8. The one or more non-transitory computer readable storage media of claim 1 , wherein the operations further comprise:
mapping each navigable point of the navigable surface boundary on the projection to a three-dimensional node of the HD map data; and
for a first mapped three-dimensional node,
identifying at least a set of neighboring three-dimensional nodes, each neighboring node mapped to a point on the navigable surface boundary in the projection that is connected to the point of the first mapped three-dimensional node;
generating a three-dimensional representation of the navigable surface boundary by connecting the first mapped three-dimensional node with each neighboring three-dimensional node of the set; and
overlaying the HD map data with the three-dimensional representation of the navigable surface boundary to generate the updated HD map data.

9. The one or more non-transitory computer readable storage media of claim 8 , wherein the operations further comprise:
determining, for each point of the navigable surface boundary in the projection, a navigability score describing a confidence that the point is navigable;
for each navigable point, assigning the navigability score to a three-dimensional node of the HD map data to which the navigable point is mapped; and
responsive to a navigability score of a neighboring three-dimensional node exceeding a threshold, connecting the neighboring three-dimensional node to a first mapped three-dimensional node to form a section of the navigable surface boundary.

10. The one or more non-transitory computer readable storage media of claim 8 , wherein the operations further comprise:
applying one or more filtering techniques to refine regions of the determined navigable surface boundary;
determining, for each point of a navigable surface boundary in the projection, latitude, longitude, and altitude values; and
mapping each point to a three-dimensional node based on the latitude, longitude, and altitude values for the point.

11. The one or more non-transitory computer readable storage media of claim 1 , wherein the navigable surface boundary is one of a plurality of navigable surface boundaries, wherein the operations further comprise determining a navigability score for each navigable surface boundaries, the navigability score indicating a level of difficulty of driving on a surface adjacent to the navigable surface boundary.

12. The one or more non-transitory computer readable storage media of claim 11 , wherein the plurality of navigable surface boundaries divide a region into a plurality of navigable surfaces, each navigable surface associated with a level of difficulty of driving a vehicle on the navigable surface.

13. A computer implemented method comprising:
a receiving high definition (HD) map data comprising a three-dimensional representation of a road and one or more structures around the road;
generating a projection of the road from the HD map data comprising a plurality of points along the road and the structures around the road, wherein each point is assigned a navigability score measuring a navigability of the point;
identifying, based on the navigability score assigned to each point, a plurality of navigable points on the projection of the road;
determining, based on the plurality of navigable points, a navigable surface boundary corresponding to a physical area that lies outside the road such that a vehicle may safely navigate within the physical area;
storing updated HD map data of the road overlaid with a projection of the navigable surface boundary; and
causing a vehicle to perform one or more driving operations based on the navigable surface boundary included in the updated HD map data.

14. The computer implemented method of claim 13 , wherein the projection of the road is a grid, each point on the grid mapping two a three-dimensional voxel of the HD map data.

15. The computer implemented method of claim 13 , wherein generating a projection of the road from the HD map data further comprises:
for each point on the projec

Assignees

• Deepmap Inc
• Nvidia Corp

Inventors

• Miller Derek Thomas
• Yang Lin
• Wheeler Mark Damon

Classifications

• G05D1/246

  using environment maps, e.g. simultaneous localisation and mapping [SLAM] · CPC title

• G05D1/617

  Safety or protection, e.g. defining protection zones around obstacles or avoiding hazards (arrangements for controlling the position or course of two or more vehicles for avoiding collisions therebetween G05D1/693; arrangements for reacting to or preventing system or operator failure G05D1/80) · CPC title

• G01C21/3815 Primary

  Road data · CPC title

• G01C21/3874

  Structures specially adapted for data searching and retrieval · CPC title

• G01C21/3881

  Tile-based structures · CPC title