Navigation system and path search method using hierarchized road data

• US 5,513,110 A
• Filed: 07/08/1994
• Issued: 04/30/1996
• Est. Priority Date: 07/09/1993
• Status: Expired due to Term

• Current Assignee: Clarion Co., Ltd. (Faurecia SA)
• Original Assignee: Hitachi, Ltd., Xanavi Informatics Corporation (Hitachi, Ltd.)
• Inventors: Nomura, Takashi, Fujita, Takehiro
• Primary Examiner(s): Chin, Gary
• Application Number:
  US08/272,493
• Time in Patent Office: 662 Days
• Field of Search: 364/443, 364/444, 364/449, 73/178 R, 340/988, 340/990, 340/995
• US Class Current: 701/207
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A navigation system in which a more preferable path can be quickly searched for by using map data in a form easy of maintenance, and which is well suited for installation on a vehicle. A map data memory unit stores therein the road data of roads which belong to management areas, for each of the management areas of predetermined extent and shape and for each of hierarchies corresponding to sorts of the roads. A path search/guidance control unit searches for the path which extends from a current point decided by a positioning unit, to a destination point set by a set input unit. The pat search is made in such a way that nodes connecting with the roads in higher hierarchies and paths extending to the nodes are searched for from the current point and from the destination point, sequentially in the respective hierarchies from the hierarchies corresponding to the current point and the destination point up to the hierarchy corresponding to a distance between the point of departure and the destination point, the connecting nodes and the extending paths being searched for as to each of the respective hierarchies and on the basis of the road data of the pertinent hierarchy relevant to the management areas which lie within limits of a size corresponding to the pertinent hierarchy, and that a path is searched for between the nodes which have been searched for and which connect with the roads in the hierarchy corresponding to the distance between the point of departure and the destination point. Further, the path search/guidance control unit gives a guidance suggestion on a display unit through a display control unit.

Claims

1. A navigation system for installation on a vehicle for providing a recommendable path from a departure point or a current position of the vehicle to a destination point, comprising:

storage means for storing therein road data representing roads of an area, wherein said road data comprises road shape data and network data, said road shape data representing sorts and shapes of said roads, and said network data comprising node data representing intersections and link data representing connections between the intersections,

said roads being classified into a plurality of hierarchies in accordance to the type of roads, said road data being divided into a plurality of hierarchized data, each hierarchized data corresponding to one of said hierarchies, each said hierarchized data being divided into a plurality of data units, each said data unit of a hierarchized data corresponding to a management area representing a particular geographical area of predetermined extent and shape;

position means for detecting said current position of the vehicle;

set input means for accepting setting of said destination point; and

path search means for searching for a recommended path which extends from a given point of departure or said current position of the vehicle to the destination point,

said path search means making a search for said recommended path in such a way that said path search means searches partial paths of said recommended path in the respective hierarchies sequentially, each of said partial paths being searched on the basis of the road data units corresponding to the combination of the management area contained in a search area of the hierarchy in which the partial path is to be searched, and the hierarchy in which the partial path is to be searched, each of said partial paths being formed of the road or roads in the hierarchy in which the partial path is to be searched, and said search area of the hierarchy being an area having a breadth predetermined so that the search area of a higher hierarchy has a broader breadth.

2. A navigation system as defined in claim 1, wherein said path search means makes the search for the partial paths in such a way that nodes connecting with the road in higher ones of said hierarchies and the partial paths extending to the nodes are searched for from the point of departure and from said destination point, sequentially in the respective hierarchies, from the hierarchies corresponding to said point of departure and said destination point up to the hierarchy directly lower than the hierarchy selected as a final hierarchy for search, said final hierarchy being selected in such a manner that the higher hierarchy is selected as said final hierarchy for search when a distance between said point of departure and said destination point is longer, and

that the remaining partial path is searched for between the nodes which have been searched for and which connect with said roads in said hierarchy selected as the final hierarchy.

3. A navigation system as defined in claim 1, wherein said path search means searches for a node connecting with the road in the hierarchy which is directly higher than the hierarchy corresponding to said current position, and a path extending to the node, from said current position, before said destination point is accepted by said set input means, and said path search means searches for said recommended path extending from the point of departure to said destination point, under a condition that said node connecting with said road in the directly higher hierarchy is set as said point of departure, after said destination point has been accepted;

and

said guidance means guides the running of said vehicle on the basis of the path which extends to said node connecting with said road in said directly higher hierarchy and which has been searched by said path search means, immediately after said destination point has been accepted.

4. A navigation system for installation on a vehicle, comprising:

storage means for storage therein road data for representing roads, wherein said roads data comprises network data which represents nodes representing connection points of nodes and links representing connections of the nodes, and shape data which represents sorts and shapes of roads, said roads are classified as to hierarchies and management areas, and said road data are divided into a plurality of road data units for each of a plurality of combinations of the hierarchy and the management area in which corresponding roads are classified, each of said hierarchies corresponding to each of a plurality of sorts of road, and said management areas being geographical areas of predetermined extent and shape;

positioning means for detecting a current position and a traveling direction of the vehicle;

set input means for accepting setting of a destination point;

path search means for searching for a recommended path which extends from a given point of departure to the destination point; and

guidance means for guiding running of said vehicle on the basis of the current position measured by said positioning means and the recommended path searched for by said path search means;

said path search means setting candidate areas to the hierarchies sequentially from the hierarchy which corresponds to the point of departure to the hierarchy to which the candidate area contains said destination point is set under a condition that the candidate areas set to the higher hierarchies have broader breadth;

then setting a search area to-be-searched in correspondence with a position and the breadth of the candidate which contains said destination point; and

subsequential making the search for said recommended path on the basis of the road data units corresponding to the combinations including the management area contained in said search area.

5. A navigation system for installation on a vehicle, comprising:

storage means for storing therein road data for representing roads, wherein said roads data comprises network data which represents nodes representing connection points of nodes and links representing connections of the nodes and shape data which represents sorts and shapes of roads, said roads are classified as to hierarchies and management areas, and said road data are divided into a plurality of road data units for each of a plurality of combinations of the hierarchy and the management area in which corresponding roads are classified, each of said hierarchies corresponding to each of a plurality of sorts of road, and said management areas being geographical areas of predetermined extent and shape;

first setting means for setting a point of departure as a first search starting point, setting the hierarchy in which the nearest road to the first search starting point is contained as a first search hierarchy, and setting a first candidate search area around said first search starting point, and repeating a process of renewing the first search hierarchy and the first candidate search area until the destination point is contained in the first candidate search area,

said process being for searching for a partial path which extends onto the road belonging to the hierarchy directly higher than the current first search hierarchy on the basis of the road data units corresponding to the combinations of the management area contained in the current first candidate search area and hierarchy corresponding to the current first search hierarchy, renewing the first search starting point to an end point of the searched partial path, renewing the first search hierarchy to the hierarchy directly higher than a current first search hierarchy, and renewing the first candidate search area around the renewed first search starting point;

second setting means for setting said destination point as a second search starting point, setting the hierarchy in which the nearest road to the second search starting point is contained as a second search hierarchy, and setting a second candidate search area around the second search starting point;

third setting means for setting an area which circumscribes the current first candidate search area and the second candidate search area as a search area after said repeating of said process has been finished; and

recommended path generating means for searching, after said search area has been set, for a remaining partial path extending between the current first search starting point and the current second search starting point on the basis of said road data units corresponding to the combinations including said management area contained in the search area, and subsequently connecting the partial paths searched by said process with the remaining partial path, thereby obtaining a recommended path which extends from the point of departure to said destination point;

the first candidate search area being set so as to have broader breadth when the current first hierarchy is higher, and the second candidate search area being set so as to have broader breadth when the second hierarchy is higher.

6. A navigation system for installation on a vehicle, comprising:

storage means for storing therein road data for representing roads, wherein said roads data comprises network data which represents nodes representing connection points of nodes and links representing connections of the nodes, and shape data which represents sorts and shapes of roads, said roads are classified as to hierarchies and management areas, and said road data are divided into a plurality of road data units for each of a plurality of combinations of the hierarchy and the management area in which corresponding roads are classified, each of said hierarchies corresponding to each of a plurality of sorts of road, and said management areas being geographical area of predetermined extent and shape;

partial path searching means for setting a point of departure as a first search starting point, setting the hierarchy in which the nearest road to the first search starting point is contained as a first search hierarchy, and setting a first candidate search area around said first search starting point, setting said destination point as a second search starting point, setting the hierarchy in which the road nearest the second search starting point is contained as a second search hierarchy, setting a second candidate search area around the second search starting point, repeating a first process of renewing the first search hierarchy and the first candidate search area until the destination point is contained in the first search hierarchy, then repeating said first process until said first search hierarchy become equal to the second search hierarchy when the current first search hierarchy is lower than the second search hierarchy, and then repeating a second process of renewing the second search hierarchy and the second candidate search area until said second search hierarchy becomes equal to the current first search hierarchy when the second search hierarchy is lower than the current first search hierarchy,

said first process being for searching for a partial path which extends onto the road belonging to the hierarchy directly higher than the current first search hierarchy on the basis of the road data units corresponding to the combinations of the management area contained in the current first candidate search area and hierarchy corresponding to the current first search hierarchy, renewing the first search starting point to an end of the searched partial path, renewing the first search hierarchy to the hierarchy directly higher than the current first search hierarchy, and renewing the first candidate search area around the renewed first search starting point;

said second process being for searching for a partial path which extends onto the road belonging to the hierarchy directly higher than the current second search hierarchy on the basis of the road data units corresponding to the combinations of the management area contained in the current second candidate search area and hierarchy corresponding to the current second search hierarchy, renewing the second search starting point to an end point of the searched partial path, renewing the second search hierarchy to the hierarchy directly higher than the current second search hierarchy, and renewing the second candidate search area around the renewed second search starting point;

second setting means for setting an area which circumscribes the current first candidate search area and the current candidate search area as a search area after said repeating of said first process; and

recommended path generating means for, after that said search area has been set, searching for a remaining partial path extending between the current first search starting point and the current second search starting point on the basis of said road data units corresponding to the combinations including said management area contained in the search area, and subsequently connecting the partial paths searched by said first process and said second process with the remaining partial path, thereby obtaining a recommended path which extends from the point of departure to said destination point;

the first candidate search area being set so as to have broader breadth when the current first hierarchy is higher, and the second candidate search area being set so as to have broader breadth when the second hierarchy is higher.