Route planner device

• US 4,962,458 A
• Filed: 08/25/1988
• Issued: 10/09/1990
• Est. Priority Date: 08/28/1987
• Status: Expired due to Term

• Current Assignee: Mannesmann VDO AG (Continental AG)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Verstraete, Rik A.
• Primary Examiner(s): Chin, Gary
• Application Number:
  US07/236,500
• Time in Patent Office: 775 Days
• Field of Search: 364/443, 364/444, 364/449, 73/178 R, 340/988, 340/990, 340/995
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A route planner comprises a control unit, a working memory and a storage memory in which a topological road network is stored in the form of at least one n-cell table. For the planning of a route between a starting point and a destination point a set of candidate cells is searched each time on the basis of an expansion index which indicates and n-cell, a further expansion index being derived from said set of candidate cells. For the storage of information blocks for each of the candidate cells found, a memory location is reserved in the memory working memory for each n-cell associated with an n-cell table used for the planning of the route. The information block of a candidate cell comprises inter alia the expansion index used to find the candidate cell and is stored at the memory location reserved for the relevant candidate cell. The sequence of the reserved memory locations preferably correspond to the sequence used to represent the n-cells in the table.

Claims

1. A planner device for planning a route through a topological road network, comprising:

background memory means for storing said network as a set of n-cell tables (n=0.1) of road segments or junctions;

random access working memory means for storing a subset of said set of n-cell tables as actually used in said planning;

address assigning means for assigning a respective first working memory address to each entry of each n-cell table used in planning the route;

data processing means coupled to said working memory means comprising;

expansion means for pointing to a set of candidate n-cells for said route, starting from one end of the route until the other end of the route is reached, on the basis of an actual expansion index indicating an actual n-cell;

linking means for linking each first working memory address pertaining to a candidate n-cell pointed to by said expansion means, to a second working memory address containing the n-cell used for said pointing;

evaluation means for assigning an evaluation value to each candidate n-cell pointed to by the expansion means;

selection means for selecting a candidate n-cell having the most advantageous evaluation value among those that have not led to an expansion index,

repeat control means for repeatedly activating said expansion means, said evaluation means and said selection means until said other end of the route is reached, and

backtracking means activated by said repeat control means for backtracking a linked set of candidate n-cells starting from the n-cell containing said other end until said one end is reached, said linked set constituting said route.

2. The device as claimed in claim 1, wherein each n-cell table of said subset of said set of n-cell tables has identical n-cell sequence in said working memory and in said background memory.

3. The device as claimed in claim 1, wherein said n-cell tables comprise 1-cells being traversable in a first and in a second direction, and said linking means comprises means for linking each candidate n-cell of the set of candidate n-cells pointed to by said expansion means to a third working memory address containing a further n-cell used for said pointing, said second and third working memory address relating to said first and second directions, respectively.

4. The device as claimed in claim 1 wherein said first working memory address contains the address of each n-cell used for said pointing.

5. The device as claimed in claim 1, wherein the working memory address containing any n-cell used for said pointing to an actual expansion index also contains an actual value of said evaluation value and wherein said linking means is responsive to said evaluation means for linking only if an updated evaluation value is more advantageous than a stored evaluation value, for replacing the latter in conjunction with storing the new n-cell used for the pointing.

6. The device as claimed in claim 3 wherein said first, second and third working memory addresses are contiguous.

7. The device as claimed in claim 1, in which the road network is subdivided into sections and in which at least one n-cell table is stored in the working memory for each section, comprising verifier means for determining whether a candidate n-cell crosses a section boundary and for generating a crossing signal and in which said address assigning means is responsive to said crossing signal for assigning addresses to the n-cells of the further section.

8. The planner device as claimed in claim 1 included in a vehicle navigation device.

9. The device as claimed in claim 2, wherein said n-cell tables comprise 1-cells being traversable in a first and in a second direction, and said linking means comprises means for linking each candidate n-cell of the set of candidate n-cells pointed to by said expansion means to a third working memory address containing a further n-cell used for said pointing, said second and third working memory address relating to said first and second directions, respectively.

10. A device as claimed in claim 2 wherein said first working memory address contains the address of each n-cell used for said pointing.

11. A device as claimed in claim 3 wherein said first working memory address contains the address of each n-cell used for said pointing.

12. A device as claimed in claim 9 wherein said first working memory address contains the address of each n-cell used for said pointing.

13. A device as claimed in claim 2 wherein the working memory address containing any n-cell used for said pointing to an actual expansion index also contains an actual value of said evaluation value and wherein said linking means is responsive to said evaluation means for linking only if an updated evaluation value is more advantageous than a stored evaluation value, for replacing the latter in conjunction with storing the new n-cell used for the pointing.

14. A device as claimed in claim 3 wherein the working memory address containing any n-cell used for said pointing to an actual expansion index also contains an actual value of said evaluation value and wherein said linking means is responsive to said evaluation means for linking only if an updated evaluation value is more advantageous than a stored evaluation value, for replacing the latter in conjunction with storing the new n-cell used for the pointing.

16. A device as claimed in claim 9 wherein the working memory address containing any n-cell used for said pointing to an actual expansion index also contains an actual value of said evaluation value and wherein said linking means is responsive to said evaluation means for linking only if an updated evaluation value is more advantageous than a stored evaluation value, for replacing the latter in conjunction with storing the n-cell used for the pointing.

17. A device as claimed in claim 10 wherein the working memory address containing any n-cell used for said pointing to an actual expansion index also contains an actual value of said evaluation value and wherein said linking means is responsive to said evaluation means for linking only if an updated evaluation value is more advantageous than a stored evaluation value, for replacing the latter in conjunction with storing the new n-cell used for the pointing.

15. A device as claimed in claim r wherein the working memory address containing any n-cell used for said pointing to an actual expansion index also contains an actual value of said evaluation value and wherein said linking means is responsive to said evaluation means for linking only if an updated evaluation value is more advantageous than a stored evaluation value, for replacing the latter in conjunction with storing the new n-cell used for the pointing.