Communications: directive radio wave systems and devices (e.g. – Directive – Including a satellite
Reexamination Certificate
2001-12-20
2003-04-08
Beaulieu, Yonel (Department: 3661)
Communications: directive radio wave systems and devices (e.g.,
Directive
Including a satellite
Reexamination Certificate
active
06545637
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to navigational devices, and in particular to navigational devices with improved route calculation capabilities.
BACKGROUND OF THE INVENTION
Route planning devices are well known in the field of navigational instruments. The method of route planning implemented by known prior art systems depends on the capabilities of system resources, such as processor speed and the amount and speed of memory. As increased system capability also increases system cost, the method of route planning implemented by a navigation device is a function of overall system cost.
One feature of increased system capability involves off-route recalculation capabilities. Many conventional navigational devices simply do not incorporate an off-route recalculation functionality in order to reduce system complexity and maintain a low overall system cost. Some of these devices may alert the user that they are off course, but they do not perform any course recalculation. In these devices, the user must halt their journey or attempt to relocate themselves on the prior planned route via traditional navigation methods, e.g. asking directions or using a conventional map. With some devices, the user may still be able to see the previously planned route, but the user will have to employ his or her own decision making to chart back onto the displayed route. This can be time consuming and provide frustration to a user who is likely unfamiliar with the routes surrounding their errant location.
Additionally, in order to calculate a route it is necessary to select a starting position to begin the route calculation. The route calculation algorithm invariably takes a small but finite amount of time, maybe on the order of 10 to 20 seconds. If the current position of the device is used as the starting position for the route calculation, a new route is generated based on the position that was known historically. Thus, a moving device will have traveled some distance beyond that historical position. In other words, the new route will have a starting point which corresponds to the historical position which may or may not correspond to the device's current position. Thus, if a turn or other maneuver is indicated as a function of getting from the historical position (as known at the time the calculation was started) to a given destination, the device will easily be beyond the turn that was generated by the route calculation algorithm.
While stopping travel during the route calculation process may solve the stated problem of generating a route while in motion, in many cases halting travel is not a viable alternative. For example, when the user is traveling on an interstate it is entirely impossible to simply stop. The alternative of pulling off on the shoulder of a road is undesirable and can be dangerous. Pulling off on an exit is equally undesirable since doing so increases travel time and provides an added inconvenience to the user. In other instances, such as navigating downtown city streets, the traffic issues alone may prevent the user from stopping his or her vehicle during the recalculation process. Even if the user has the ability to safely stop his or her vehicle, such as when traveling in a neighborhood, the inconvenience factor is present.
In summary, current prior art systems have created a spectrum of products in which the degree of navigational accuracy is dictated primarily by the cost of the system. The lower cost systems currently offer a low degree of accuracy that is often inadequate for users. Therefore, there exists a need for a navigational route planning device which is more efficient and accurate than current low cost systems, without requiring more expensive system resources. In addition, there is also a need for a navigational route planning device which provides a user with more understandable, accurate and timely route calculation capabilities.
SUMMARY OF THE INVENTION
The above mentioned problems of navigational devices are addressed by the present invention and will be understood by reading and studying the following specification. Systems and methods are provided for a navigational route planning device which is more efficient and accurate than current low cost systems, without requiring the more expensive system resources. The systems and methods of the present invention offer an improved navigational route planning device which provides a user with more understandable, accurate and timely route calculation capabilities.
In one embodiment of the present invention, an electronic navigational aid device with improved route calculation capabilities is provided. The navigational aid device includes a processor with a display connected to the processor. A memory is connected to the processor as well. The memory includes cartographic data and a route to a desired destination stored therein. The cartographic data includes data indicative of thoroughfares of a plurality of types. The device processes travel along the route. The device is capable of selecting an appropriate starting point for a route calculation and capable of recognizing when the device has deviated from a route. When the device is off-route, the device calculates a new route to navigate to the desired destination. In order to select an appropriate starting point for the route calculation or recalculation, the device adjusts a starting point for the new route to a location forward along a current thoroughfare on which the device is located or traveling such that the device is on the route at a time when the new route calculation is completed.
These and other embodiments, aspects, advantages, and features of the present invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art by reference to the following description of the invention and referenced drawings or by practice of the invention. The aspects, advantages, and features of the invention are realized and attained by means of the instrumentalities, procedures, and combinations particularly pointed out in the appended claims.
REFERENCES:
patent: 5537323 (1996-07-01), Schulte
patent: 5559511 (1996-09-01), Ito et al.
patent: 5659476 (1997-08-01), LeFebvre et al.
patent: 5757289 (1998-05-01), Nimura et al.
patent: 5774073 (1998-06-01), Mackawa et al.
patent: 5926118 (1999-07-01), Hayashida et al.
patent: 6285950 (2001-09-01), Tanimoto
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: 2001/0047242 (2001-11-01), Ohta
“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 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—Univeristy 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).
Zhao, Y., et al., “An Adaptive Route-guidance Algorithm for Intelligent Vehicle Highway S
Burgett Scott M.
Childs Michael
Krull Jay Dee
Walters Thomas H.
Beaulieu Yonel
Garmin Ltd.
Schwegman Lundberg Woessner & Kluth P.A.
LandOfFree
Systems and methods for a navigational device with improved... 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 and methods for a navigational device with improved..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for a navigational device with improved... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3014336