Navigation device and program

• US 8,219,313 B2
• Filed: 08/27/2009
• Issued: 07/10/2012
• Est. Priority Date: 10/16/2008
• Status: Expired due to Fees

• Current Assignee: Aisin AW Company Limited (Aisin Corp.)
• Original Assignee: Aisin AW Company Limited (Aisin Corp.)
• Inventors: Hosoi, Yasuki, Matsuhisa, Syougo
• Primary Examiner(s): Algahaim, Helal A
• Application Number:
  US12/461,915
• Publication Number:
  US 20100100309A1
• Time in Patent Office: 1,048 Days
• Field of Search: 701/410, 701/433, 701/533, 701/540
• US Class Current: 701/410
• 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, the hierarchical structure being defined such that;

a lowest level of the hierarchical structure includes the map data for all roads, including local roads,

a highest level of the hierarchical structure includes the map data for only major roads, and

one or more middle levels of the hierarchical structure includes the map data for the major roads and the map data for one or more categories intermediate roads, but not the map data for the local roads,

map data being excluded from at least one of the defined middle levels of the hierarchical structure in order to reduce the overall size of the map data stored in the information storage unit; and

a controller that;

reads the map data from the information storage unit;

performs a route search within a predetermined area of each level of the hierarchical structure that includes map data and acquires a shortest cost route;

the predetermined area within each hierarchical level having map data that exists immediately below a hierarchical level having no map data being expanded into an expanded search area having a size equal to a predetermined area that would have been searched in the hierarchical level having no map data if it had had map data;

performs a route search in the expanded search area to acquire a first route;

performs a route search in a hierarchy level higher than the hierarchy level including the first route to acquire a second route;

determines whether the first route or the second route has a smaller cost; and

identifies the one of the first route and the second route having the smallest cost as a shortest cost route.

2. The navigation device according to claim 1, wherein the controller:

expands the expanded search area by priority in a direction in which a cost to an area boundary becomes the smallest.

3. The navigation device according to claim 1, wherein the controller:

ends route searching when a search cost of an incomplete route exceeds the cost of the shortest cost route.

4. The navigation device according to claim 1, wherein the controller:

ends route searching when an arrival cost is not set to a boundary node on a departure point side or a destination side.

5. The navigation device according to claim 1, wherein the controller

ends route searching when a total cost of smallest costs of boundary nodes on a departure point side and a destination side is greater than the cost of the shortest-cost route.

6. The navigation device according to claim 1, wherein the controller:

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 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 map data relating to roads in a hierarchical structure, the hierarchical structure being defined such that;

a lowest level of the hierarchical structure includes the map data for all roads, including local roads,

a highest level of the hierarchical structure includes the map data for only major roads, and

one or more middle levels of the hierarchical structure includes the map data for the major roads and the map data for one or more categories intermediate roads, but not the map data for the local roads,

map data being excluded from at least one of the defined middle levels of the hierarchical structure in order to reduce the overall size of the map data stored in the information storage unit; and

a controller that;

searches for a route to a destination based on the map data stored in the information storage unit

with detailed data in a range of each predetermined area on a departure point side and a destination side the predetermined area within each hierarchical level having map data that exists immediately below a hierarchical level having no map data being expanded into an expanded search area having a size equal to a predetermined area that would have been searched in the hierarchical level having no map data if it had had map data; and

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

8. A non-transitory computer-readable storage medium storing a computer-executable route search program, the program comprising:

instructions for accessing an information storage unit that stores map data in a hierarchical structure, the hierarchical structure being defined such that;

a lowest level of the hierarchical structure includes the map data for all roads, including local roads,

a highest level of the hierarchical structure includes the map data for only major roads, and

one or more middle levels of the hierarchical structure includes the map data for the major roads and the map data for one or more categories intermediate roads, but not the map data for the local roads,

map data being excluded from at least one of the defined middle levels of the hierarchical structure in order to reduce the overall size of the map data stored in the information storage unit;

instructions for reading the map data from the information storage unit;

instructions for performing a route search within a predetermined area of each level of the hierarchical structure that includes map data and acquires a shortest cost route;

the predetermined area within each hierarchical level having map data that exists immediately below a hierarchical level having no map data being expanded into an expanded search area having a size equal to a predetermined area that would have been searched in the hierarchical level having no map data if it had had map data;

instructions for performing a route search in the expanded search area to acquire a first route;

instructions for performing a route search in a hierarchy level higher than the hierarchy level including the first route to acquire a second route;

instructions for determining whether the first route or the second route has a smaller cost; and

instructions for identifying the one of the first route and the second route having the smallest cost as a shortest cost route.