Data processing: vehicles – navigation – and relative location – Navigation – Determination of travel data based on the start point and...
Reexamination Certificate
2004-08-25
2009-10-13
Beaulieu, Yonel (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Determination of travel data based on the start point and...
C701S209000, C340S995190
Reexamination Certificate
active
07603229
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.
REFERENCES:
patent: 6021372 (2000-02-01), Harrington
patent: 6311125 (2001-10-01), Okano et al.
patent: 6526350 (2003-02-01), Sekiyama
patent: 6559794 (2003-05-01), Nakajima et al.
patent: 6615133 (2003-09-01), Boies et al.
patent: 6785608 (2004-08-01), Milici et al.
B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest Paths Algorithms: Theory and Experimental Evaluation. InProc. 5th ACM-SIAM Symposium on Discrete Algorithms, pp. 516-525, 1994.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest.Introduction to Algorithms. MIT Press, Cambridge, MA, pp. 514-549, 1990.
L. J. Cowen and C. G. Wagner. Compact Roundtrip Routing in Directed Networks. InProc. Symp. on Principles of Distributed Computation, pp. 51-59, 2000.
G. B. Dantzig.Linear Programming and Extensions. Princeton Univ. Press, Princeton, NJ, 1962, chapters 17-19.
D. de Champeaux. Bidirectional Heuristic Search Again.J. ACM, 30(1):22-32, 1983.
E. V. Denardo and B. L. Fox. Shortest-Route Methods: 1. Reaching, Pruning, and Buckets.Oper. Res., 27:161-186, 1979.
E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs.Numer. Math., 1:269-271, 1959.
J. Doran. An Approach to Automatic Problem-Solving. Machine Intelligence, 1:105-123, 1967.
D. Dreyfus. An Appraisal of Some Shortest Path Algorithms. Technical Report RM-5433, Rand Corporation, Santa Monica, CA, 1967.
J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. InProc. 42nd IEEE Annual Symposium on Foundations of Computer Science, pp. 232-241, 2001.
L.R. Ford Jr., and D. R. Fulkerson,Flows in Networks.Princeton Univ. Press, Princeton, NJ, 1962, pp. 130-137.
M. L. Fredman and R. E. Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.J. Assoc. Comput. Mach., 34:596-615, 1987.
G. Gallo and S. Pallottino. Shortest Paths Algorithms.Annals of Oper. Res., 13:3-79, 1988.
A. V. Goldberg. A Simple Shortest Path Algorithm with Linear Average Time. InProc. 9th ESA, Lecture Notes in Computer Science LNCS 2161, pp. 230-241. Springer-Verlag, 2001.
A. V. Goldberg. Shortest Path Algorithms: Engineering Aspects, InProc. ESAAC '01, Lecture Notes in Computer Science. Springer-Verlag, 2001.
A. V. Goldberg and C. Harrelson. Computing the Shortest Path: A Search Meets Graph Theory. Technical Report MSR-TR-2004-24, Microsoft Corp., Redmond, WA, 2004.
A. V. Goldberg and C. Silverstein. Implementations of Dijkstra's Algorithm Based on Multi-Level Buckets. In P. M. Pardalos, D. W. Hearn, and W. W. Hages, editors,Lecture Notes in Economics and Mathematical Systems 450(Refereed Proceedings), pp. 292-327. Springer Verlag, 1997.
R. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. InProc. Algorithm engineering and experimentation: sixth annual international workshop, 2004.
P. E. Hart, N. J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths.IEEE Transactions on System Science and Cybernetics, SSC-4(2), 1968.
T. Ikeda, Min-Yao Hsu, H. Imai, S. Nishimura, H. Shimoura, T. Hashimoto, K. Tenmoku, and K. Mitoh. A Fast Algorithm for Finding Better Routes by AI Search Techniques. InProc. Vehicle Navigation and Information Systems Conference. IEEE, 1994.
R. Jacob, M.V. Marathe, K. Nagel. A Computational Study of Routing Algorithms for Realistic Transportation Networks. Tech. Rep. LA-UR-98-2249, Los Alamos Nat'l Lab., 1999.
P. Klein. Preprocessing an Undirected Planar Network to Enable Fast Approximate Distance Queries. InSODA, pp. 820-827, 2002.
J.B.H. Kwa. BS: An Admissible Bidirectional Staged Heuristic Search Algorithm.Artif. Intell., 38(1):95-109, 1989.
U. Meyer. Single-Source Shortest Paths on Arbitrary Directed Graphs in Linear Average Time. InProc. 12th ACM-SIAM Symposium on Discrete Algorithms, pp. 797-806, 2001.
T. A. J. Nicholson. Finding the Shortest Route Between Two Points in a Network.Computer J., 9:275-280, 1966.
S. Pallottino and M. G. Scutell. A New Algorithm for Reoptimizing Shortest Paths when the Arc Costs Change.Networks, 31:149-160, 2003.
I. Pohl. Bi-directional Search. InMachine Intelligence, vol. 6, pp. 124-140. Edinburgh Univ. Press, Edinburgh, 1971.
F. Schulz, D. Wagner, and C. Zaroliagis. Using Multi-Level Graphs for Timetable Information in Railway Systems. InProc. Algorithm Engineering and Exteriments, pp. 43-59. LNCS, Springer, 2002.
R. Sedgewick and J.S. Vitter. Shortest Paths in Euclidean Graphs.Algorithmica, 1:31-48, 1986.
L. Sint and D. de Champeaux. An Improved Bidirectional Heuristic Search Algorithm, J.ACM, 24(2):177-191, 1977.
R. E. Tarjan.Data Structures and Network Algorithms.Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.
M. Thorup. Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time.J. Assoc. Comput. Mach., 46:362-394, 1999.
M. Thorup. Compact Oracles for Reachability and Approximate Distances in Planar Digraphs. InProc. 42nd IEEE Annual Symposium on Foundations of Computer Science, pp. 242-251, 2001.
D. Wagner and T. Willhalm. Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs. InEuropean Symposium on Algorithms, 2003.
F. B. Zhan and C. E. Noon. Shortest Path Algorithms: An Evaluation using Real Road Networks,Transp. Sci., 32:65-73, 1998.
F. B. Zhan and C. E. Noon. A Comparison Between Label-Setting and Label-Correcting Algorithms for Computing One-to-One Shortest Paths.Journal of Geographic Information and Decision Analysis, 4, 2000.
Goldberg Andrew V.
Harrelson Christopher Robert
Beaulieu Yonel
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
Efficiently finding shortest paths using landmarks for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficiently finding shortest paths using landmarks for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficiently finding shortest paths using landmarks for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4099427