Navigation system having optimal destination route setting capability

• US 5,752,217 A
• Filed: 05/24/1996
• Issued: 05/12/1998
• Est. Priority Date: 05/30/1995
• Status: Expired due to Term

• Current Assignee: Nippondenso Co., Ltd. (DENSO Corporation)
• Original Assignee: Nippondenso Co., Ltd. (DENSO Corporation)
• Inventors: Fujimoto, Hidetoshi, Ishizaki, Takashi
• Primary Examiner(s): Louis-Jacques, Jacques H.
• Assistant Examiner(s): Pipala, Edward J.
• Application Number:
  US08/653,268
• Time in Patent Office: 718 Days
• Field of Search: 364/444.1, 364/444.2, 364/449.1, 364/449.2, 364/449.3, 364/449.7, 701/201, 701/202, 701/207, 701/208, 701/209, 701/213, 340/988, 340/995, 73/178 R
• US Class Current: 701/201
• 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/096861 where the immediate route instructions are output to the driver, e.g. arrow signs for next turn
• CPC Class Codes: G08G 1/096872 where instructions are given per voice

Abstract

Route costs are computed using the Dijkstra algorithm based on link information and connection information and a destination route is set based on a connection of links which has the least route cost. The route cost is set to sub-nodes of each connection link. Therefore, optimal routes can be set even though traffic regulations such as no right turns or the like exist on certain nodes.

Claims

1. A navigation system comprising:

storage means for storing link information of links which connect nodes of a map and have route costs, and link connection information;

destination setting means for setting a destination in said map;

route determination means, which includes route cost storage means for storing said route costs of said links, for determining a destination route from a starting position to said destination set by said destination setting means by computing route costs based on said link information and said link connection information using a Dijkstra algorithm and by selecting links which form said destination route that have a least cost as determined by calculating an individual route cost, for every link connected to nodes in said destination route, of travel from said node to said link, and for individually updating said route costs for links connected to said nodes in said destination route; and

navigation means for performing cruising navigation based on said navigation route.

2. A navigation system according to claim 1, said route determination means including:

route cost updating means for updating said route costs; and

determining means for determining whether entry to a specified link is possible based on said link connection information and allowing said route cost updating means to update a route cost of said specified link when such entry is possible.

3. A navigation system according to claim 1, wherein said route determination means is for updating said route costs of said links in accordance with a direction of entry to said links.

4. A navigation system according to claim 1, wherein said route determination means is for updating a route cost of a specified link with respect to a direction from a specified node to said specified link.

5. A navigation system according to claim 4, wherein said route cost storage means stores route costs for each of said links.

6. A navigation system according to claim 4, wherein said route costs are initially set to a predetermined maximum value and can be updated to smaller values.

7. A navigation system according to claim 5, wherein:

said route costs are initially set to a predetermined maximum value; and

said route cost determination means is for updating said route cost of said specified link to a value smaller than said predetermined maximum value.

8. A navigation system according to claim 1, wherein:

said link information includes at least one of link identification code, link start coordinate, link end coordinate, link length, link type and link width; and

said link connection information includes traffic regulation information.

9. A navigation system according to claim 4, wherein:

said link information includes at least one of link identification code, link start coordinate, link end coordinate, link length, link type and link width; and

said link connection information includes traffic regulation information.

10. A navigation system according to claim 5, wherein said route determination means is for updating costs of said links in accordance with a direction of entry to said links.

11. A computer program product for determining routes in a map, said computer program product comprising:

first computer readable program code means for causing a computer to read link information of links that connect nodes and link connection information which includes traffic regulation information from a storage medium;

second computer readable program code means for causing said computer to select a node from among nondesignated nodes read by said first computer readable program code means so that a route cost from a starting position to a destination is minimal;

third computer readable program code means for causing said computer to compute a cost for passing through specified links connected to nondesignated nodes and for individually computing and storing a route cost of travel from said nodes to each specified link connected to said nodes; and

fourth computer readable program code means for causing said computer to repeatedly execute said selection and computation operations and for updating said route costs for links connected to said nodes in said destination route.

12. A method of navigating a vehicle using a map defined by a plurality of nodes connected by links from a starting position of said vehicle to a destination position of said vehicle, said nodes and links being representative of possible paths of travel of said vehicle, said method comprising the steps of:

selecting a node most proximate to said vehicle starting position as a vehicle starting node and as a current node;

selecting node most proximate to said vehicle destination position as a vehicle destination node;

computing route costs from said current node to all target nodes connected to said current node via a single link;

for each of said target nodes connected to said current node via a single link, sub-node associating said route cost from said vehicle starting position to a sub-node of said target node and a route from said vehicle starting position to said sub-node of said target node having said route cost with said sub-node of said target node if said route cost is less than a route cost already associated with said sub-node and movement from said current node to said sub-node is permitted along said route;

target node associating with each of said target nodes a smallest route cost and a path from said vehicle starting position to said target node providing said smallest route cost of sub-nodes of said target node;

selecting a node of said plurality of nodes in said map which has a route cost not greater than route costs of all other nodes in said plurality of nodes as a least cost node;

when said least cost node has not been selected as a current node, selecting said least cost node as said current node and repeating said computing and associating steps;

when said least cost node has been selected as a current node and a node, other than said vehicle destination node, which has not been selected as a current node has a route cost associated therewith which is less than a route cost of said vehicle destination node, selecting said non-selected node other than said vehicle destination node as said current node and repeating said computing and associating steps; and

when said least cost node has been selected as a current node and a node, other than said vehicle destination node, which has not been selected as a current node has a route cost associated therewith which is not less than a route cost of said vehicle destination node, selecting a path associated with said vehicle destination node as a least-cost path from said vehicle starting position to said vehicle destination position.

13. The method of claim 12, said sub-node associating step comprising the step of sub-node associating said route cost from said vehicle starting position to said target node and a route from said vehicle starting position to said target node having said route cost with a sub-node of said target node most proximate to said current node if movement from said current node to said target node is permitted as indicated by traffic regulation information associated with a current-target link connecting said current node and said target node.

14. The method of claim 13, said traffic regulation information being indicative of a permissible direction of travel of said vehicle on said current-target link.

15. The method of claim 13, said traffic regulation information being indicative of a permissible direction of turning of said vehicle from a last link in a least cost path from said starting position to said current node to said current-target link.

16. The method of claim 12, further comprising the step of determining said starting position based on signals from at least one of a global positioning system, a vehicle orientation sensor, and a vehicle speed sensor.

17. The method of claim 12, further comprising the step of inputting a user-provided indication of said destination position.

18. The method of claim 12, further comprising the step of generating a user-perceptible description of said least cost path.

19. The method of claim 12, further comprising the step of generating a user-perceptible description of a position of said vehicle relative to said least cost path.

20. A vehicle navigation system comprising:

a storage device storing data representative of a map defined by a plurality of nodes connected by links from a starting position of said vehicle to a destination position of said vehicle, said nodes and links being representative of possible paths of travel of said vehicle; and

microprocessor means for;

reading said data representative of said map stored in said storage device;

selecting a node most proximate to said vehicle starting position as a vehicle starting node and as a current node;

selecting node most proximate to said vehicle destination position as a vehicle destination node;

computing route costs from said current node to all target nodes connected to said current node via a single link;

for each of said target nodes connected to said current node via a single link, sub-node associating said route cost from aid vehicle starting position to a sub-node of said target node and a route from said vehicle starting position to said sub-node of said target node having said route cost with said sub-node of said target node if said route cost is less than a route cost already associated with said sub-node and movement from said current node to said sub-node is permitted alone said route;

target node associating with each of said target nodes a smallest route cost and a path from said vehicle starting position to said target node providing said smallest route cost of sub-nodes of said target node;

selecting a node of said plurality of nodes in said map which has a route cost not greater than route costs of all other nodes in said plurality of nodes as a least cost node;

when said least cost node has not been selected as a current node, selecting said least cost node as said current node and repeating said computing and associating functions;

when said least cost node has been selected as a current node and a node, other than said vehicle destination node, which has not been selected as a current node has a route cost associated therewith which is less than a route cost of said vehicle destination node, selecting said non-selected node other than said vehicle destination node as said current node and repeating said computing and associating functions; and

when said least cost node has been selected as a current node and a node, other than said vehicle destination node, which has not been selected as a current node has a route cost associated therewith which is not less than a route cost of said vehicle destination node, selecting a path associated with said vehicle destination node as a least-cost path from said vehicle starting position to said vehicle destination position.

21. The system of claim 20, wherein said microprocessor means is for sub-node associating said route cost from said vehicle starting position to said target node and a route from said vehicle starting position to said target node having said route cost with a sub-node of said target node most proximate to said current node if movement from said current node to said target node is permitted as indicated by traffic regulation information associated with a current-target link connecting said current node and said target node.

22. The system of claim 21, said traffic regulation information being indicative of a permissible direction of travel of said vehicle on said current-target link.

23. The system of claim 21, said traffic regulation information being indicative of a permissible direction of turning of said vehicle from a last link in a least cost path from said starting position to said current node to said current-target link.

24. The system of claim 20, further comprising:

vehicle movement indicator means for generating at least one of a positioning signal representative of a position of said vehicle relative to said map, a vehicle orientation signal representative of an orientation of said vehicle, and a vehicle speed signal representative of a speed of said vehicle as an output;

wherein said microprocessor means is further for determining said starting position based on said output of said vehicle movement indicator means.

25. The system of claim 20, further comprising input means for inputting a user-provided indication of said destination position.

26. The system of claim 20, further comprising output means for generating a user-perceptible description of said least cost path.

27. The system of claim 20, further comprising output means for generating a user-perceptible description of a position of said vehicle relative to said least cost path.