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

• US 7,809,500 B2
• Filed: 02/07/2005
• Issued: 10/05/2010
• Est. Priority Date: 02/07/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Soden, Steven L, Baribault, Gregory P, Couckuyt, Jeffrey Darren
• Primary Examiner(s): Keith; Jack
• Assistant Examiner(s): Nguyen; Chuong P
• Application Number:
  US11/052,994
• Publication Number:
  US 20060178809A1
• Time in Patent Office: 2,066 Days
• Field of Search: 340/995.25, 701/200, 701201-202, 701205-210, 701213-214
• US Class Current: 701/207
• 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 computer-implemented navigation system for resolving discrepancies between a reported location and route data, the navigation system comprising:

a memory storage; and

a processing unit coupled to the memory storage, wherein the processing unit is configured to;

receive a reported route location from a location subsystem,

determine a radius for identifying a plurality of prospective roads within the radius based on a current speed obtained from one of the navigation system, the location subsystem, and a speedometer of a vehicle in operation with the navigation system,

identify a plurality of prospective roads in the route data onto which the navigation system could resolve the reported location to the route location,

generate a plurality of aspect related scores for each identified prospective road according to a plurality of aspects of each identified prospective road,

obtain historical data corresponding to a plurality of previous route locations for each identified prospective road,

generate a historical score for each identified prospective road according to the obtained historical data,

generate an overall score for each identified prospective road according to the plurality of aspect related scores of each identified prospective road and the historical score by;

normalizing the plurality of aspect related scores of each identified prospective road and the historical score, wherein normalizing the plurality of aspect related scores of each identified prospective road and the historical score comprises translating each of the plurality of aspect related scores into a common range of values, and

weighting at least one of the plurality of aspect related scores of each identified prospective road and the historical score,

selecting a prospective road of the plurality of prospective roads 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 storage.

3. The navigation system of claim 1, wherein the processing unit is further operative to identify those roads in the route data that fall within a pre-determined radius of the reported location that is not based on the current speed.

4. The navigation system of claim 1, wherein the processing unit being operative to generate the plurality of aspect related scores for each identified prospective road according to the plurality of aspects of each identified prospective road comprises the processing unit being further operative to:

obtain a first heading for the reported location;

obtain a second heading for the prospective road;

determine a difference between the first heading for the reported location and the second heading for the prospective road; and

generate an aspect related heading score according to the difference between the first heading for the reported location and the second heading for the identified prospective road.

5. The navigation system of claim 4, wherein the processing unit being operative to generate the plurality of aspect related scores for each identified prospective road according to the plurality of aspects of each identified prospective road further comprises the processing unit being operative to:

determine a closest point on each identified prospective road to the reported location;

determine a distance between the identified closest point on each identified prospective road and the reported location; and

generate an aspect related distance score according to the distance between the identified closest point on each identified prospective road and the reported location.

6. The navigation system of claim 5, wherein the processing unit being operative to generate the plurality of aspect related scores for each identified prospective road according to the plurality of aspects of each identified prospective road further comprises the processing unit being operative to:

determine whether each identified prospective road is part of a predetermined route; and

generate an aspect related predetermined route score based on whether each identified prospective road is part of the predetermined route.

7. The navigation system of claim 6, wherein the processing unit being operative to generate the plurality of aspect related scores for each identified prospective road according to the plurality of aspects of each identified prospective road further comprises the processing unit being operative to:

obtain the current speed;

obtain an assigned road speed for each identified prospective road; and

generate an aspect related road speed score based on a difference between the assigned road speed and the current speed.

8. The navigation system of claim 7, wherein the processing unit being operative to generate the plurality of aspect related scores for each identified prospective road according to the plurality of aspects of each identified prospective road further comprises the processing unit being further operative to:

obtain a road classification for each identified prospective road; and

generate an aspect related road classification score according to a relationship of the current speed to the road classification.

9. The navigation system of claim 1, wherein the processing unit being operative to generate the overall score for each identified prospective road according to the plurality of aspect related scores of each identified prospective road further comprises the processing unit being operative to:

generate a plurality of historical scores between each identified prospective road and the historical data; and

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

10. The navigation system of claim 9, wherein the processing unit being operative to generate the historical score for each identified prospective road according to the obtained historical data comprises the processing unit being further operative to:

determine a historical prior road score according to whether each identified prospective road has been a previously selected prospective road in the historical data.

11. The navigation system of claim 10, wherein the processing unit being operative to generate the historical score for each identified prospective road according to the obtained historical data further comprises the processing unit being operative to:

obtain connectivity data for each identified prospective road; and

determine a historical connectivity score according to whether each identified prospective road is reachable from the previously selected prospective road in the historical data.

12. The navigation system of claim 11, wherein the processing unit being operative to generate historical score for each identified prospective road according to the obtained historical data further comprises the processing unit being operative to:

obtain the current speed; and

determine a historical speed score according to the current speed and a previous speed for a previous route location on each identified prospective road in the historical data.

13. The navigation system of claim 12, wherein the processing unit being operative to generate historical score for each identified prospective road according to the obtained historical data further comprises the processing unit being operative to:

obtain a current heading for the reported location;

determine a historical heading score according to a difference between the current heading for the reported location and a previous heading for a previous route location on each identified prospective road in the historical data.

14. A computer-implemented navigation system for resolving discrepancies between a reported location and route data, the navigation system comprising:

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

a memory storage; and

a processing unit coupled to the memory storage, the location subsystem, and the navigation system, wherein the processing unit is configured to;

determine a radius for identifying a plurality of prospective roads within the radius based on a current speed obtained from one of the navigation system, the location subsystem, and a speedometer of a vehicle in operation with the navigation system,

identify a plurality of prospective roads as those roads in the route data that have a road segment within the radius of the reported location,

obtain historical data corresponding to a plurality of previous route locations for each identified prospective road,

generate a plurality of aspect related scores for each identified prospective road according to a plurality of aspects of each identified prospective road,

generate a historical score for each identified prospective road according to the obtained historical data,

normalize each of the plurality of aspect related scores into a common range of values by translating each of the plurality of aspect related scores into the common range of values comparable to other scores,

determine an overall score for each prospective road according to a cumulation of the normalized aspect related scores and the historical score by weighting at least one of the plurality of aspect related scores of each identified prospective road and the historical score,

select a prospective road of the plurality of prospective roads with the best overall score, and

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

15. The navigation system of claim 14, wherein the processing unit is further operative to:

apply a predetermined weighting function to the normalized score for each identified prospective road.

16. The navigation system of claim 14, wherein the processing unit is further operative to:

generate a plurality of historical scores for each identified prospective road in relation to the reported location and according to the obtained historical data of previous route locations on each identified prospective road.

17. The navigation system of claim 14, wherein the location subsystem comprises a global positioning system (GPS) unit.

18. The navigation system of claim 14, wherein the processing unit being operative to generate the historical score for each identified prospective road according to the obtained historical data comprises the processing unit being further operative to:

determine a historical prior road score according to whether each identified prospective road has been a previously selected prospective road in the historical data.

19. The navigation system of claim 18, wherein the processing unit being operative to generate the historical score for each identified prospective road according to the obtained historical data further comprises the processing unit being operative to:

obtain connectivity data for each identified prospective road; and

determine a historical connectivity score according to whether each identified prospective road is reachable from the previously selected prospective road in the historical data.