Methods and systems for map matching

Patent metadata

Field	Value
Publication number	US-11747146-B2
Application number	US-202117396734-A
Country	US
Kind code	B2
Filing date	Aug 8, 2021
Priority date	Jul 29, 2016
Publication date	Sep 5, 2023
Grant date	Sep 5, 2023

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 in a first driving direction 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 a U-turn manoeuvre has been performed by the device, creating an additional set of candidate paths for inclusion in the pool, wherein each candidate path is a possible path in a second, opposite driving direction 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;
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 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;
maintaining a pool of candidate paths with respect to the electronic map, each candidate path being a possible path in a first driving direction 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 reverse driving is being performed, creating a new set of candidate paths to replace those in the pool, wherein each of the new candidate paths is a possible path in a second, opposite driving direction 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;
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 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 in a first driving direction 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 a U-turn manoeuvre has been performed by the device, creating an additional set of candidate paths for inclusion in the pool, wherein each candidate path is a possible path in a second, opposite driving direction 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;
identify a candidate path from the pool which provides the best match to th

Assignees

• Tomtom Navigation Bv

Inventors

• Koponen Lauri
• Sun Rui

Classifications

• G01C21/30 Primary

  Map- or contour-matching · CPC title

• G01C21/3844

  Data obtained from position sensors only, e.g. from inertial navigation · 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/3848

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