Bucket-oriented route planning method, and navigation system comprising a route planner for carrying out such a method

• US 5,170,353 A
• Filed: 06/25/1991
• Issued: 12/08/1992
• Est. Priority Date: 11/17/1988
• Status: Expired due to Fees

• 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/723,704
• Time in Patent Office: 532 Days
• Field of Search: 364/443, 364/444, 364/424.02, 364/449, 180/167, 180/168, 180/169, 318/587, 340/990, 340/995
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

A method of planning optimum routes on the basis of successively selected sub-sets of the total topographical and traffic information, so-called buckets, which method anticipates which buckets will be of importance in the near future for the calculation of the navigation data, and navigation system comprising a route planner for carrying out such a method.

Claims

1. A method of determining an optimum route between a starting position and a destination position on the basis of topographical and traffic information by repeated selection of vectors and expansion of a search tree which contains previously selected vectors which form already planned sub-routes, the method comprising:

(a) assigning a respective weighting factor to each of the vectors and determining a cumulative weighting factor for each respective one of the already planned sub-routes by adding the weighting factors of the vectors of the respective one of the already planned sub-routes;

(b) sub-dividing the topographic and traffic information into a number of buckets in a background memory wherein the number of buckets is the total available buckets;

(c) determining a maximum number of buckets from the total available buckets for transfer to a working memory based on an evaluation value obtained by summing

i) the cumulative weighting factor of at least one of the already planned sub-routes; and

ii) the weighting factor of at least one vector of a proposed sub-route within a relevant bucket;

(d) selecting a vector to add to the search tree wherein the vector is selected from within the working memory, whereby the search tree is expanded; and

(e) outputting the optimum route based on a best one of the sub-routes in the search tree when all vectors have been searched.

2. A method of determining an optimum route as claimed in claim 1, comprising the steps of

determining said evaluation value for a bucket in the working memory by selecting the most attractive evaluation value of all vectors in the relevant bucket which are listed on a candidate list, and

determining said evaluation value for a neighboring bucket of the bucket in the working memory by adding

the weighting factor of an idealized straight path between a current position and a point z which is a point intersection of

a connecting line between centers of said bucket and said neighboring bucket and

a common boundary or an extension of the common boundary of said bucket and said neighboring bucket,

the weighting factor of an idealized straight path between said point z and an end point of a vector v_b in said bucket, and

the cumulated weighting factor of an already planned sub-route from said vector v_b to a target vector.

3. A method of determing an optimum route as claimed in claim 2, comprising the step of selecting the vector v_b that has the most attractive evaluation value of all vectors in said bucket which are listed on the candidate list.

4. A method of determining an optimum route as claimed in claim 3, comprising the step of selecting the vector v_b which is situated nearest to said point z, from several vectors in a bucket which are listed on the candidate list as having the most attractive evaluation value.

5. A method of determining an optimum route as claimed in claim 2, comprising the step of selecting, as the most attractive evaluation value, the evaluation value of a neighboring bucket adjoining several buckets in the working memory.

6. A method of determining an optimum route as claimed in claim 3, comprising the step of selecting, as the most attractive evaluation value, the evaluation value of a neighboring bucket adjoining several buckets in the working memory.

7. A method of determining an optimum route as claimed in claim 4, comprising the step of selecting, as the most attractive evaluation value, the evaluation value of a neighboring bucket adjoining several buckets in the working memory.

8. The method of claim 1, wherein the background memory is a compact disc.

9. A navigation system including a route planner having

a memory for bucket storage of topographical and traffic information;

an input/output unit for inputting and outputting information concerning a given starting position and a given destination position; and

a processor which is programmed so that, via repeated selection of vectors and expansion of a search tree containing previously selected vectors which form already planned sub-routes, an optimum route is calculated from the given starting position to the given destination position based on weighting factors assigned to each vector,

wherein the improvement comprises that the memory includes;

(a) a background memory in which the bucket organized topographical and traffic information is stored; and

(b) a working memory for receiving from the background memory buckets selected based on an evaluation value which is determined by a sum of the weighting factors of the vectors of;

i) at least one of the already planned sub-routes and

ii) a proposed sub-route, the proposed sub-route including at least one vector from at least one of the selected buckets,

such that only vectors from the selected buckets in the working memory are used for the repeated selection of the vectors and the expansion of the search tree.

10. A navigation system as claimed in claim 9, further comprising:

(a) means for determining an actual position of an object whose route is to be planned; and

(b) means for comparing the actual position with positions on routes found, such that the route planner continues a search when non-correspondence is found by said means for comparing and terminates the search when correspondence is found by said means for comparing.

11. A navigation system as claimed in claim 9, wherein the working memory is for storing:

a candidate list with vectors to be selected for expansion,

a search tree list with vectors already examined and their evaluation values and pointers,

a search list with target vectors not yet found,

a candidate bucket list with buckets which overlap the candidate list,

a bucket request list with both candidate buckets and neighboring buckets of those candidate buckets already in the working memory,

a locked bucket list with buckets which are locked in the working memory, and

a filtered candidate list with candidate list vectors present in one of the locked buckets.

12. The system of claim 9, wherein the background memory is a compact disc.

13. A method for determining an optimum route between a starting position and a destination position on the basis of topographical and traffic information comprising the steps of

a) storing the topographical and traffic information in buckets in a background memory in the form of vectors and weighting values associated with the vectors;

b) loading some of the buckets into a working memory based on a first evaluation value which is a sum of weighting values of at least one already planned sub-route and estimated values associated with the buckets;

c) searching vectors within the working memory based on a second evaluation value which is a sum of

i) the weighting value of at least one currently searched sub-route which is one of the at least one already planned sub-route, said at least one currently searched sub-route leading to a currently searched vector; and

ii) the weighting value associated with the currently searched vector;

d) designating the optimum route, based on a combination of

i) one of the at least one currently searched sub-route;

ii) the currently searched vector; and

iii) a target vector which leads to the destination position.

14. The method of claim 13, wherein the background memory is a compact disc.

15. The method of claim 13 further comprising

prior to the loading step, initializing a search tree for containing the at least one already planned sub-route, and

as part of the designating step, repeating the loading and searching steps until the already planned sub-route leading to the currently searched vector when combined with the currently searched vector forms the optimum route.