Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2005-12-13
2005-12-13
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S211000, C340S995190
Reexamination Certificate
active
06975940
ABSTRACT:
Devices, systems, functional data and methods are provided for an improved route generation in navigational enabled devices. 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: 3660812 (1972-05-01), Inose et al.
patent: 3883847 (1975-05-01), Frank
patent: 4827419 (1989-05-01), Selby, III
patent: 4926336 (1990-05-01), Yamada
patent: 4937753 (1990-06-01), Yamada
patent: 5208593 (1993-05-01), Tong et al.
patent: 5272638 (1993-12-01), Martin et al.
patent: 5343399 (1994-08-01), Yokoyama et al.
patent: 5371497 (1994-12-01), Nimura et al.
patent: 5410486 (1995-04-01), Kishi et al.
patent: 5452212 (1995-09-01), Yokoyama et al.
patent: 5452217 (1995-09-01), Kishi et al.
patent: 5475599 (1995-12-01), Yokoyama et al.
patent: 5506578 (1996-04-01), Kishi et al.
patent: 5528248 (1996-06-01), Steiner et al.
patent: 5537323 (1996-07-01), Schulte
patent: 5546107 (1996-08-01), Deretsky et al.
patent: 5638279 (1997-06-01), Kishi et al.
patent: 5712788 (1998-01-01), Liaw et al.
patent: 5729109 (1998-03-01), Kaneko et al.
patent: 5729458 (1998-03-01), Poppen
patent: 5739772 (1998-04-01), Nanba et al.
patent: 5793631 (1998-08-01), Ito et al.
patent: 5809447 (1998-09-01), Kato et al.
patent: 5821887 (1998-10-01), Zhu
patent: 5845282 (1998-12-01), Alley et al.
patent: 5874905 (1999-02-01), Nanba et al.
patent: 5878368 (1999-03-01), DeGraaf
patent: 5893081 (1999-04-01), Poppen
patent: 5902349 (1999-05-01), Endo et al.
patent: 5938721 (1999-08-01), Dussell et al.
patent: 5946692 (1999-08-01), Faloutsos et al.
patent: 5951622 (1999-09-01), Nomura
patent: 5953722 (1999-09-01), Lampert et al.
patent: 5977885 (1999-11-01), Watanabe
patent: 5978730 (1999-11-01), Popen et al.
patent: 5995970 (1999-11-01), Robinson et al.
patent: 6021406 (2000-02-01), Kuznetsov
patent: 6023655 (2000-02-01), Nomura
patent: 6038559 (2000-03-01), Ashby et al.
patent: 6047280 (2000-04-01), Ashby et al.
patent: 6052645 (2000-04-01), Harada
patent: 6061003 (2000-05-01), Harada
patent: 6061630 (2000-05-01), Walgers et al.
patent: 6073076 (2000-06-01), Crowley et al.
patent: 6088652 (2000-07-01), Abe
patent: 6112200 (2000-08-01), Livshutz et al.
patent: 6121314 (2000-09-01), Richter et al.
patent: 6121900 (2000-09-01), Takishita
patent: 6122593 (2000-09-01), Friederich et al.
patent: 6128515 (2000-10-01), Kabler et al.
patent: 6128573 (2000-10-01), Nomura
patent: 6151552 (2000-11-01), Koizumi et al.
patent: 6161092 (2000-12-01), Latshaw et al.
patent: 6169956 (2001-01-01), Morimoto et al.
patent: 6172641 (2001-01-01), Millington
patent: 6182010 (2001-01-01), Berstis
patent: 6192314 (2001-02-01), Khavakh et al.
patent: 6199013 (2001-03-01), O'Shea
patent: 6199045 (2001-03-01), Giniger et al.
patent: 6202024 (2001-03-01), Yokoyama et al.
patent: 6202026 (2001-03-01), Nimura et al.
patent: 6219457 (2001-04-01), Potu
patent: 6249740 (2001-06-01), Ito et al.
patent: 6259988 (2001-07-01), Galkowski et al.
patent: 6263276 (2001-07-01), Yokoyama et al.
patent: 6263277 (2001-07-01), Tanimoto et al.
patent: 6266612 (2001-07-01), Dussell et al.
patent: 6266615 (2001-07-01), Jin
patent: 6285951 (2001-09-01), Gaskins et al.
patent: 6292743 (2001-09-01), Pu et al.
patent: 6298303 (2001-10-01), Khavakh et al.
patent: 6308177 (2001-10-01), Israni et al.
patent: 6314365 (2001-11-01), Smith
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: 6324467 (2001-11-01), Machii et al.
patent: 6349257 (2002-02-01), Liu et al.
patent: 6381535 (2002-04-01), Durocher et al.
patent: 6393149 (2002-05-01), Friederich et al.
patent: 6401034 (2002-06-01), Kaplan et al.
patent: 6401035 (2002-06-01), Jin
patent: 6405123 (2002-06-01), Rennard et al.
patent: 6411899 (2002-06-01), Dussell et al.
patent: 6460046 (2002-10-01), Meek
patent: 6477526 (2002-11-01), Hayashi et al.
patent: 6484093 (2002-11-01), Ito et al.
patent: 6504496 (2003-01-01), Mesarovic et al.
patent: 6505123 (2003-01-01), Root et al.
patent: 6510379 (2003-01-01), Hasegawa et al.
patent: 6512525 (2003-01-01), Capps et al.
patent: 6532152 (2003-03-01), White et al.
patent: 6535743 (2003-03-01), Kennedy et al.
patent: 6563440 (2003-05-01), Kangas
patent: 6567743 (2003-05-01), Mueller et al.
patent: 6574553 (2003-06-01), Beesley et al.
patent: 6574554 (2003-06-01), Beesley et al.
patent: 6594666 (2003-07-01), Biswas et al.
patent: 6615131 (2003-09-01), Rennard et al.
patent: 6633809 (2003-10-01), Aizono et al.
patent: 6650996 (2003-11-01), Beesley et al.
patent: 6674849 (2004-01-01), Froeberg
patent: 6675093 (2004-01-01), Childs et al.
patent: 6704645 (2004-03-01), Beesley et al.
patent: 6725155 (2004-04-01), Takahashi et al.
patent: 6775612 (2004-08-01), Kao et al.
patent: 6799115 (2004-09-01), Childs et al.
patent: 6807483 (2004-10-01), Chao et al.
patent: 6823256 (2004-11-01), Burt
patent: 6839624 (2005-01-01), Beesley et al.
patent: 6845322 (2005-01-01), Chao et al.
patent: 6847890 (2005-01-01), Childs et al.
patent: 6850842 (2005-02-01), Park
patent: 6856893 (2005-02-01), Beesley et al.
patent: 6856900 (2005-02-01), Childs et al.
patent: 6892135 (2005-05-01), Krull et al.
patent: 6898520 (2005-05-01), Kao et al.
patent: 2001/0043745 (2001-11-01), Frederich et al.
patent: 2001/0045949 (2001-11-01), Chithambaram et al.
patent: 2001/0056327 (2001-12-01), Jin
patent: 2002/0040271 (2002-04-01), Park et al.
patent: 2002/0091527 (2002-07-01), Shiau
patent: 2002/0102988 (2002-08-01), Myllymaki
patent: 2002/0120753 (2002-08-01), Levanon et al.
patent: 2002/0164998 (2002-11-01), Younis
patent: 2002/0173905 (2002-11-01), Jin
patent: 2003/0006913 (2003-01-01), Joyce et al.
patent: 2003/0006918 (2003-01-01), Barnett
patent: 2003/0013483 (2003-01-01), Ausems et al.
patent: 2003/0045301 (2003-03-01), Wollrab
patent: 2003/0045998 (2003-03-01), Medl
patent: 2003/0048599 (2003-03-01), Martin
patent: 2003/0069899 (2003-04-01), Brown et al.
patent: 2003/0105845 (2003-06-01), Leemakers
patent: 2003/0131023 (2003-07-01), Bassett et al.
patent: 2003/0131059 (2003-07-01), Brown et al.
patent: 2003/0139150 (2003-07-01), Rodriguez et al.
patent: 2004/0220726 (2004-11-01), Jin
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 Shortes 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 the ACM, 34(3), 2 pages, (1987).
Fu, L., “Heuristic Shortest Path Algorithms and their Potential IVHS Applications”, Proceedings of the Fourth University of Alberta—University of Calagary, Joint Graduate Study 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, AAA1 press, S
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-3514735