The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Oct. 13, 2009
Filed:
Aug. 25, 2004
Applicants:
Andrew V. Goldberg, Redwood City, CA (US);
Christopher Robert Harrelson, Berkeley, CA (US);
Inventors:
Andrew V. Goldberg, Redwood City, CA (US);
Christopher Robert Harrelson, Berkeley, CA (US);
Assignee:
Microsoft Corporation, Redmond, WA (US);
Attorney:
Primary Examiner:
Int. Cl.
CPC ...
G01C 21/34 (2006.01);
U.S. Cl.
CPC ...
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.