Map data validation using knowledge graphs and randomness measures

Patent metadata

Field	Value
Publication number	US-11859985-B2
Application number	US-201916547276-A
Country	US
Kind code	B2
Filing date	Aug 21, 2019
Priority date	Aug 21, 2019
Publication date	Jan 2, 2024
Grant date	Jan 2, 2024

Abstract

Systems and methods are disclosed for improved mapping data validation using randomness measures. Methods may include receiving a map dataset that includes a plurality of map features. A knowledge graph may be generated based on the map dataset that may include nodes representing or corresponding to the map features. Nodes corresponding to map features of a particular feature type may be identified and edges connected to the identified nodes may be processed to identify a plurality of paths. A randomness measure for the particular feature type may be determined based on the plurality of paths. The randomness measure may indicate a predictability of occurrences of map features of the particular feature type in the map dataset. The randomness measure may then be compared to a second randomness measure determined based on another map dataset.

First claim

The invention claimed is:

1. A method comprising:
receiving a new map dataset associated with operation of a vehicle, wherein the new map dataset includes a plurality of new map features relative to a previous map dataset;
generating, based on the new map dataset, a knowledge graph comprising a plurality of nodes reflecting the plurality of new map features;
determining one or more traversal paths along nodes and edges within the knowledge graph based on the plurality of nodes reflecting the plurality of new map features;
generating, based on the one or more traversal paths within the knowledge graph, a first entropy score for the plurality of new map features;
determining a second entropy score for a previous knowledge graph corresponding to the previous map dataset;
generating a randomness difference between the knowledge graph and the previous knowledge graph by comparing the first entropy score with the second entropy score; and
based on determining that the randomness difference satisfies a predetermined threshold, incorporating the plurality of new map features in generating a production map dataset.

2. The method of claim 1 , further comprising:
determining that a difference between a third entropy score of an additional map dataset and a fourth entropy score of the production map dataset fails to satisfy the predetermined threshold; and
excluding an additional plurality of new map features from the production map dataset.

3. The method of claim 1 , further comprising:
receiving the new map dataset from a map data provider;
determining an accuracy score corresponding to the map data provider based on the randomness difference between the first entropy score and the second entropy score; and
generating, based on the accuracy score, an accuracy profile associated with the map data provider.

4. The method of claim 1 , wherein generating a knowledge graph based on the new map dataset further comprises:
identifying the plurality of new map features within the new map dataset;
determining one or more relationships between the plurality of new map features;
generating, for each of the plurality of new map features, a node in the knowledge graph; and
generating, for each relationship of the one or more relationships, an edge between two corresponding nodes of the knowledge graph.

5. The method of claim 4 , wherein the edges of the knowledge graph designate a relationship type of each relationship between connected nodes.

6. The method of claim 5 , wherein the edge is stored as a triple comprising an identification of a first node connected by the edge, an identification of a second node connected by the edge, and a relationship type of a relationship between the first node and the second node.

7. The method of claim 1 , wherein generating the first entropy score comprises determining information entropy between a starting node and an ending node for a traversal path of the one or more traversal paths.

8. A system comprising:
one or more processors; and
a memory coupled to the one or more processor, the memory comprising instructions, which when executed by the one or more processors, cause the system to:
receive a new map dataset associated with operation of a vehicle, wherein the new map dataset includes a plurality of new map features relative to a previous map dataset;
generate, based on the new map dataset, a knowledge graph comprising a plurality of nodes reflecting the plurality of new map features;
determine one or more traversal paths along nodes and edges within the knowledge graph based on the plurality of nodes reflecting the plurality of new map features;
generate, based on the one or more traversal paths within the knowledge graph, a first entropy score for the plurality of new map features;
determine a second entropy score for a previous knowledge graph corresponding to the previous map dataset;
generate a randomness difference between the knowledge graph and the previous knowledge graph by comparing the first entropy score with the second entropy score; and
based on determining that the randomness difference satisfies a predetermined threshold, incorporate the plurality of new map features in generating a production map dataset.

9. The system of claim 8 , wherein the memory comprises further instruction which, when executed by the one or more processors, cause the system to:
determine that a difference between a third entropy score of an additional map dataset and a fourth entropy score of the production map dataset fails to satisfy the predetermined threshold; and
exclude an additional plurality of new map features from the production map dataset.

10. The system of claim 8 , wherein the memory comprises further instructions which, when executed by the one or more processors, cause the system to:
receive the new map dataset from a map data provider;
determine an accuracy score corresponding to the map data provider based on the randomness difference between the first entropy score and the second entropy score; and
generate, based on the accuracy score, an accuracy profile associated with the map data provider.

11. The system of claim 8 , wherein the memory comprises further instructions which, when executed by the one or more processors cause the system to:
identify the plurality of new map features within the new map dataset;
determine one or more relationships between the plurality of new map features;
generate, for each of the plurality of new map features, a node in the knowledge graph; and
generate, for each relationship of the one or more relationships, an edge between two corresponding nodes of the knowledge graph.

12. The system of claim 11 , wherein the edges of the knowledge graph designate a relationship type of each relationship between connected nodes.

13. The system of claim 12 , wherein the edge is stored as a triple comprising an identification of a first node connected by the edge, an identification of a second node connected by the edge, and a relationship type of a relationship between the first node and the second node.

14. The system of claim 8 , wherein the memory comprises further instruction which, when executed by the one or more processors, cause the system to generate the first entropy score by determining information entropy between a starting node and an ending node for a traversal path of the one or more traversal paths.

15. A non-transitory computer readable storage medium comprising instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
receiving a new map dataset associated with operation of a vehicle, wherein the new map dataset includes a plurality of new map features relative to a previous map dataset;
generating, based on the new map dataset, a knowledge graph comprising a plurality of nodes reflecting the plurality of new map features;
determining one or more traversal paths along nodes and edges within the knowledge graph based on the plurality of nodes reflecting the plurality of new map features;
generating, based on the one or more traversal paths within the knowledge graph, a first entropy score for the plurality of new map features;
determining a second entropy score for a previous knowledge graph corresponding to the previous map dataset;
generating a randomness difference between the knowledge graph and the previous knowledge graph by comparing the first entropy score with the second entropy score; and
based on determining that the randomness difference satisfies a predetermined threshold, incorporating the plurality of new map fea

Assignees

• Lyft Inc

Inventors

• Michener Barak
• Dedeco Thomas Michael
• Yuen Albert

Classifications

• G01C21/32 Primary

  Structuring or formatting of map data · CPC title

• G01C21/34

  Route searching; Route guidance · CPC title

• G06F16/29 Primary

  Geographical information databases · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title

• G06N5/04

  Inference or reasoning models · CPC title