Methods and systems for map matching by using two separate criteria

Patent metadata

Field	Value
Publication number	US-11054264-B2
Application number	US-201716318923-A
Country	US
Kind code	B2
Filing date	Jul 28, 2017
Priority date	Jul 29, 2016
Publication date	Jul 6, 2021
Grant date	Jul 6, 2021

Abstract

An advanced map matching algorithm is disclosed, which embeds the road topology inherently in a set of path candidates. Road connectivity is maintained even in special situations such as U-turns, reverse driving, and tunnels. Careful path candidate management is designed to reduce the candidate count while preserving well-matching candidates. Paths are treated and evaluated independently using multiple criteria, which makes the algorithm reliable and robust in different scenarios.

First claim

The invention claimed is:

1. A method of matching a current position of a device to an electronic map indicative of a network of navigable elements within a geographic area, the electronic map comprising a plurality of segments representative of the navigable elements, the method comprising:
obtaining positional data comprising a position data sample indicative of the position of the device;
obtaining electronic map data in respect of at least a portion of the area covered by the electronic map;
using a first matching engine to provide, for each of a plurality of segments in a set of segments of the electronic map, a first score based on a first criterion indicative of the likelihood that the current position may be mapped to the segment of the electronic map;
using a second matching engine to provide, for each of the plurality of segments in the set, a second score based on a second criterion indicative of the likelihood that the current position may be mapped to the segment of the electronic map, the first matching engine and the second matching engine operating independently of one another based on different first and second criteria;
using at least the first and second scores to determine, for each of the plurality of segments in the set, an overall score indicative of the likelihood that the current position may be mapped to the segment;
using the overall scores determined in respect of the plurality of segments of the electronic map to obtain an estimated current position of the device with respect to a segment of the set of segments of the electronic map for output as the map matched current position; and
generating data indicative of the map matched current position.

2. The method of claim 1 , further comprising ranking the segments based at least on the likelihood that the current position may be mapped to the segment using their respective overall scores.

3. The method of claim 1 , wherein the step of the first or second matching engine providing a first or second score indicative of the likelihood that the current position may be mapped to the segment comprises the matching engine matching the positional data to the segment based on the respective criterion of the matching engine.

4. The method of claim 1 , wherein the positional data used in the matching process includes a plurality of position data samples in respect of different times.

5. The method of claim 1 , wherein the step of determining the overall score is carried out using a technique based on belief theory.

6. The method of claim 1 , comprising identifying the segment that provides the best match to the positional data based on the overall scores.

7. The method of claim 6 , wherein the identification of the segment providing the best match is based on the respective matching score for the segment and an offset between the positional data trace and the segment.

8. The method of claim 1 , wherein the matching in relation to each of the criteria for a segment comprises the step of identifying a point on the segment that provides the best estimate as to the current position of the device.

9. The method of claim 1 , wherein the criteria include at least heading and position.

10. The method of claim 1 , wherein the matching in relation to each of the criteria comprises the step of identifying a point on the segment that provides the best estimate as to the current position of the device.

11. The method of claim 1 , further comprising inputting the generated data indicative of a map matched current position to a prediction engine for use in generating data indicative of one or more predicted updated position of the device, and using the predicted updated position data provided by the prediction engine in displaying an indication of the position of the moving device on an electronic map.

12. The method of claim 1 , wherein the first and second criteria have different sources of error.

13. A map matching engine comprising one or more processors and a memory for storing an electronic map indicative of a navigable network, the electronic map comprising a plurality of nodes connected by segments representative of navigable elements, the one or more processors being arranged to perform a method for matching a current position of a device to the electronic map, the method comprising:
obtaining positional data comprising a position data sample indicative of the position of the device;
obtaining electronic map data in respect of at least a portion of the area covered by the electronic map;
using a first matching engine to provide, for each of a plurality of segments in a set of segments of the electronic map, a first score based on a first criterion indicative of the likelihood that the current position may be mapped to the segment of the electronic map;
using a second matching engine to provide, for each of the plurality of segments in the set, a second score based on a second criterion indicative of the likelihood that the current position may be mapped to the segment of the electronic map, the first matching engine and the second matching engine operating independently of one another based on different first and second criteria;
using at least the first and second scores to determine, for each of the plurality of segments in the set, an overall score indicative of the likelihood that the current position may be mapped to the segment;
using the overall scores determined in respect of the plurality of segments of the electronic map to obtain an estimated current position of the device with respect to a segment of the set of segments of the electronic map for output as the map matched current position; and
generating data indicative of the map matched current position.

14. The map matching engine of claim 13 , wherein the engine is provided by a server and/or a navigation device.

15. A system for comprising one or more processors and a memory for storing an electronic map indicative of a network of navigable elements within a geographic area, the electronic map comprising a plurality of segments representative of the navigable elements, the one or more processors being arranged to:
obtain positional data comprising a position data sample indicative of the position of the device;
obtaining obtain electronic map data in respect of at least a portion of the area covered by the electronic map;
use a first matching engine to provide, for each of a plurality of segments in a set of segments of the electronic map, a first score based on a first criterion indicative of the likelihood that the current position may be mapped to the segment of the electronic map;
use a second matching engine to provide, for each of the plurality of segments in the set, a second score based on a second criterion indicative of the likelihood that the current position may be mapped to the segment of the electronic map, the first matching engine and the second matching engine operating independently of one another based on different first and second criteria;
use at least the first and second scores to determine, for each of the plurality of segments in the set, an overall score indicative of the likelihood that the current position may be mapped to the segment;
use the overall scores determined in respect of the plurality of segments of the electronic map to obtain an estimated current position of the device with respect to a segment of the set of segments of the electronic map for output as the map matched current position; and
generate data indicative of the map matched current position.

16. A non-transitory computer readable medium comprising instruction

Assignees

• Tomtom Navigation Bv

Inventors

• Koponen Lauri
• Sun Rui

Classifications

• G01C21/387

  Organisation of map data, e.g. version management or database structures · CPC title

• G01C21/3848

  Data obtained from both position sensors and additional sensors · CPC title

• G01C21/367 Primary

  Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker · CPC title

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/3844

  Data obtained from position sensors only, e.g. from inertial navigation · CPC title