Bucket-oriented route planning method, and navigation system comprising a route planner for carrying out such a method
AssigneeU.S. Philips Corporation
InventorRik A. Verstraete
Life of this patent
Estimating the term…
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.
Claims15
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.
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.
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.
Dependencies are inferred from the claim text.