Mini-Map-Matching for Navigation Systems

• US 20130151146A1
• Filed: 12/08/2011
• Published: 06/13/2013
• Est. Priority Date: 12/08/2011
• Status: Active Grant

• Current Assignee: Qualcomm technologies international, ltd. (Qualcomm, Inc.)
• Original Assignee: CSR Technology Incorporated (Qualcomm, Inc.)
• Inventors: Colley, Jaime B., Witanis, Stefan, Syed, Qutub Salman, Macaulay, Terence Douglas
• Granted Patent: US 9,075,141 B2
• Time in Patent Office: Days
• US Class Current: 701/446
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G01S 19/40 Correcting position, velocity or attitude
• CPC Class Codes: G01S 19/49 whereby the further system is an inertial position system, e.g. loosely-coupled

Abstract

The present invention uses a map database which is created with the view of optimization in terms of size and complexity, so that it can be easily embedded into a navigation chip. The optimized map database is referred to as a “mini-map” database. The mini-map database easily integrates with the position calculation routine. The algorithm for position calculation includes a map-matching component, which is referred to as the “mini-map-matching” (MMM) algorithm, which is implemented on the navigation chip. Application of the present invention includes any navigation system for vehicles and/or pedestrians. The navigation system may include an inertial sensor, such as a dead-reckoning (DR) sensor, for further improvement in calculated positional accuracy when satellite signals are degraded due to environmental factors.

Claims

1. A method for determining location of a navigation device, the method comprising:

embedding a map database for selected geographic areas into a memory section of a navigation chip that executes a navigation algorithm, wherein the map database comprises a reduced set of map data corresponding to each of the selected geographic areas;

calculating an initial location of the navigation device using signals from a navigation satellite system received by the navigation chip;

determining whether the calculated initial location falls within one of the selected geographic areas;

initiating a map-matching algorithm executed at a processor included in the navigation chip to calculate a map-matched solution, if it is determined that the calculated initial location falls within one of the selected geographic areas;

determining whether the map-matched solution is acceptable by a map-matching feedback logic included in the navigation algorithm; and

overwriting the calculated initial location of the navigation device with the map-matched solution that indicates the location of the navigation device with improved accuracy.

2. The method of claim 1, wherein while calculating the initial location, data from a dead-reckoning sensor is utilized.

3. The method of claim 1, wherein data from a dead-reckoning sensor is utilized while calculating the map-matched solution.

4. The method of claim 1, wherein prior to embedding the map database, the following steps are performed:

identifying a geographic area where the signals from the navigation satellite system is degraded;

selecting the geographic area as one of the geographic areas for which a reduced set of map data is to be included in the map database;

identifying the respective reduced set of map data that represents a corresponding geographic area; and

creating the map database to be embedded into the memory section of the navigation chip.

5. The method of claim 1, wherein the reduced set of map data includes one or more of:

nodes representing road intersections, nodes representing end points of road segments, nodes representing geographic landmarks;

nodes representing meeting point of two or more roads;

nodes representing internal points within a traffic plaza; and

, lines representing road segments connected to the nodes.

6. The method of claim 1, wherein if it is determined that the calculated initial location does not fall within one of the selected geographic areas, then outputting the calculated initial location as the final location of the navigation device.

7. The method of claim 1, wherein the method further comprises:

updating a navigation state information with the map-matched solution for a next epoch.

8. The method of claim 1, wherein the map-matching algorithm includes one or both of a tracking mode and a first-fix mode.

9. The method of claim 1, wherein the map-matching algorithm is configured to switch between a first-fix mode to a tracking mode.

10. The method of claim 1, wherein the map-matching feedback logic interfaces the map-matching algorithm within the navigation algorithm.

11. The method of claim 1, wherein accuracy of the determined location of the navigation device is further improved by using one or both of Wi-Fi augmentation, and cell-triangulation.

12. A navigation device, comprising:

a navigation chip that executes a navigation algorithm to calculate an initial location of the navigation device using signals received from a navigation satellite system;

a map database for selected geographic areas embedded into a memory section of the navigation chip, wherein the map database comprises a reduced set of map data corresponding to each of the selected geographic areas;

wherein the navigation chip further determines whether the calculated initial location falls within one of the selected geographic areas;

initiates a map-matching algorithm executed at a processor included in the navigation chip to calculate a map-matched solution, if it is determined that the calculated initial location falls within one of the selected geographic areas;

determines whether the map-matched solution is acceptable by a map-matching feedback logic included in the navigation algorithm; and

, overwrites the calculated initial location of the navigation device with the map-matched solution that indicates the location of the navigation device with improved accuracy.

13. The navigation device of claim 12, wherein the memory section of the navigation chip includes non-volatile FLASH memory coupled to the processor.

14. The navigation device of claim 12, wherein device further comprises a dead-reckoning sensor for further improving accuracy of the calculated location of the navigation device.

15. The navigation device of claim 12, wherein the device further comprises Wi-Fi augmentation for further improving accuracy of the calculated location of the navigation device.

16. The navigation device of claim 12, wherein the device further comprises cell-triangulation augmentation for further improving accuracy of the calculated location of the navigation device.

17. The device of claim 12, wherein the map database comprises a reduced set of map data, including one or more of:

nodes representing road intersections, nodes representing end points of road segments, nodes representing geographic landmarks;

nodes representing meeting point of two or more roads;

nodes representing internal points within a traffic plaza; and

, lines representing road segments connected to the nodes.

18. The device of claim 12, wherein the map-matching algorithm includes one or both of a tracking mode and a first-fix mode.

19. The device of claim 12, wherein the map-matching algorithm is configured to switch between a first-fix mode to a tracking mode.

20. The device of claim 12, wherein the map-matching feedback logic interfaces the map-matching algorithm within the navigation algorithm.