Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2005-02-15
2005-02-15
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S211000, C340S995190
Reexamination Certificate
active
06856900
ABSTRACT:
Devices, systems, functional data and methods are provided for an improved route generation in navigational enabled devices. The navigational device with route generation capabilities includes a processor communicating with a memory. The memory includes a current location of the device, one or more available locations, and a destination of the device. A display communicates with the processor and is capable of communicating at least a portion of a generated route for the device.In generating the route, the available locations are inspected repetitively and locations adjacent to a last selected location are inserted into a first data structure such that the first location of the first data structure is always a least cost location associated with all adjacent locations comprising the first data structure. The first location is then optionally inserted into a second data structure. The generated route includes the current location, one or more first locations, and the destination.
REFERENCES:
patent: 5938721 (1999-08-01), Dussell et al.
patent: 5953722 (1999-09-01), Lampert et al.
patent: 6121314 (2000-09-01), Richter et al.
patent: 6259988 (2001-07-01), Galkowski et al.
patent: 6285951 (2001-09-01), Gaskins et al.
patent: 6317684 (2001-11-01), Roeseler et al.
patent: 6317687 (2001-11-01), Morimoto et al.
patent: 6321158 (2001-11-01), DeLorme et al.
patent: 6477526 (2002-11-01), Hayashi et al.
patent: 10-132594 (1998-05-01), None
“An optimal pathfinder for vehicles in real-world digital terrain maps”, http://www.nease.net/jamsoft/shortestpath/pathfinder/4-html, 11 pages, (1999).
“Informed Search Methods”,Artificial Intelligence. A Modern Approach,Prentice Hall, Inc., pp. 92-115, (1995).
“Real-Time Vehicle Routing in Dynamic and Stochastic Urban Traffic Networks”, http://www.gpu.srv.ualberta.ca/, lfu/research.htm, pp. 1-3, (1997).
Ahuja, R., et al., “Faster Algorithms for the Shortest Path Problem”,Journal of the Association for Computing Machinery, 37 (2),pp. 213-223, (1990).
Chung, V., et al., “An Efficient Implementation of Parallel A ”,CFPAR,Montreal, Canada, pp. 153-167, (1994).
Fredman, M., et al., “Fibonacci heaps and their uses in improved network optimization algorithms”,Journal of ACM, 34 (3),2 pages, (1987).
Fu, L., “Beuristic Shortest Path Algorithms and their Potential IVES Applications”,Proceedings of the Fourth University of Alberta-University of Calgary, Joint Graduate Student Symposium in Transportation Engineering,pp. 83-109, (1995).
Ikeda, T., et al., “A Fast Algorithm for Finding Better Routes by AI Search Techniques”,Vehicle Navigation and Information Systems Conference Proceedings,pp. 291-296, (1994).
Kaindl, H., et al., “Memory-Bounded Bidirectional Search”,Proceedings of the 12th National Conference on Art,AAAI Press, Seattle, WA, pp. 1359-1364, (1994).
Laporte, G., “The Vehicle Routing Problem: An overview of exact and approximate algorithms”,European Journal of Operational Research, 59,pp. 345-358, (1992).
Myers, B., “Data Structures for Best-First Search”, http://www4.ncsu.edu/jbmyers/dsai.htm, pp. 1-6, (1997).
Ronngren, R., et al., “Parallel and Sequential Priority Queue Algorithms”,ACM Transactions on Modeling and Computer Simulation, 7(2),pp. 168-172, 198. 19, (1997).
Stout, B., “Smart Moves: Intelligent Pathfinding”,Gamasutra,http://www.ganasutra.com/features/programming/080197/pathfinding.htm, pp. 1-11, (1997).
Wai, L., et al., “Comparative Study of Shortest Path Algorithm for Transport Network”,USRP Report 2,http://www.comp.nus.edu.sq/, leonghoe/USRPreport-txt.html, pp. 1-10, (1999).
Zhan, F.B., “Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures”,Journal of Geographic Information and Decision Analysis, 1(1),http://www.geog.uno.ca/gimda /journal/vol1.1/Zhan/Zhan.htm, 11 pages, (1997).
Zhao, Y., et al., “An Adaptive Route-Guidance Algorithm for Intelligent Vehicle Highway Systems”,American Control Conference, Boston, MA,Department of Electrical Engineering and Computer Science, The University of Michigan, pp. 2568-2573. (1991).
Oberhauser et al.; Fast data structures for shortest path routing: a comparative evaluation; 1995 IEEE International Conference on Gateway to Globalization; Jun. 1995; vol. 3, pgs. 1597-1601.
Beesley Darin J.
Childs Michael
Garmin Ltd.
Rolf Devon A.
Zanelli Michael J.
LandOfFree
Systems, functional data, and methods for generating a route does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems, functional data, and methods for generating a route, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems, functional data, and methods for generating a route will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3513978