Supervised point map matcher

Patent metadata

Field	Value
Publication number	US-11168989-B2
Application number	US-201916237945-A
Country	US
Kind code	B2
Filing date	Jan 2, 2019
Priority date	Jan 2, 2019
Publication date	Nov 9, 2021
Grant date	Nov 9, 2021

Abstract

System and methods are provided for a supervised point map matcher. The supervised point map matcher learns parameters from historical data that provide insight into the optimal probabilistic metrics that inform the bias of probes heading and distance for segments on the roadway. Probability weights for segments are generated. A more accurate path based map matching algorithm is used to identify direction and heading errors in the historical probe data. Values for the probability weights are calculated using kernel density estimation and a gaussian probability density function. The probability weights are used to improve the real time performance of the point map matcher. A confidence value is calculated as a function of the probability weights and provided with the map matched results.

First claim

The invention claimed is:

1. A method for providing a point based map matching algorithm, the method comprising:
acquiring a plurality of probe reports for a road segment, the plurality of probe reports comprising heading data and a plurality of positional points generated using global positioning systems;
map matching the plurality of positional points using a path based map matching algorithm;
map matching the plurality of positional points using a point based map matching algorithm;
determining accurately point based map matched positional points and erroneously point based map matched positional points using a comparison between the path based map matched positional points and the point based map matched positional points;
identifying a distance error value and a heading error value for each of the accurately point based map matched positional points and the erroneously point based map matched positional points;
generating, using kernel density estimation, a probability density distribution for each of the distance error values and heading error values for the accurately point based map matched positional points and the erroneously point based map matched positional points;
calculating probability weights for each of the probability density distributions; and
map matching, by the point based map matching algorithm, positioning data from a GPS (global positioning system) unit of a vehicle to the road segment; and
updating, by a navigation application, a display of a route of the vehicle based on the map matched road segment and a respective probability weight.

2. The method of claim 1 , further comprising:
calculating a confidence metric as a function of the probability weights; and
providing the confidence metric for use in real time map matching with the point based map matching algorithm.

3. The method of claim 1 , wherein the path based map matching algorithm is more accurate than the point based map matching algorithm.

4. The method of claim 1 , wherein the plurality of probe reports are for road segments include the same configuration.

5. The method of claim 1 , wherein providing the probability weights comprises:
storing the probability weights as an artifact for the road segment in a geographic database.

6. The method of claim 1 , wherein the heading data is provided by a magnetometer.

7. The method of claim 1 , wherein the probability density distributions are gaussian.

8. The method of claim 7 , wherein a respective probability weight is calculated using a mean and a variance of the respective probability density distribution.

9. A method for identify a current road segment of a vehicle traversing a roadway, the method comprising:
acquiring, by a processor, positional data and heading data of the vehicle;
identifying, by the processor, a plurality of road segments based on the positional data;
determining, by the processor, a closest point between the positional data and each of the plurality of road segments;
calculating, by the processor, a distance to the closest point for each of the plurality of road segments;
identifying, by the processor, a road segment heading for each of the plurality of road segments;
computing, by the processor, a match probability for each of the plurality of road segments as a function of the distances, road segment headings, heading data, distance weight, and heading weight; wherein the distance weight and heading weight are calculated for each road segment as a function of a kernel density estimation for a plurality of historical probe data reports;
selecting, by the processor, a road segment with the highest match probability as the current road segment for the vehicle; and
altering, by the processor, a display of a route as a function of the selected road segment.

10. The method of claim 9 , further comprising:
acquiring, by the processor, a confident metric for the road segment calculated as a function of the distance weight and heading weight; and
providing, by the processor, the confidence metric with the selected road segment to a navigation application.

11. The method of claim 10 , further comprising:
generating a vehicle guidance command based on the selected road segment and the confidence metric.

12. The method of claim 9 , wherein the positional data is acquired using a global position system.

13. The method of claim 9 , wherein the distance weight and heading weight are calculated prior to acquiring the positional data and heading data.

14. The method of claim 9 , wherein the distance weight and heading weight are stored in a geographic database as an artifact for the road segment.

15. A navigation device comprising:
a global positioning system configured to provide positional data;
a magnetometer configured to provide heading data;
a geographic database configured to store road segment heading data, distance weights, and heading weights for a plurality of road segments; wherein the distance weights and heading weights are calculated for each road segment of the plurality of road segments as a function of a kernel density estimation for a plurality of historical probe data reports; and
a map matching processor configured to identify a current road segment using a point map matcher, the positional data, the road segment heading data, the distance weights, and the heading weights.

16. The navigation device of claim 15 , further comprising
a controller configured to alter a route as a function of the identified current road segment.

17. The navigation device of claim 15 , further comprising:
a display configured to output a visual indication of the identified current road segment.

18. The navigation device of claim 15 , wherein the distance weights and heading weights are calculated based on a probability distribution function generated using kernel density estimation.

19. The navigation device of claim 15 , wherein the plurality of historical probe data reports are acquired for similarly configured road segments.

20. The navigation device of claim 15 , wherein the map matching processor is configured to generated probabilities for the plurality of road segments for the positional data; wherein the current road segment is identified as including the highest probability of the plurality of road segments.

Assignees

• Here Global Bv

Inventors

• Fowe James

Classifications

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G01C21/30 Primary

  Map- or contour-matching · CPC title

• G01C21/3415

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title

• G01C21/3819

  Road shape data, e.g. outline of a route · CPC title

• G05D1/0274

  using mapping information stored in a memory device (navigation using map-matching G01C21/30) · CPC title