Efficiently finding shortest paths using landmarks for computing lower-bound distance estimates

• US 7,603,229 B2
• Filed: 08/25/2004
• Issued: 10/13/2009
• Est. Priority Date: 08/25/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Harrelson, Christopher Robert, Goldberg, Andrew V.
• Primary Examiner(s): Beaulieu; Yonel
• Application Number:
  US10/925,751
• Publication Number:
  US 20060047416A1
• Time in Patent Office: 1,875 Days
• Field of Search: 701200-202, 701208-209, 701/25, 340/988, 342/357.08, 342/357.09
• US Class Current: 701/202
• CPC Class Codes: G01C 21/34 Route searching; Route guidance

Abstract

Methods and systems are described for computing shortest paths among a set of locations. A small set of landmarks is chosen and the distance between each location and each landmark is computed and stored. Given source and destination locations, the landmark distances are used to compute lower-bound estimates of distances from locations to the destination. The estimates are then used with a heuristic search to find the shortest path from source to destination.

Claims

1. A computer-readable storage medium comprising computer-executable instructions facilitating the finding of a shortest path from a starting location to a destination location among a set of locations, the computer-executable instructions, when executed by a computer processor, performing the steps of:

estimating distances to the destination location from locations in the set of locations by using distances between the locations and one or more landmarks from a set of landmarks;

selecting a first unscanned location whose sum of distance from the starting location and estimated distance to the destination location is minimal;

computing the distance from the starting location to other unscanned locations adjacent to the first unscanned location; and

marking the first unscanned location as scanned.

2. The computer-readable storage medium of claim 1 wherein the estimating comprises calculating the difference between:

the distance from a first location in the set of locations to a first landmark in the set of landmarks; and

the distance from the destination location to the first landmark.

3. The computer-readable storage medium of claim 1 wherein the estimating comprises calculating the difference between:

the distance from a first landmark in the set of landmarks to the destination location; and

the distance from the first landmark to a first location in the set of locations.

4. The computer-readable storage medium of claim 3 wherein the estimating further comprises:

computing, for the first location, distance differences for each landmark in a subset of the set of landmarks; and

estimating the distance to the destination location from the first location to be the maximal difference value over the subset of landmarks.

5. The computer-readable storage medium of claim 1 wherein the distances from a location in the set of locations to each landmark in the set of landmarks are stored in a memory with respect to the location.

6. The computer-readable storage medium of claim 5 wherein the differences between the distance from the location to each landmark and the distance from each landmark to the location are stored in a memory with respect to the location.

7. The computer-readable storage medium of claim 5 wherein the distances stored in the memory each occupies approximately 32 bits.

8. The computer-readable storage medium of claim 6 wherein the differences stored in the memory each occupies approximately 16 bits.

9. The computer-readable storage medium of claim 1 further performing the step of selecting the set of landmarks randomly.

10. The computer-readable storage medium of claim 1 further performing the step of selecting the set of landmarks using a planar landmark selection method.

11. The computer-readable storage medium of claim 1 further performing the step of selecting the set of landmarks using a farthest landmark selection method.

12. A computer-readable storage medium comprising computer-executable instructions facilitating the estimating the distance from a first location to the destination location, the computer-executable instructions, when executed by a processor, performing the steps of:

computing a first distance from the first location to a landmark;

computing a second distance from the destination location to the landmark;

calculating a first difference between the first distance and the second distance for estimating the distance from the first location to the destination location;

computing a third distance from the landmark to the destination location;

computing a fourth distance from the landmark to the first location;

calculating a second difference between the third distance and the fourth distance for estimating the distance from the first location to the destination location; and

using the maximum of the first difference and the second difference for estimating the distance from the first location to the destination location.

13. A computer-implemented method of finding a shortest path from a starting location to a destination location among a set of locations, the method comprising:

estimating distances to the destination location from locations in the set of locations by using distances between the locations and one or more landmarks from a set of landmarks;

selecting a first unscanned location whose sum of distance from the starting location and estimated distance to the destination location is minimal;

computing the distance from the starting location to other unscanned locations adjacent to the first unscanned location; and

marking the first unscanned location as scanned.

14. The method of claim 13 wherein the estimating comprises calculating the difference between:

the distance from a first location in the set of locations to a first landmark in the set of landmarks; and

the distance from the destination location to the first landmark.

15. The method of claim 13 wherein the estimating comprises calculating the difference between:

the distance from a first landmark in the set of landmarks to the destination location; and

the distance from the first landmark to a first location in the set of locations.

16. The method of claim 15 wherein the estimating further comprises:

computing, for the first location, distance differences for each landmark in a subset of the set of landmarks; and

estimating the distance to the destination location from the first location to be the maximal difference value over the subset of landmarks.

17. The method of claim 13 wherein the distances from a location in the set of locations to each landmark in the set of landmarks are stored in a memory with respect to the location.

18. The method of claim 17 wherein the differences between the distance from the location to each landmark and the distance from each landmark to the location are stored in a memory with respect to the location.

19. The method of claim 18 wherein the distances stored in the memory each occupies approximately 32 bits.

20. The method of claim 18 wherein the differences stored in the memory each occupies approximately 16 bits.

21. The method of claim 13 further comprising selecting the set of landmarks randomly.

22. The method of claim 13 further comprising selecting the set of landmarks using a planar landmark selection method.

23. A computer-implemented method of estimating the distance from a first location to the destination location, the method comprising:

computing a first distance from the first location to a landmark;

computing a second distance from the destination location to the landmark;

calculating a first difference between the first distance and the second distance for estimating the distance from the first location to the destination location;

computing a third distance from the landmark to the destination location;

computing a fourth distance from the landmark to the first location;

calculating a second difference between the third distance and the fourth distance for estimating the distance from the first location to the destination location; and

comprising using the maximum of the first difference and the second difference for estimating the distance from the first location to the destination location.