METHODS AND SYSTEM FOR GENERATING A LANE-LEVEL MAP FOR AN AREA OF INTEREST FOR NAVIGATION OF AN AUTONOMOUS VEHICLE

1 . A system for controlling navigation of an autonomous vehicle, the system comprising:

a processor; and

a non-transitory computer readable medium comprising one or more programming instructions that, when executed by the processor, will cause the processor to:

receive information relating to a geonet that represents a portion of a map area within which an autonomous vehicle is allowed to operate, the geonet comprising a plurality of geo-coordinate pairs, each of the plurality of geo-coordinate pairs being indicative of a start location and an end location of each of a plurality of geonet elements in the geonet,

receive a lane-level map comprising a plurality of lane segments corresponding to the map area,

for each of the plurality of lane segments:

identify a match geonet element from the plurality of geonet elements,

determine a match distance between the match geonet element and that lane segment, and

select that lane segment for inclusion in the geonet upon determining that the match distance is less than a threshold distance,

generate, using one or more lane segments selected for inclusion in the geonet, an updated lane-level map that includes the geonet, and

cause the autonomous vehicle to navigate between an origin location and a destination location within the geonet by generating, using the updated lane-level map, a trajectory between the origin location and the destination location.

2 . The system of claim 1 , further comprising programming instruction that, when executed by the processor, will cause the processor to:

create a data representation of the geonet that includes an indication of the one or more lane segments selected for inclusion in the geonet; and

add the data representation to a low definition map comprising the geonet for creation of the updated lane-level map within the low definition map.

3 . The system of claim 1 , wherein the programming instructions to, for each of the plurality of lane segments, identify the match geonet element from the plurality of geonet elements comprise programming instructions that when executed by the processor, will cause the processor to identify a geo-coordinate that forms a mid-point of that lane segment.

4 . The system of claim 3 , wherein the programming instructions to, for each of the plurality of lane segments, identify the match geonet element from the plurality of geonet elements comprise programming instructions that when executed by the processor, will cause the processor to:

identify, using a spatial search algorithm, a plurality of candidate geonet elements that are within a first threshold distance of that lane segment;

determine a candidate match distance between each of the plurality of candidate geonet elements and that lane segment;

identify a candidate geonet element of the plurality of candidate geonet elements that has the least candidate match distance; and

determine that the candidate geonet element is the match geonet element.

5 . The system of claim 4 , wherein the programming instructions to determine the candidate match distance between each of the plurality of candidate geonet elements and that lane segment comprise programming instructions that, when executed by the processor, will cause the processor to determine the candidate match distance for a candidate geonet element as an average of the following:

an angular distance between a centerline of that lane segment and that candidate geonet element;

a perpendicular distance between the geo-coordinate of that lane segment and an infinite line defined by that geonet element; and

a lengthwise minimum distance along a line computed as the projection of the geo-coordinate of that lane segment onto the infinite line defined by that geonet element to each of that geonet element's endpoints.

6 . The system of claim 1 , further comprising programming instructions that, when executed by the processor, will cause the processor to:

cluster the one or more lane segments selected for inclusion in the geonet into logical groupings that form a plurality of undirected streets; and

for each of the plurality of undirected streets:

determine a median match distance as an average of match distances of all the lane segments that form that street,

determine whether the median match distance is greater than a second threshold distance, and

determine, when the median match distance is greater than the second threshold distance that all the lane segments that form that street should not be included in the geonet.

7 . The system of claim 6 , further comprising programming instructions that, when executed by the processor, will cause the processor to determine, when the median match distance is less than the second threshold distance that all the lane segments that form that street will be included in the geonet.

8 . The system of claim 6 , wherein the programming instructions to cluster the one or more lane segments selected for inclusion in the geonet into logical groupings that form the plurality of undirected streets comprise programming instructions to cause the processor to perform at least one of the following:

merge one or more lane segments to create road segments;

replace one or more lane segments with a single lane required to span a street perpendicular to traffic; or

merge road segments parallel with traffic.

9 . The system of claim 1 , further comprising programming instructions that, when executed by the processor, will cause the processor to:

identify a subset of the one or more lane segments selected for inclusion in the geonet as strongly connected lane segments by:

creating a routing graph using the one or more lane segments selected for inclusion in the geonet, and

identifying a strongly connected component of the routing graph; and

use only the identified subset for generating the updated lane-level map.

10 . The system of claim 1 , wherein each of the plurality of lane segments is represented as a polygon within the lane-level map.

11 . A method for controlling navigation of an autonomous vehicle, the method comprising, by a processor:

receiving information relating to a geonet that represents a portion of a map area within which an autonomous vehicle is allowed to operate, the geonet comprising a plurality of geo-coordinate pairs, each of the plurality of geo-coordinate pairs being indicative of a start location and an end location of each of a plurality of geonet elements in the geonet,

receiving a lane-level map comprising a plurality of lane segments corresponding to the map area,

for each of the plurality of lane segments:

identifying a match geonet element from the plurality of geonet elements,

determining a match distance between the match geonet element and that lane segment, and

selecting that lane segment for inclusion in the geonet upon determining that the match distance is less than a threshold distance,

generating, using one or more lane segments selected for inclusion in the geonet, an updated lane-level map that includes the geonet, and

causing the autonomous vehicle to navigate between an origin location and a destination location within the geonet by generating, using the updated lane-level map, a trajectory between the origin location and the destination location.

12 . The method of claim 11 , further comprising:

creating a data representation of the geonet that includes an indication of the one or more lane segments selected for inclusion in the geonet; and

adding the data representation to a low definition map comprising the geonet for creation of the updated lane-level map within the low definition map.

13 . The method of claim 11 , wherein, for each of the plurality of lane segments, identifying the match geonet element from the plurality of geonet elements comprises identifying a geo-coordinate that forms a mid-point of that lane segment.

14 . The method of claim 13 , wherein, for each of the plurality of lane segments, identifying the match geonet element from the plurality of geonet elements comprises:

identifying, using a spatial search algorithm, a plurality of candidate geonet elements that are within a first threshold distance of that lane segment;

determining a candidate match distance between each of the plurality of candidate geonet elements and that lane segment;

identifying a candidate geonet element of the plurality of candidate geonet elements that has the least candidate match distance; and

determining that the candidate geonet element is the match geonet element.

15 . The method of claim 14 , wherein determining the candidate match distance between each of the plurality of candidate geonet elements and that lane segment comprises determining the candidate match distance for a candidate geonet element as an average of the following:

an angular distance between a centerline of that lane segment and that candidate geonet element;

a perpendicular distance between the geo-coordinate of that lane segment and an infinite line defined by that geonet element; and

a lengthwise minimum distance along a line computed as the projection of the geo-coordinate of that lane segment onto the infinite line defined by that geonet element to each of that geonet element's endpoints.

16 . The method of claim 11 , further comprising:

clustering the one or more lane segments selected for inclusion in the geonet into logical groupings that form a plurality of undirected streets; and

for each of the plurality of undirected streets:

determining a median match distance as an average of match distances of all the lane segments that form that street,

determining whether the median match distance is greater than a second threshold distance, and

determining, when the median match distance is greater than the second threshold distance that all the lane segments that form that street should not be included in the geonet.

17 . The method of claim 16 , further comprising determining, when the median match distance is less than the second threshold distance that all the lane segments that form that street will be included in the geonet.

18 . The method of claim 16 , wherein clustering the one or more lane segments selected for inclusion in the geonet into logical groupings that form the plurality of undirected streets comprises performing at least one of the following:

merging one or more lane segments to create road segments;

replacing one or more lane segments with a single lane required to span a street perpendicular to traffic; or

merging road segments parallel with traffic.

19 . The method of claim 11 , further comprising:

identifying a subset of the one or more lane segments selected for inclusion in the geonet as strongly connected lane segments by:

creating a routing graph using the one or more lane segments selected for inclusion in the geonet, and

identifying a strongly connected component of the routing graph; and

use only the identified subset for generating the updated lane-level map.

20 . The method of claim 11 , wherein each of the plurality of lane segments is represented as a polygon within the lane-level map.