Navigation devices

• US 8,788,202 B2
• Filed: 07/09/2012
• Issued: 07/22/2014
• Est. Priority Date: 07/09/2009
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom International BV (TomTom NV)
• Inventors: Schilling, Heiko, Gawrilow, Ewgenij, Hilger, Moritz, Profous, Andreas, Werber, Jrgen, Pelle, Dominique
• Primary Examiner(s): MARC-COLEMAN, MARTHE Y
• Application Number:
  US13/544,028
• Publication Number:
  US 20130173152A1
• Time in Patent Office: 743 Days
• Field of Search: 701/527, 701/533, 701/410, 701/461, 701/468, 701/446, 701/517, 340/995.18, 340/995.19, 340/990, 342/357.41, 707/999.004, 707/999.1, 707/999.2, 707/999.201, 707/E17.005
• US Class Current: 701/527
• 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/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/3664 Details of the user input interface, e.g. buttons, knobs or sliders, including those provided on a touch screen; remote controllers; input using gestures
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated
• CPC Class Codes: G08G 1/096866 where the complete route is shown to the driver
• CPC Class Codes: H03M 7/3068 Precoding preceding compression, e.g. Burrows-Wheeler transformation
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4043 Adaptive prefix coding
• CPC Class Codes: H03M 7/70 Type of the data to be coded, other than image and sound
• CPC Class Codes: H03M 7/705 Unicode

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.

Claims

1. 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, the method comprising using at least one processing apparatus to process an electronic map comprising a plurality of navigable segments each representing segments of a navigable route in an area covered by the map, the method comprising:

a) dividing the map into a plurality of hierarchical regions belonging to at least a coarser level and a neighboring finer level such that each navigable segment is categorized into at least one region in each of the coarser and finer levels and wherein any one region of the coarser level contains a plurality of regions of the finer level;

b) determining, for a given destination region, the extent of a visibility area, comprising at least the coarser level region containing the destination region, by assessing whether regions close to the coarser level region containing the destination region should be added to the visibility area and adding those regions if the assessment is positive;

c) determining, for navigable segments in the visibility area of the destination region, whether a navigable segment is part of a minimum cost route to the destination region, wherein the search performed to make said determination is constrained by the visibility area;

d) arranging the search acceleration data to comprise information indicating said determination for the navigable segments; and

e) generating the map data.

2. At least one computing device arranged to perform the method of claim 1.

3. A non-transitory computer readable medium containing instructions which when read on a machine cause the machine to perform the method of claim 1.

4. Search acceleration data generated by the method of claim 1.

5. A method according to claim 1, wherein the processing of a navigation segment to determine if the navigable segment is part of a minimum cost route comprises performing a reverse search from the destination region back toward the navigable segment and includes substantially only navigable segments in the visibility area.

6. A method according to 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 CO₂ emission.

7. A method according to claim 1, wherein a time varying function is associated with at least some, and generally each, navigable segment.

8. A method according to claim 7, wherein the time varying function associated with a navigable segment represents an average speed on the navigable segment at a plurality of time intervals.

9. A method according to claim 1, comprising:

reducing the number of navigable segments to be considered in the creation of the search acceleration data by removing segments to form a core network of navigable segments.

10. A method according to claim 9 in which navigable segments are removed from the electronic map prior to the creation of the search acceleration data according to any one or more of the following criteria:

(i) removing navigable segments which fulfil a predetermined criterion related to the road property;

(ii) collapsing nodes, which occur at junctions between navigable segments, onto one another in predetermined situations; and

(iii) collapsing nodes onto one another if they have two or less than two navigable segments connected thereto.

11. A method according to claim 1, wherein the plurality of navigable segments of the electronic map each have a plurality of nodes associated therewith and each have at least one associated attribute representing a parameter of the navigable route, the at least one attribute associated with a navigable segment includes any one of the following:

(i) a type of the navigable segment;

(ii) an average speed along the navigable segment;

(iii) a length of the navigable segment; and

(iv) a connectivity of the navigable segment to other navigable segments, and wherein the categorization of each of the navigable segments uses an assessment of the least one attribute to ensure that the plurality of nodes associated with the navigable segments are balanced across the regions of the electronic map.

12. A method according to claim 1, wherein the minimum cost route is determined according to one of the following cost criterion:

shortest distance;

shortest travel time;

least environment impact;

least petrol used;

least CO₂ generated.

13. A method according to claim 1, comprising:

determining, for at least some navigable segments, whether a navigable segment is part of a minimum cost route to the destination region according to a first cost criterion and whether the navigable segment is part of a minimum cost route to the destination region according to a second cost criterion.

14. A method according to claim 1, wherein the generated map data comprises a side-file including the search acceleration data, the side-file being associated with the electronic map used to generate the side-file.

15. 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, the method comprising using at least one processing apparatus to process an electronic map comprising a plurality of navigable segments each representing segments of a navigable route in an area covered by the map, the method comprising:

a) dividing the map into a plurality of hierarchical regions at one or more levels of hierarchy;

b) processing at least some of the regions belonging to a particular level of hierarchy in the order of the level hierarchy, working from the finest level up to the coarsest, and for at least some of these regions, determining which navigable segments enter or leave that region;

c) processing at least some of the navigable segments within the map to determine at least one minimum cost route from that navigable segment to a destination region;

d) wherein the processing of a navigable segment includes performing a reverse search from the destination region back toward the navigable segment;

e) in a resulting search graph, identifying, for at least one region at the next-finer level, a set of regions at that next-finer level, such that each minimum-cost path from the given region passes through at least one of the regions of the set, resulting in a correlation matrix;

f) in the resulting search graph, identifying which navigable segments are not contained in any path from a region different from a region including the respective navigable segment to a further destination region, so they can be thought of as “

non-transit segments”

, and removing the non-transit segments for the subsequent steps in order to reduce the number of navigable segments which are considered in the subsequent steps;

g) wherein the creation of search acceleration data comprises using the correlation matrix to assign search acceleration data to the non-transit segments which have been removed in all previous steps; and

h) generating the map data.

16. At least one computing device arranged to perform the method of claim 15.

17. A non-transitory computer readable medium containing instructions which when read on a machine cause the machine to perform the method of claim 15.

18. A navigation device arranged to generate a route across an electronic map using a processor thereof, the navigation device comprising:

an electronic map comprising 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 any one region of the coarser level contains a plurality of regions of the finer level; and

search acceleration data that indicates whether 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;

wherein the processor is arranged to;

perform a route search across the electronic map;

perform, in a cost calculation at nodes processed during the search which represent navigable segments in the electronic map, an assessment of whether navigable segments connected to those nodes are marked, within the search acceleration data, as being part of a minimum cost route; and

if there are such navigable segments exploring only those navigable segments.