Navigable boundary generation for autonomous vehicles

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 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.

16. The computer implemented method of claim 13 , wherein each navigable point represents a historical position of a vehicle on the road.

17. The computer implemented method of claim 13 , 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.

18. The computer implemented method of claim 13 , 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.

19. The computer implemented method of claim 13 , 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.

20. The computer implemented method of claim 13 , further comprising:

mapping each navigable point of the navigable surface boundary on the projection to a three-dimensional node of the HD map data;

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.

21. The computer implemented method of claim 20 , further comprising:

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.

22. The computer implemented method of claim 20 , further comprising:

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.

23. The computer implemented method of claim 13 , wherein the navigable surface boundary is one of a plurality of navigable surface boundaries, the method further comprising 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.

24. The computer implemented method of claim 23 , 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.

25. A computer system comprising:

one or more processors to perform operations, the operations; and

one or more non-transitory computer readable storage media storing instructions that, in response to being executed by one or more processors, cause the 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.

26. The computer system of claim 25 , 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.

27. The computer system of claim 25 , 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.

28. The computer system of claim 25 , wherein each navigable point represents a historical position of a vehicle on the road.

29. The computer system of claim 25 , wherein identifying the plurality of navigable points on the projection comprises:

accessing a history of traffic navigating along the road of the HD map, 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.

30. The computer system of claim 25 , 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.

31. The computer system of claim 25 , 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.

32. The computer system of claim 25 , 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;

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.

33. The computer system of claim 32 , 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.

34. The computer system of claim 32 , 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.

35. The computer system of claim 25 , 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.

36. The computer system of claim 35 , 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.