SYSTEMS AND METHODS OF GENERATING COMPOSITE ROUTING MAPS
Systems and methods for generating a composite map are provided. In one aspect, a method is provided that includes identifying a first node and a source node on a first map. The method further includes determining a candidate source node on a second map that corresponds to the source node on the first map. The method further includes determining a plurality of candidate nodes on the second map that potentially correspond to the first node and selecting a respective candidate node from the plurality of candidate nodes based on a similarity of a routing distance between: the respective candidate node and the candidate source node on the second map and the first node and the source node on the first map. The method may also include connecting the selected respective candidate node and the first node and combining the first map and the second map into a composite map.
1 . A method of generating a composite map that includes both high-definition (HD) map data and standard definition (SD) map data, the method comprising:
identifying, on an HD map, a first node and a source node;
determining a candidate source node on an SD map that corresponds to the source node on the HD map; and
determining a plurality of candidate nodes on the SD map that potentially correspond to the first node on the HD map;
selecting a respective candidate node, from the plurality of candidate nodes on the SD map, as corresponding to the first node of the HD map, based on a similarity of:
a routing distance between the respective candidate node on the SD map and the candidate source node on the SD map; and
a routing distance between the first node on the HD map and the source node on the HD map; and
generating a composite map that includes information from the HD map and the SD map.
2 . The method of claim 1 , further including:
identifying a target node on the HD map;
determining a candidate target node on the SD map that corresponds to the target node on the HD map,
wherein the respective candidate node on the SD map is further selected based on a similarity of:
a routing distance between the respective candidate node on the SD map and the candidate target node on the SD map; and
a routing distance between the first node on the HD map and the target node on the HD map.
3 . The method of claim 2 , wherein the source node on the HD map, the first node on the HD map, and the target node on the HD map correspond to a same physical road.
4 . The method of claim 2 , wherein:
the source node, the target node and the first node are located on a same edge;
the source node is an initial node of the edge; and
the target node is a terminal node of the edge.
5 . The method of claim 2 , further including:
determining a plurality of candidate source nodes on the SD map that potentially correspond to the source node on the HD map; and
selecting the source node on the SD map from the plurality of candidate source nodes on the SD map as corresponding to the source node on the HD map based on the similarity of the routing distance between the respective candidate node on the SD map and the source node on the SD map.
6 . The method of claim 5 , further including:
determining a plurality of candidate target nodes on the SD map that potentially correspond to the target node on the HD map; and
selecting the target node on the SD map from the plurality of candidate target nodes on the SD map as corresponding to the target node on the HD map based on the similarity of the routing distance between the respective candidate node on the SD map and the target node on the SD map.
7 . The method of claim 1 , wherein a candidate node of the plurality of candidate nodes is located on an edge that is adjacent to the first node.
8 . The method of claim 1 , wherein selecting the respective candidate node includes selecting the candidate node with a minimum difference between the routing distances on the SD map and the HD map.
9 . The method of claim 1 , wherein selecting the respective candidate node includes selecting the candidate node with a minimum of the squares of differences between the routing distances on the SD map and the HD map.
10 . The method of claim 1 , wherein determining the plurality of candidate nodes on the SD map includes generating nodes on the SD map that did not previously exist.
11 . The method of claim 1 , including:
determining the routing distance between the respective candidate node on the SD map and the source node on the SD map by making a first call to a routing engine using the source node on the SD map as an origin and the respective candidate node as a destination; and
determining the routing distance between the first node on the HD map and the source node on the HD map by making a second call to the routing engine using the source node on the HD map as an origin and the first node as a destination.
12 . The method of claim 1 , including mapping each node of the HD map to a node of the SD map.
13 . The method of claim 1 , wherein the first node corresponds to one or more of an intersection, a lane change, a lane merge, a lane division, or a turn.
14 . The method of claim 1 , wherein generating the composite map includes:
generating an edge between the first node on the HD map and the selected candidate node on the SD map, the edge connecting the first node on the HD map to the selected candidate node on the SD map, wherein the composite map includes the edge connecting the first node on the HD map to the selected candidate node on the SD map.
15 . The method of claim 1 , wherein the composite map includes an HD portion and an SD portion.
16 . The method of claim 15 , wherein generating the composite map includes combining the HD map and the SD map to enable routing between the HD portion of the composite map and the SD portion of the composite map.
17 . The method of claim 1 , wherein the composite map covers at least one geographic area that includes an SD portion and does not include an HD portion.
18 . A computer system, comprising:
one or more processors; and
memory storing one or more programs, the one or more programs storing instructions that, when executed by the one or more processors, cause the one or more processors to:
identify, on an HD map, a first node and a source node;
determine a candidate source node on an SD map that corresponds to the source node on the HD map; and
determine a plurality of candidate nodes on the SD map that potentially correspond to the first node on the HD map;
select a respective candidate node, from the plurality of candidate nodes on the SD map, as corresponding to the first node of the HD map, based on a similarity of:
a routing distance between the respective candidate node on the SD map and the candidate source node on the SD map; and
a routing distance between the first node on the HD map and the source node on the HD map; and
generate a composite map that includes information from the HD map and the SD map.
19 . A non-transitory computer readable storage medium storing instructions that, when executed by a computer system having one or more processors, cause the computer system to:
identify, on an HD map, a first node and a source node;
determine a candidate source node on an SD map that corresponds to the source node on the HD map; and
determine a plurality of candidate nodes on the SD map that potentially correspond to the first node on the HD map;
select a respective candidate node, from the plurality of candidate nodes on the SD map, as corresponding to the first node of the HD map, based on a similarity of:
a routing distance between the respective candidate node on the SD map and the candidate source node on the SD map; and
a routing distance between the first node on the HD map and the source node on the HD map; and
generate a composite map that includes information from the HD map and the SD map.