Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2002-10-11
2004-09-07
Zenelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S211000, C340S995190
Reexamination Certificate
active
06789012
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to navigational devices, and in particular to PDA systems, functional data, and methods which use optimal data structures and methods to generate a route plan.
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.
Generally, with a navigational aid device, cartographic data is loaded into a memory of the device and manipulated to provide route planning to a user of the device. Selecting the optimal route can be processor and memory intensive since a variety of thoroughfare names, thoroughfare classifications, geographic distances between thoroughfares, time estimates between thoroughfares, and the like must be rapidly processed to provide near instantaneous route planning information to the user of the device. Moreover, as the memory and the processor performance demands increase to provide an acceptable level of processing throughput, the navigational device becomes more expensive for the user to purchase. Additionally, the physical dimensions of the device may increase and correspondingly the portability and attractiveness of the device becomes less appealing to the user.
Additionally, when a navigation device deviates from a provided route plan, the device preferably responds rapidly respond by projecting a new route plan which must be communicated to the user of the device quickly. Otherwise unless the device is completely stopped for some period of time, the device could deviate farther from the projected new route and the device could be rendered useless to the user. Of course, stopping may not be practical when the device is being used within a vehicle on the roadways.
Clearly, 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 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 their vehicle during the recalculation process. Even if the user has the ability to safely stop their vehicle, such as when traveling in a neighborhood, the inconvenience factor is present. Accordingly, it is vitally important for the device to rapidly and often repetitively calculate a dynamic route plan for the device to reach a desired destination. To achieve this result, efficient memory and processor performance are critical.
A variety of techniques addressing a subset of the problem have attempted to alleviate memory and processor bottlenecks, such as requiring the user to load into the device's memory a selected geographic region by connecting the device to a remote storage having a desired region or by requiring the user to connect the device to a computing device and download the desired region from a remote location. Yet, cartographic data are voluminous and even with reduced region selections, current devices require substantial memory to efficiently generate a route plan for a user. Typically, to generate a route plan with a reasonable processor there must be at least 500 kilobytes of available random access memory (RAM), but more likely 2 megabytes or more of available RAM can be required.
In summary, current prior art systems have created a spectrum of products in which the processing throughput of the products is directly related to the capacity of the available RAM of the products. Further, as users demand products with greater functionality the problem continues to escalate proportionally. As a result, products are costly and becoming less portable due to an increase in their physical size.
Therefore, there exists a need for a navigational route planning device which is more efficient and accurate than current systems, without requiring the more expensive system resources, such as increased RAM capacity. In addition, there is also a need for a navigational route planning device which rapidly and efficiently generates a route plan.
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. Devices, systems, functional data, and methods are provided for a navigational route planning device which is more efficient and accurate than current systems, without requiring the more expensive system resources and increased requirements of memory. The devices, systems, functional data, and methods of the present invention offer an improved navigational route planning device which is capable of rapidly generating a more efficient route plan with minimal memory and processor requirements.
In one embodiment of the present invention, a navigational device is provided having a processor, a memory in communication with the processor, and a display in communication with the processor. The device dynamically generates a route path, using the processor and the memory, from a moveable location associated with the device to a destination of the device by repetitively and dynamically expanding one or more adjacent locations and inserting the expanded adjacent locations into a first data structure. At various points in time, one or more first locations of the first data structure will include a then existing least cost location in the route path. The route path is dynamically generated from the moveable location, the first locations of the first data structure, and the destination. Further, at least a portion of the route path is communicated to the display.
In another embodiment of the present invention a navigation system is provided having a mass storage device adapted to store navigation data, a server adapted to communicate with the mass storage; and a navigation device adapted to communicate with and retrieve navigation data from the server via a communication channel, wherein the navigation device includes a processor in communication with a memory. Furthermore, the processor and the memory cooperate to generate a projected route from a starting location, one or more available locations, and an ending location. Each available location has an associated cost. Moreover, each available location is evaluated as the projected route is constructed, if an available location is adjacent to a last inserted available location and has a least cost when compared to costs associated with all available adjacent locations. The adjacent locations are inserted into a first data structure such that a first location of the first data structure is a least cost location of the data structure.
In still another embodiment of the present invention, functional data to select an optimal route is provided. The functional data include a beginning node representative of an initial geographic location, a destination node representative of a desired geographic location, and an optimal route, wherein the optimal route is a path starting with the beginning node and including one or more selected intermediate nodes and ending with the destination node. Moreover, the functional data include one or more available nodes, wherein each available node has a cost associated with the art of including each available node in the path as one of the selected intermediate nodes. Further, as one or more of the available nodes become available for inspection, the available nodes are organized as a first data structure wherein a least cost available node is a first node of the data structure.
In yet another embodiment of the present invention a method for generating a projected
Beesley Darin J.
Childs Michael E.
Garmin Ltd.
Rolf Devon A.
Zenelli Michael J.
LandOfFree
PDA systems, functional data, and methods for generating a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with PDA systems, functional data, and methods for generating a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and PDA systems, functional data, and methods for generating a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3229766