Navigation devices

• US 9,835,466 B2
• Filed: 07/27/2015
• Issued: 12/05/2017
• Est. Priority Date: 07/09/2009
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom Navigation B.V (TomTom NV)
• Inventors: Schilling, Heiko, Gawrilow, Ewgenij, Hilger, Moritz, Profous, Andreas, Werber, Jrgen, Pelle, Dominique
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): LI, CE LI
• Application Number:
  US14/809,366
• Publication Number:
  US 20160091331A1
• Time in Patent Office: 862 Days
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures

Abstract

A method of creating map data including search acceleration data arranged to increase the speed at which a route can be planned across an electronic map comprising a plurality of navigable segments, each navigable segment representing a segment of a navigable route in the area covered by the map, wherein the method comprises:

• • a) reducing the number of navigable segments to be considered in the creation of the search acceleration data by removing navigable segments to form a core network of navigable segments;
  • b) dividing the electronic map into a set of hierarchical regions such that the or each navigable segment is categorized into at least one region in each level of the hierarchy;
  • c) using a time varying function associated with at least some, and generally each, navigable segment of the core network to determine whether that navigable segment is part of minimum cost route to at least one of the regions and recording this determination in the search acceleration data.

Claims

1. A method of generating a route across an electronic map using a processor of a computing device, comprising:

performing, by the processor, a route search across the electronic map, wherein the electronic map comprises a plurality of navigable segments representing segments of a navigable route in an area covered by the map, wherein the map is divided into a plurality of hierarchical regions belonging to at least a coarser level and a neighbouring finer level such that each navigable segment is categorized into at least one region in each of the coarser and finer levels and wherein anyone region of the coarser level contains a plurality of regions of the finer level;

performing, by the processor, in a cost calculation at nodes processed during the route search which represent navigable segments in the electronic map, an assessment of whether navigable segments connected to those nodes are marked, within search acceleration data, as being part of a minimum cost route, and if there are such navigable segments exploring only those navigable segments wherein the search acceleration data indicates that a navigable segment is part of a minimum cost route to a region, the search acceleration data for a region of the finer level being constrained to data that indicates whether a navigable segment within a visibility area of the finer level region is part of a minimum cost route to the region, the visibility area comprising the coarser level region containing the finer level region and any regions determined to be close to the coarser level region;

generating, by the processor, a minimum cost route across the electronic map from an origin to a destination based on the route search; and

providing, by the processor, at least one of;

audible navigation instructions to guide a user along the generated route via an output device and displaying the generated route via a display of the computing device.

2. The method of claim 1, in which the assessment as to whether regions are close to the coarser level region containing the destination region is based upon a predetermined criterion comprising at least one of:

graph-theoretical distance, geographical distance, travel time, fuel consumption, and CO2 emission.

3. The method of claim 1, further comprising associating a time varying function associated with at least some navigable segments.

4. The method of claim 1, wherein the time varying function associated with a navigable segment represents an average speed on the navigable segment at a plurality of time intervals.

5. The method of claim 1, wherein the search acceleration data for each segment is stored as a binary bit-vector.

6. The method of claim 5, wherein the search acceleration data for each segment comprises bits for each of the coarser and finer levels.

7. The method of claim 5, wherein calculating the search acceleration data for each segment comprises calculating the bit vector showing the minimum cost route across the network at a plurality of time periods rather than at a single time.

8. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor of a computing device, causes the computing device to perform a method for generating a route across an electronic map, comprising:

performing a route search across the electronic map, wherein the electronic map comprises a plurality of navigable segments representing segments of a navigable route in an area covered by the map, wherein the map is divided into a plurality of hierarchical regions belonging to at least a coarser level and a neighbouring finer level such that each navigable segment is categorized into at least one region in each of the coarser and finer levels and wherein anyone region of the coarser level contains a plurality of regions of the finer level;

performing, in a cost calculation at nodes processed during the route search which represent navigable segments in the electronic map, an assessment of whether navigable segments connected to those nodes are marked, within search acceleration data, as being part of a minimum cost route, and if there are such navigable segments exploring only those navigable segments wherein the search acceleration data indicates that a navigable segment is part of a minimum cost route to a region, the search acceleration data for a region of the finer level being constrained to data that indicates whether a navigable segment within a visibility area of the finer level region is part of a minimum cost route to the region, the visibility area comprising the coarser level region containing the finer level region and any regions determined to be close to the coarser level region;

generating a minimum cost route across the electronic map from an origin to a destination based on the route search; and

providing at least one of;

audible navigation instructions to guide a user along the generated route via an output device and displaying the generated route via a display of the computing device.

9. The computer-readable medium of claim 8, in which the assessment as to whether regions are close to the coarser level region containing the destination region is based upon a predetermined criterion comprising at least one of:

graphtheoretical distance, geographical distance, travel time, fuel consumption, and CO2 emission.

10. The computer-readable medium of claim 8, further comprising associating a time varying function associated with at least some navigable segments.

11. The computer-readable medium of claim 8, wherein the time varying function associated with a navigable segment represents an average speed on the navigable segment at a plurality of time intervals.

12. The computer-readable medium of claim 8, wherein the search acceleration data for each segment is stored as a binary bit-vector.

13. The computer-readable medium of claim 12, wherein the search acceleration data for each segment comprises bits for each of the coarser and finer levels.

14. The computer-readable medium of claim 12, wherein calculating the search acceleration data for each segment comprises calculating the bit vector showing the minimum cost route across the network at a plurality of time periods rather than at a single time.