Methods and systems for map matching

Patent metadata

Field	Value
Publication number	US-12235111-B2
Application number	US-202318207561-A
Country	US
Kind code	B2
Filing date	Jun 8, 2023
Priority date	Jul 29, 2016
Publication date	Feb 25, 2025
Grant date	Feb 25, 2025

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, 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;
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 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 and leading to an exit of the tunnel;
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 expanding each of the one or more candidate paths 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 , further comprising actively managing the pool of candidate paths, said managing including discarding paths and/or reducing the length of candidate paths.

5. The method of claim 1 , further 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 is carried out independently for each candidate path.

6. The method of claim 1 , further 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 1 , 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 combining includes 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 identifying a point on the candidate path that provides the best estimate as to the current position of the device.

14. The method of claim 13 , 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.

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

16. A map matching engine that matches 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 map matching engine configured to:
obtain 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;
obtain electronic map data in respect of at least a portion of the area covered by the electronic map;
maintain 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 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 and leading to an exit of the tunnel;
identify a candidate path from the pool which provides the best match to the positional data, based on a plurality of said position data samples;
use 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
generate data indicative of the map matched current position.

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

18. The map matching engine of claim 16 , wherein the map matching engine is further configured to, for each candidate path considered:
match 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.

19. A non-transitory computer-readable storage medium storing instructions that, when executed by a map matching engine, cause the map matching engine to perform a method for 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;
maintaining a pool of candidate paths with respect to th

Assignees

• Tomtom Navigation Bv

Inventors

• Koponen Lauri
• Sun Rui

Classifications

• G01C21/3844

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

• 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/3446

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

• G01C21/30 Primary

  Map- or contour-matching · CPC title