Bucket-oriented route planning method, and navigation system comprising a route planner for carrying out such a method
First Claim
Patent Images
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 summingi) 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
15 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12)
-
-
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. - View Dependent Claims (14, 15)
-
Specification