Method and device for correcting errors in map data

A server computer for correcting errors in map data, comprising:

• a communications interface;
• a memory interface;
• and a processing unit configured to:
• obtain the map data specifying travel possibilities between locations;
• generate a routing graph from the map data by assigning a vertex to each location and an edge from one vertex to another vertex if the map data specifies that it is possible to travel from the location to which the first vertex is assigned to the location to which the second vertex is assigned;
• identify the largest strongly connected component of the routing graph by identifying the largest component of the routing graph in which there is a path between all pairs of vertices of the component, and wherein the component is a subgraph of the routing graph;
• identify one or more additional strongly connected components of the routing graph;
• detect errors in the map data by identifying missing travel possibilities that are not in the map data which lead to missing connections between the one or more additional strongly connected components of the routing graph and the largest strongly connected component of the routing graph;
• amend the map data by the identified missing travel possibilities;
• transmit the amended map data to a vehicle to control the navigation of the vehicle;
• determine a quality indicator of the routing graph, the quality indicator based at least in part on the ratio of strongly connected components to the number of vertices in the routing graph;
• and
• store the quality indicator as time series data associated with the map data;
• wherein the processing unit is further configured to:
• monitor the quality of the map data by tracking the quality indicator over time;
• and generate an alarm signal when the quality indicator falls below a predetermined threshold.

A computer-readable medium comprising program instructions, which, when executed by one or more processors, cause the one or more processors to perform a method for correcting errors in map data, the method comprising:

• downloading, to a server, map data specifying travel possibilities between locations;
• generating a routing graph from the map data by assigning a vertex to each location and an edge from one vertex to another vertex if the map data specifies that it is possible to travel from the location to which the first vertex is assigned to the location to which the second vertex is assigned;
• identifying the largest strongly connected component of the routing graph by identifying the largest component of the routing graph in which there is a path between all pairs of vertices of the component, and wherein the component is a subgraph of the routing graph;
• identifying one or more additional strongly connected components of the routing graph;
• detecting errors in the map data by identifying missing travel possibilities that are not in the map data which lead to missing connections between the one or more further additional strongly connected components of the routing graph and the largest strongly connected component of the routing graph;
• amending the map data by the identified missing travel possibilities;
• transmitting the amended map data to a vehicle to control the navigation of the vehicle;
• determining a quality indicator of the routing graph, the quality indicator based at least in part on the ratio of strongly connected components to the number of vertices in the routing graph;
• storing the quality indicator as time series data associated with the map data;
• monitoring the quality of the map data by tracking the quality indicator over time;
• and
• generating an alarm signal when the quality indicator falls below a predetermined threshold.