In-car navigation apparatus

• US 5,684,704 A
• Filed: 10/25/1995
• Issued: 11/04/1997
• Est. Priority Date: 01/20/1995
• Status: Expired due to Term

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Okazaki, Katsuzi
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): WALDER, STEPHEN JOSEPH
• Application Number:
  US08/548,264
• Time in Patent Office: 741 Days
• Field of Search: 364/444, 364/449, 364/424.02, 364/424.027, 364/424.029, 364/444.1, 364/444.2, 364/449.1, 364/449.3, 364/449.4, 364/449.5, 364/449.6 , 364/449.7
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/0969 having a display in the form of a map
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

An in-car navigation apparatus capable of searching an optimal or a quasi-optimal route always, and further capable of shortening the waiting time until a route is obtained, has an operating section which receives a starting point, a destination and searching conditions for searching from a handling section to read digital map data to be used for searching from the map database section of the apparatus. The operating section holds a plurality of weighting factors of each heuristic term to be used in an evaluation function or computing formulae to be used for the evaluation function, and searches an optimal or a quasi-optimal route by selecting an appropriate one in accordance with the road conditions and the searching conditions of the map data read in when searching is performed.

Claims

1. An in-car navigation apparatus comprising:

a map database storing digital map data composed of at least two ranks different in degree of road detail; and

searching means for searching a route from an appointed starting point to a destination through which a moving body should travel by means of a heuristic algorithm by changing a relative weight of a heuristic term of an evaluation function in accordance with said ranks of the digital map data stored in said map database.

2. A navigation system for determining a route to be travelled by a moving body going from starting point S to destination point T, comprising:

a map database containing a plurality of maps having different rank numbers; and

an operating section for selecting one of said ranked maps from said map database and for determining a section of said route from point S to point T by calculating an evaluation value from an evaluation function f(n), said evaluation function f(n) including a calculated cost term g(n) and a heuristic term h(n), the weight of said heuristic term h(n) relative to said calculated cost term g(n) being set in accordance with the rank number of said selected map.

3. A navigation system according to claim 2, wherein said operating section changes the weight of the heuristic term h(n) relative to the cost term g(n) in conformity with searching conditions regarding a road type through which the moving body should travel.

4. A navigation system according to claim 2, wherein said operating section changes the weight of the heuristic term h(n) relative to the cost term g(n) in conformity with searching conditions regarding whether computing time necessary for searching is given priority or whether searching of an optimal route is given priority.

5. A navigation system according to claim 2, wherein said operating section selects a rank of map data from which searching is begun in accordance with a distance of a straight line from the appointed starting point S to the destination point T.

6. A navigation system according to claim 2, wherein said map data stored in said map database is composed of a first rank including only major arterial roads, a second rank including major and local arterial roads, and a third rank including all passable roads, and wherein said operating section searches routes in consecutive rank order by decreasing the weight of the heuristic term h(n) relative to the cost term g(n) in order from the first rank to the third rank.

7. A navigation system according to claim 2, wherein said operating section searches a route by making the weight of the heuristic term h(n) relative to the cost term g(n) small in accordance with largeness of detail of a road in a rank of the map data.

8. A navigation system as defined in claim 2, wherein the weight of said heuristic term h(n) relative to said cost term g(n) is set by multiplying h(n) by a weighting factor k_h which changes for different map rank numbers.

9. A navigation system as defined in claim 2, wherein the weight of said heuristic term h(n) relative to said cost term g(n) is set by multiplying said cost term g(n) by the inverse of a weighting factor k_h which changes for different map rank numbers.

10. A navigation system as defined in claim 2, wherein the weight of said heuristic term h(n) relative to said cost term g(n) is set by calculating h(n) with a formula which changes for different map rank numbers.

11. A navigation system as defined in claim 2, wherein said operating section changes the weight of said heuristic term h(n) relative to said cost term g(n) in conformity with a searching condition, said searching condition including an indication that toll roads are or are not preferred.

12. A navigation system as defined in claim 2, wherein said operating section changes the weight of said heuristic term h(n) relative to said cost term g(n) in conformity with a searching condition, said searching condition including an indication that wide roads are or are not preferred.

13. A method for navigating a route to be travelled by a moving body going from starting point S to destination point T, comprising the steps of:

(a) storing in a database a plurality of maps having different rank numbers;

(b) selecting one of said ranked maps from said map database;

(c) determining a section of said route from point S to point T by calculating an evaluation value from an evaluation function f(n), said evaluation function f(n) including a calculated cost term g n) and a heuristic term h(n), the weight of said heuristic term h(n) relative to said calculated cost term g(n) being set in accordance with the rank number of said selected map; and

(d) repeating said steps (b) and (c) until a desirable complete route from point S to point T is determined.

14. A method for navigating as defined in claim 13, wherein the weight of said heuristic term h(n) relative to said cost term g(n) is set by multiplying h(n) by a weighting factor k_h which changes for different map rank numbers.

15. A method for navigating as defined in claim 13, wherein the weight of said heuristic term h(n) relative to said cost term g(n) is further set in accordance with whether computing time or the determination of an optimal route is given priority.

16. A method for navigating as defined in claim 13, wherein the rank of the map initially selected in step (b) is determined in accordance with the distance of a straight line form starting point S to destination point T.

17. A method for navigating as defined in claim 13, wherein the weight of said heuristic term h(n) relative to said cost term g(n) is further set in accordance with a selected road type preference.

18. A method for navigating as defined in claim 13, wherein the weight of said heuristic term h(n) relative to said cost term g(n) is further set in accordance with the level of road detail.

19. A method for navigating as defined in claim 13, wherein said ranked maps includes;

a map having a high rank which contains only major arterial roads, a map having an intermediate rank which contains both major and local arterial roads, and a map having a low rank which includes all passable roads, said steps (b) and (c) starting with a high ranked map and progressing consecutively through lower ranked maps until a desirable complete route from starting point S to destination point T is determined, the weight of said heuristic term h(n) relative to said cost term g(n) decreasing with a decrease in map rank.