Navigation apparatus and method for exploring an optimal route based on characteristics of an exploration object zone

• US 5,410,485 A
• Filed: 10/19/1993
• Issued: 04/25/1995
• Est. Priority Date: 10/22/1992
• Status: Expired due to Term

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Ichikawa, Shigeru
• Primary Examiner(s): ZANELLI, MICHAEL J
• Application Number:
  US08/139,595
• Time in Patent Office: 553 Days
• Field of Search: 364/443, 364/444, 364/449, 364/489, 340/990, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A method and apparatus for reliably determining an optimal route between a departure point and a destination in an exploration object zone, the optimal route being determined according to the situation of roads separating the departure point and the destination. Prior to route exploration, an area determiner counts the total number of intersection network lists associated with a route exploration object zone, which lists are stored in a route exploration memory. When a density of intersections (which is the total number of intersection network lists divided by the size of the route exploration object zone) exceeds a certain value, the area determiner determines that the object zone lies in an urban (high road density) district. When the density of intersections is smaller, the area determiner determines that the object zone lies in a suburban (low road density) district. When the area determiner determines that the object zone lies in an urban district, an optimal route explorer executes heuristic exploration; that is, it uses intersection network lists to explore an optimal route linking a departure point and a destination while trimming away routes that deviate from the direction specified with a straight line joining the departure point and destination or while lowering the priorities of such routes. When the area determiner determines that the object zone lies in a suburban district, the optimal route explorer executes normal non-heuristic (exhaustive) exploration.

Claims

1. A route exploration method for exploring an optimal route that links a departure point and a destination, comprising the steps of:

determining a characteristic of an exploration object zone;

selecting one of at least two exploration techniques depending on the determined characteristic; and

identifying the optimal route between the departure point and the destination using the selected one of said at least two exploration techniques.

2. A route exploration method according to claim 1, wherein the characteristic is a road density of said exploration object zone.

3. A route exploration method in which road data including intersection network lists is referenced to explore an optimal route linking a departure point and a destination, comprising the steps of:

referencing said road data to determine a road density of an exploration object zone;

when said exploration object zone lies in a high road density district, executing a heuristic exploration whereby routes deviating from the direction specified with a straight line joining the departure point and destination are trimmed away or the priorities of such routes are lowered; and

when said exploration object zone lies in a low road density district, executing a non-heuristic exploration.

4. A route exploration method according to claim 3, wherein area determination data, which indicates whether an object area defined by road data lies in a high or low road density district, is included in said road data, and said area determination data is referenced to determine whether an exploration object zone lies in a high or low road density district.

5. A route exploration method according to claim 3, wherein intersection network lists are pre-stored in map data units in a memory, whereby a necessary intersection network list can be read from said memory.

6. A route exploration method according to claim 3, wherein said non-heuristic exploration includes a Dijkstra exploration.

7. A route exploration method according to claim 3, wherein said non-heuristic exploration includes a horizontal exploration.

8. A route exploration method according to claim 3, wherein the density of roads is determined by dividing the total number of intersections, corresponding to the total number of intersection network lists, by the size of an object area for which the intersection network lists are stored, and comparing with a predetermined reference value, wherein when the density is larger than the reference value, a high road density district is identified, and wherein when the density is smaller than the reference value, a low road density district is identified.

9. A route exploration method according to claim 8, wherein the road data includes a node table comprising a number of nodes, each node having an associated intersection identification flag which, when set, identifies an intersection, and wherein the total number of intersections is determined by counting the number of nodes having intersection identification flags which are set.

10. A route exploration method according to claim 8, wherein the number of intersections defined by intersection node lists is counted to determine the total number of intersections.

11. A route exploration method according to claim 8, wherein the total number of intersections is estimated in terms of a capacity of a route exploration memory occupied by intersection network lists stored therein.

12. A route exploration method according to claim 8, wherein the total number of intersections is estimated in terms of the sum of the sizes of intersection node lists included in road data.

13. A route exploration method according to claim 3, wherein said step of executing heuristic exploration comprises:

checking successively during optimal route exploration if the azimuth of a route leading to a certain adjacent intersection from the i-th intersection (i=1, 2, etc., and n) deviates by more than a specified angle from the azimuth of a destination relative to a departure point; and

when the azimuth deviates by more than the specified angle, trimming away the route, whereby exploration will not proceed with the route any longer.

14. A route exploration method according to claim 13, further comprising the step of determining said azimuth of a route leading to a certain adjacent intersection from the i-th intersection by reading the latitudinal and longitudinal coordinates of the i-th intersection and the intersection adjoining the ith intersection from an intersection network list.

15. A route exploration method according to claim 3, wherein said step of heuristic exploration comprises:

checking successively during optimal route exploration if a total distance of a route leading to an adjacent intersection of the i-th intersection (i=1, 2, etc., and n) from a departure point intersection exceeds a specified distance; and

when the total distance exceeds the specified distance, stopping exploration of the route.

16. A route exploration method according to claim 15, wherein said total distance is a sum of a distance d₁ from the departure point intersection to the ith intersection and a distance d₂ from the i-th intersection to the adjacent intersection.

17. A route exploration method according to claim 3, wherein said step of heuristic exploration comprises:

storing difference coordinates of adjacent intersections in a difference coordinate system, of which an origin is set at an object intersection, in the intersection network list;

determining at the start of retrieval in which quadrant a destination intersection resides in terms of a difference coordinate system whose origin is set at a departure point intersection;

referencing the intersection network list for the i-th intersection to retrieve difference coordinates registered for each adjacent intersection;

determining whether the quadrant, in which the adjacent intersection resides, agrees with the quadrant in which the destination resides; and

determining on the basis of the result of the determination whether a route linking the i-th intersection and the adjacent intersection adjoining the i-th intersection is to be trimmed away.

18. A route exploration method according to claim 3, wherein said step of heuristic exploration comprises:

checking successively during optimal route exploration if the azimuth of a route leading to a certain adjacent intersection from the tip of an exploration branch is deviating by a specified angle from the azimuth of a destination relative to a departure point; and

when the azimuth is deviating by more than the specified angle, weighting the distance of the route to lower the priority of the route.

19. A route exploration method for a navigation apparatus including a vehicle location detector and a guidance route memory from which road data including intersection network lists is referenced to explore an optimal route linking a departure point and a destination, comprising the steps of:

reading a road data portion from the guidance route memory;

calculating a density of intersections in the road data portion by dividing the total number of intersections corresponding to the total number of intersection network lists by the size of an object area for which intersection network lists are created, and then comparing with a certain reference value;

when the calculated density exceeds said reference value, determining that an exploration object zone lies in an urban district;

when the calculated density is less than said reference value, determining that an exploration object zone lies in a suburban district;

when the determination is that the exploration object zone lies in an urban district, reading the latitudinal and longitudinal coordinates of the i-th intersection (i=1, 2, etc., and n) and a certain intersection adjoining the i-th intersection from an intersection network list and a vehicle location from the vehicle location detector, and calculating an azimuth of a route leading from the vehicle location to the adjacent intersection from the i-th intersection;

checking if said azimuth is deviating by more than a specified angle from the azimuth of the destination relative to the departure;

when said azimuth is deviating by more than the specified angle, trimming away the route whereby exploration will not proceed with the route any longer; and

when said exploration object zone lies in a suburban district, executing non-heuristic exploration.

20. A vehicular navigation apparatus having a memory that stores map data including road data, a vehicle location detector for detecting a current location of a vehicle, a guidance route memory that stores guidance route data concerning routes leading to a desired destination, and a map display controller that uses map data stored in said map data memory and guidance route data stored in said guidance route memory to display a map image, which shows a location of the vehicle and its surrounding areas, together with a vehicle location mark and a guidance route as a route guidance screen, and comprising:

an operation unit designating route guidance that provides a desired route leading to the destination; and

an area determiner that when said operation unit is used to designate route guidance, references road data to determine whether an exploration object zone lies in an high or low density district;

wherein;

when said area determiner determines that said exploration object zone lies in a high road density district, a heuristic exploration trims away routes deviating from the direction specified with a straight line joining the departure point and destination or the priorities of such routes are lowered; and

when said exploration object zone lies in a low road density district, a non-heuristic exploration is executed.