Methods and systems for map matching

Patent metadata

Field	Value
Publication number	US-11118914-B2
Application number	US-201716318853-A
Country	US
Kind code	B2
Filing date	Jul 28, 2017
Priority date	Jul 29, 2016
Publication date	Sep 14, 2021
Grant date	Sep 14, 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 indicative of the movement of the device, the positional data comprising a plurality of position data samples indicative of the position of the device at different times;
obtaining electronic map data in respect of at least a portion of the area covered by the electronic map; and
maintaining a pool of candidate paths with respect to the electronic map, each candidate path being a possible path through the electronic map to which the current position of the device may be matched, each candidate path comprising one or more segments of the electronic map, wherein said maintaining further comprises updating the pool of candidate paths by expanding one or more of the candidate paths to provide an expanded candidate path including at least a segment connected to the segment providing a head end of the original candidate path,
wherein the method further comprises:
identifying a candidate path from the pool which provides the best match to the positional data, based on a plurality of said position data samples;
using the identified candidate path in obtaining an estimated current position of the device with respect to a segment 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 , wherein the position data samples are time stamped position data samples.

3. The method of claim 1 , wherein the step of expanding a candidate path is triggered when the most recent map matched position of the device is in proximity to the head end of the path.

4. The method of claim 1 , comprising actively managing the pool of candidate paths, optionally by discarding paths and/or reducing the length of candidate paths.

5. The method of claim 1 , comprising matching the positional data to each one of a plurality of the candidate paths of the candidate path pool based on a plurality of the position data samples, wherein the matching process is carried out independently for each candidate path.

6. The method of claim 1 , comprising, for each candidate path considered, matching the positional data to the candidate path according to each of a plurality of matching criteria, wherein the matching in respect of each criteria is carried out independently.

7. The method of claim 6 , wherein the matching in respect of each criteria is carried out by an independent matching engine.

8. The method of claim 6 , wherein the method comprises providing, for each candidate path considered, a score indicative of the extent to which the positional data matches the candidate path, and ranking the candidate paths based at least on their respective scores.

9. The method of claim 8 , wherein, for each candidate path, a respective score indicative of the extent to which the positional data matches the candidate path is obtained for each one of the matching criteria, and the method comprises combining each score to provide an overall matching score for the candidate path.

10. The method of claim 9 , wherein the step of combining each score is carried out using a technique based on belief theory.

11. The method of claim 8 , wherein the identification of the candidate path providing the best match is based on the respective matching score for the candidate path and an offset between the positional data trace and the candidate path for each candidate path considered.

12. The method of claim 6 , wherein the criteria include at least heading and position.

13. The method of claim 6 , wherein the matching in relation to each of the criteria for a candidate path comprises the step of identifying a point on the candidate path that provides the best estimate as to the current position of the device; optionally further comprising choosing the estimated current position for output from among the estimated current position of the device on the best matching candidate path, and the estimated current position on one or more candidate paths connected thereto.

14. 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.

15. A method of matching a current position of a device to an electronic map indicative of a network of navigable elements, the electronic map comprising a plurality of segments representative of the navigable elements, the method comprising:
obtaining positional data indicative of the movement of the device, the positional data comprising a plurality of position data samples indicative of the position of the device at different times;
obtaining electronic map data in respect of at least a portion of the area covered by the electronic map; and
maintaining a pool of candidate paths with respect to the electronic map, each candidate path being a possible path through the electronic map to which the current position of the device may be matched, each candidate path comprising one or more segments of the electronic map, wherein said maintaining further comprises, upon detecting that the current position is in, or approaching a tunnel, updating the pool of candidate paths by expanding one or more of the candidate paths to provide an expanded candidate path including at least a segment connected to the segment providing a head end of the original candidate path, wherein the segment is a segment that leads to an exit of the tunnel,
wherein the method further comprises:
identifying a candidate path from the pool which provides the best match to the positional data, based on a plurality of said position data samples;
using the identified candidate path in obtaining an estimated current position of the device with respect to a segment of the electronic map for output as the map matched current position; and
generating data indicative of the map matched current position.

16. 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 the 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 indicative of the movement of the device, the positional data comprising a plurality of position data samples indicative of the position of the device at different times;
obtaining electronic map data in respect of at least a portion of the area covered by the electronic map; and
maintaining a pool of candidate paths with respect to the electronic map, each candidate path being a possible path through the electronic map to which the current position of the device may be matched, each candidate path comprising one or more segments of the electronic map, wherein said maintaining further comprises updating the pool of candidate paths by expanding one or more of the candidate paths to provide an expanded candidate path including at least a segment connected to the segment providing a head end of the original candida

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