Navigation device and program

• US 20100100309A1
• Filed: 08/27/2009
• Published: 04/22/2010
• Est. Priority Date: 10/16/2008
• Status: Active Grant

• Current Assignee: Aisin AW Company Limited (Aisin Corp.)
• Original Assignee: Aisin AW Company Limited (Aisin Corp.)
• Inventors: Hosoi, Yasuki, Matsuhisa, Syougo
• Granted Patent: US 8,219,313 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

Navigation devices, methods, and programs store map data hierarchically with the map data of a hierarchy level being excluded. The devices, methods, and programs read the stored map data, perform a route search within each predetermined area on a departure point side and a destination side, and acquire a shortest cost route in a range overlapped in search areas. In a hierarchy level having a proximal higher hierarchy level of which the map data does not exist, the devices, methods, and programs expand the predetermined area into a search area in the proximal higher hierarchy level and acquire a first shortest cost route, and perform the route search in a higher hierarchy level to acquire a second shortest cost route. When the second shortest cost route'"'"'s cost is smaller than the first shortest cost route'"'"'s cost, the devices, methods, and programs update the cost of the shortest cost route.

Claims

1. A navigation device that searches for a route from a departure point to a destination, comprising:

an information storage unit that stores map data in a hierarchical structure, in which the map data of at least one hierarchy level has been excluded;

a route search unit that reads the map data in the hierarchical structure from the information storage unit, performs route search within each predetermined area on a departure point side and a destination side, and acquires a shortest cost route in a range overlapped in search areas; and

a control unit that controls the route search of the route search unit, wherein

the route search unit, in the route search in a hierarchy level having a proximal higher hierarchy level of which the map data does not exist, expands the predetermined area into a search area in the proximal higher hierarchy level and performs the route search to acquire a first shortest cost route, and further performs the route search in a higher hierarchy level to acquire a second shortest cost route, and

the control unit, when a cost of the second shortest cost route is smaller than the cost of the first shortest cost route, updates the cost of the shortest cost route.

2. The navigation device according to claim 1, wherein

the route search unit, when expanding the predetermined area into the search area in the higher hierarchy level, expands by priority in a direction in which the cost to a boundary of the predetermined area becomes the smallest.

3. The navigation device according to claim 1, wherein

the control unit, when an arrival cost in the middle of the route search within the predetermined area on the departure point side or the destination side has exceeded the cost of the already-acquired shortest cost route, controls the route search unit not to perform cost assignment to subsequent nodes.

4. The navigation device according to claim 1, wherein

the control unit, when an arrival cost is not set to a boundary node of the predetermined area on the departure point side or the destination side, terminates the route search of the route search unit.

5. The navigation device according to claim 1, wherein

the control unit, when a total cost of smallest costs of boundary nodes of each predetermined area on the departure point side and the destination side is greater than the cost of the already-acquired shortest cost route, terminates the route search of the route search unit.

6. The navigation device according to claim 1, wherein

the control unit, when an arrival cost of an adjacent node of a higher hierarchy level node corresponding to a boundary node in a lower hierarchy level has exceeded the cost of the already-acquired shortest cost route, controls the route search unit not to perform cost assignment to subsequent nodes.

7. A navigation device comprising:

an information storage unit that stores information relating to a road;

a route search unit that searches for a route to a destination based on road information stored in the information storage unit; and

a control unit that determines quality of the route searched by the route search unit and controls route search processing, wherein the road information is structured with data levels in a plurality of hierarchy levels with different degree of details, in which at least one hierarchy level has been excluded,

the route search unit performs route search with detailed data in a range of each predetermined area on a departure point side and a destination side, expands, in the route search in a hierarchy level having a proximal higher hierarchy level of which the map data does not exist, the predetermined area into a search area in the proximal higher hierarchy level and performs the route search, and then moves to a data level in a higher hierarchy level and continues the route search, and

the control unit, when a route was connected between a departure point and a destination, compares a cost of the route searched in the data level in the higher hierarchy level with a cost of the route searched in the data level in a lower hierarchy level and terminates route search processing if it is determined that the cost of the route searched in the data level in the lower hierarchy level is lower than the cost of the route searched in the data level in the higher hierarchy level.

8. A program that controls a navigation device performing route search from a departure point to a destination, the program that causes a computer to perform the steps of:

reading map data in a hierarchical structure, in which the map data of at least one hierarchy level has been excluded, from an information storage unit;

performing the route search within each predetermined area on a departure point side and a destination side, expanding, in the route search in a hierarchy level having a proximal higher hierarchy level of which the map data does not exist, the predetermined area into a search area in the proximal higher hierarchy level and performing the route search to acquire a first shortest cost route in a range overlapped in search areas, and further performing the route search in a higher hierarchy level to acquire a second shortest cost route in a range overlapped in search areas;

when a cost of the second shortest cost route is smaller than the cost of the first shortest cost route, updating the cost of the shortest cost route.