Resolving discrepancies between location information and route data on a navigation device

• US 20060178809A1
• Filed: 02/07/2005
• Published: 08/10/2006
• Est. Priority Date: 02/07/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Soden, Steven L., Couckuyt, Jeffrey Darren, Baribault, Gregory P.
• Granted Patent: US 7,809,500 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

A navigation system and method for resolving discrepancies between a reported position and route data is presented. Based on a reported position, the navigation system identifies prospective road segments within a radius of the reported position. For each road segment, the navigation system generates a series of scores according to various attributes, including the current heading, current speed, proximity of reported location to the prospective road, and the like. Historical scores are also generated based on historical information, i.e., previous navigation device locations. Scores are normalized such that they can be compared, and optionally weighted according to particular implementation details. After scores have been generated for each prospective road, the prospective road, and its determined location, with the best score is selected as the resolved, actual location.

Claims

1. A navigation system for resolving discrepancies between a reported location and route data, the navigation system comprising:

a processor;

a memory; and

a location subsystem, wherein the location subsystem provides a reported location to the navigation system;

and wherein the navigation system is configured to resolve discrepancies between the reported location and route data into a route location on a road identified in the route data, by;

identifying prospective roads in the route data onto which the navigation system could resolve the reported location to a route location;

for each prospective road, generating a score for the prospective road in relation to the reported location;

selecting the prospective road with the best score; and

identifying a position on the selected prospective road as the resolved route location.

2. The navigation system of claim 1, wherein the route data is stored in the memory.

3. The navigation system of claim 1, wherein identifying prospective roads in the route data onto which the navigation system could resolve the reported location to the route location comprises:

identifying those roads in the route data that fall within a radius of the reported location.

4. The navigation system of claim 1, wherein generating a score for the prospective road in relation to the reported location comprises:

generating a plurality of aspect related scores between the prospective road and the reported location; and

determining an overall score based on the plurality of aspect related scores.

5. The navigation system of claim 4, wherein generating a plurality of aspect related scores between the prospective road and the reported location comprises:

obtaining a heading for the reported location;

obtaining a heading for the prospective road;

determining the difference between the heading for the reported location and the heading for the prospective road; and

generating a heading score according to the difference between the heading for the reported location and the heading for the prospective road;

6. The navigation system of claim 5, wherein generating a plurality of aspect related scores between the prospective road and the reported location further comprises:

identifying the closest point on the prospective road to the reported location;

determining the distance between the identified closest point on the prospective road and the reported location; and

generating a distance score according to distance between the identified closest point on the prospective road and the reported location.

7. The navigation system of claim 6, wherein generating a plurality of aspect related scores between the prospective road and the reported location further comprises:

determining whether the prospective road is part of a predetermined route; and

generating a predetermined route score based on whether the prospective road is part of a predetermined route.

8. The navigation system of claim 7, wherein generating a plurality of aspect related scores between the prospective road and the reported location further comprises:

obtaining a current speed;

obtaining an assigned road speed for the prospective road; and

generating a road speed score based on the difference between the assigned road speed and the current speed.

9. The navigation system of claim 8, wherein generating a plurality of aspect related scores between the prospective road and the reported location further comprises:

obtaining a road classification for the prospective road; and

generating a road classification score according to the relationship of the current speed to the road classification.

10. The navigation system of claim 4, wherein generating a score for the prospective road in relation to the reported location further comprises:

determining whether historical data exists as to previous route locations; and

if historical data exists as to previous route locations, generating a plurality of historical scores between the prospective road and the historical data; and

determining an overall score based on the plurality of aspect related scores and historical scores.

11. The navigation system of claim 10, wherein generating a plurality of historical scores between the prospective road and the historical data comprises:

determining a prior road score according to whether the prospective road is a “

snap-to”

road in the historical data.

12. The navigation system of claim 11, wherein generating a plurality of historical scores between the prospective road and the historical data further comprises:

obtaining connectivity data for the prospective road; and

determining a connectivity score according to whether the prospective road is reachable from a “

snap-to”

road in the historical data.

13. The navigation system of claim 12, wherein generating a plurality of historical scores between the prospective road and the historical data further comprises:

obtaining a current speed; and

determining a historical speed score according to the current speed and the speed for a previous route position in the historical data.

14. The navigation system of claim 13, wherein generating a plurality of historical scores between the prospective road and the historical data further comprises:

obtaining a current heading for the reported location;

determining a historical heading score according to the difference between the current heading for the reported location and the heading for a previous route position in the historical data.

15. A navigation system for resolving discrepancies between a reported location and route data, the navigation system comprising:

a processor;

a memory; and

a location subsystem, wherein the location subsystem provides a reported location to the navigation system;

and wherein the navigation system is configured to resolve discrepancies between the reported location and route data into a route location on a road identified in the route data, by;

identifying prospective roads as those roads in the route data that have a road segment within a radius of the reported location;

for each identified prospective road;

generating a plurality of scores for the prospective road in relation to the reported location;

normalizing each of the plurality of scores into a common range of values; and

determining an overall score for the prospective road according to the cumulation of the normalized scores;

selecting the prospective road with the best overall score; and

identifying a position on the selected prospective road as the route location.

16. The navigation system of claim 15 further comprising, for each identified prospective road:

applying a predetermined weighting function to a normalized score.

17. The navigation system of claim 15 further comprising:

generating a plurality of scores for the prospective road in relation to the reported location and according to historical data of previous route positions.

18. The navigation system of claim 15, wherein the location subsystem comprises a GPS unit.

19. A method, executable by a navigation system, for resolving discrepancies between a reported location and route data, the method comprising:

obtaining a reported location from a location subsystem;

obtaining route data identifying a plurality of roads;

identifying prospective roads in the route data that have a road segment within a radius of the reported location;

for each identified prospective road;

generating a plurality of scores for the prospective road in relation to the reported location;

normalizing each of the plurality of scores into a common range of values; and

determining an overall score for the prospective road according to the cumulation of the normalized scores;

selecting the prospective road with the best overall score; and

identifying a position on the selected prospective road as the resolved route location.

20. The method of claim 19 further comprising generating a plurality of scores for the prospective road in relation to the reported location and according to historical data of previous route positions.