Systems, functional data, and methods for generating a route

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.

FIELD OF THE INVENTION

The present invention relates generally to navigational devices, and in particular to navigational devices having navigation 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 OD 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 route is provided wherein an initial starting location and an ending location are received and one or more available locations existing between the starting location and the ending location are identified. Moreover, a first evaluation is initiated by beginning with the starting location and proceeding to the ending location and selecting one or more adjacent locations from the available locations. As one or more of the adjacent locations are selected, each of the selected adjacent locations arm inserted into a first data structure such that a first location of the first data structure is always associated with a least cost location of the first data structure. Further, the projected route is generated from the starting location, one or more of the selected adjacent locations, which occupy the first location of the first data structure, and the ending location.

DETAILED DESCRIPTION OF THE INVENTION

The present invention is drawn to navigational systems and devices having route generation capabilities. One type of navigational system includes Global Positioning Systems (GPS). Such systems are known and have a variety of uses. In general, GPS is a satellite-based radio navigation system capable of determining continuous position, velocity, time, and in some instances direction information for an unlimited number of users. Formally known as NAVSTAR, the GPS incorporates a plurality of satellites which orbit the earth in extremely precise orbits. Based on these precise orbits, GPS satellites can relay their location to any number of receiving units.

The GPS system is implemented when a device specially equipped to receive GPS data begins scanning radio frequencies for GPS satellite signals. Upon receiving a radio signal from a GPS satellite, the device can determine the precise location of that satellite via one of different conventional methods. The device will continue scanning for signals until it has acquired at least three different satellite signals. Implementing geometrical triangulation, the receiver utilizes the three known positions to determine its own two-dimensional position relative to the satellites. Additionally, acquiring a fourth satellite signal will allow the receiving device to calculate its three-dimensional position by the same geometrical calculation. The positioning and velocity data can be updated in real time on a continuous basis by an limited number of users.

In fact, although GPS enabled devices are often used to describe navigational devices, it will be readily appreciated that satellites need not be used at all to determine a geographic position of a receiving unit, since cellular towers or any customized transmitting radio frequency towers can be deployed and combined in groups of three or more. With such a configuration, any standard geometric triangulation algorithm can be used to determine the exact location of the receiving unit. In this way, personal hand held devices, cell phones, intelligent appliances, intelligent apparel, and others can be readily located geographically, if appropriately equipped to be a receiving unit.

FIG. 1shows one representative view of a GPS denoted generally by reference numeral100. A plurality of satellites120are in orbit about the Earth124. The orbit of each satellite120is not necessarily synchronous with the orbits of other satellites120and, in fact, is likely asynchronous. A GPS receiver device140of the present invention is shown receiving spread spectrum GPS satellite signals160from the various satellites120.

The spread spectrum signals160continuously transmitted from each satellite120utilize a highly accurate frequency standard accomplished with an extremely accurate atomic clock. Each satellite120, as part of its data signal transmission160, transmits a data stream indicative of that particular satellite120. It will be appreciated by those skilled in the relevant art that the GPS receiver device140must acquire spread spectrum GPS satellite signals160from at least thee satellites120for the GPS receiver device140to calculate its two-dimensional position by triangulation. Acquisition of an additional signal160, resulting in signals160from a total of four satellites120, permits GPS receiver device140to calculate its three-dimensional position.

Of course as previously presented and as is readily appreciated by those skilled in the art, GPS satellites and GPS receiving devices are not required by the tenets of the present invention, since any receiving device capable or receiving the location from at least three transmitting locations can perform basic triangulation calculations to determine the relative position of the receiving device with respect to the transmitting locations.

For example, at least three cellular towers can each transmit their location information to a receiving cellular phone, or any other receiving device, and if the phones or devices are equipped to perform the triangulation algorithm, then the location of the cellular phone or device can be readily resolved. By further way of example, an amusement park or entertainment facility can deploy three or more transmitting radio frequency devices and provide users with receiving units capable of performing a triangulation algorithm to determine the receiving units location, within the amusement park or entertainment facility. In this way, it is readily apparent that a receiving unit need not be exclusively GPS enabled to benefit from the teachings of the present invention.

FIGS. 2A and 2Billustrate views for one embodiment of an electronic navigational device230according to the teachings of the present invention. As one of ordinary skill in the art will understand upon reading this disclosure, the device can be portable and can be utilized in any number of implementations such as automobile, personal marine craft, and avionic navigation. Moreover, the device can be used independent of any vehicle or craft such as, and by way of example only, a pedestrian using the device for navigation

InFIG. 2Aa front view of one embodiment230is provided showing the navigational device having a generally rectangular housing232, which is constructed of resilient material and has been rounded for aesthetic and ergonomic purposes. As shown inFIG. 2A, a control face234has access slots for an input key pad238, other individual keys239, and a display screen236. In one embodiment, the display screen236is a LCD display which is capable of displaying both text and graphical information. The invention, however, is not so limited.

InFIG. 2B, a side view of the navigational device230is provided.FIG. 2Billustrates that the device's housing232is defined by an outer front case240and a rear case242. As shown inFIG. 2B, the outer front case240is defined by the control face234. In the embodiment shown inFIG. 2B, the outer front case240and the rear case242are made of one molded piece or separate molded pieces to form the device housing232and support input key pad238, other individual keys239, and display screen236in respective access slots shown in the control face234of FIG.2A.

FIGS. 3A-3Cillustrate views for another embodiment of an electronic navigational device310according to the teachings of the present invention. The navigational device310shown inFIGS. 3A-3Cincludes a personal digital assistant (PDA) with integrated GPS receiver and cellular transceiver according to the teachings of the present invention. The GPS integrated PDA operates with an operating system (OS) such as, for example, the well-known Palm or Pocket PC operating systems, or the lesser-used Linux OS. As shown in the top view ofFIG. 3A, the GPS integrated PDA310includes an internal integrated GPS patch antenna314and a cellular transceiver316contained in a housing318. The housing318is generally rectangular with a low profile and has a front face320extending from a top end322to a bottom end324. Mounted on front face320is a display screen326, which is touch sensitive and responsive to a stylus330(shown stored in the side view ofFIG. 3B) or a finger touch.FIGS. 3A-3Cillustrate the stylus330nested within housing318for storage and convenient access in a conventional manner. The embodiment shown inFIG. 3Aillustrates a number of control buttons, or input keys328positioned toward the bottom end324. The invention, however, is not so limited and one of ordinary skill in the art will appreciate that the input keys328can be positioned toward the top end322or at any other suitable location. The end view ofFIG. 3Cillustrates a map data cartridge bay slot332and headphone jack334provided at the top end322of the housing318. Again, the invention is not so limited and one of ordinary skill in the art will appreciate that a map data cartridge bay slot332and headphone jack334can be provided at the bottom end324, separately at opposite ends, or at any other suitable location.

It should be understood that the structure of GPS integrated PDA310is shown as illustrative of one type of integrated PDA navigation device. Other physical structures, such as a cellular telephone and a vehicle-mounted unit are contemplated within the scope of this invention.

FIGS. 2A-2Band3A-3C are provided as illustrative examples of hardware components for a navigational device according to the teachings of the present invention. However, the invention is not limited to the configuration shown inFIGS. 2A-2Band3A-3C. One of ordinary skill in the art will appreciate other suitable designs for a hardware device which can accommodate the present invention.

FIG. 4Ais a block diagram of one embodiment for the electronic components within the hardware ofFIGS. 2A-2B, such as within housing332and utilized by the electronic navigational device. In the embodiment shown inFIG. 4A, the electronic components include a processor410which is connected to an input420, such as keypad420via line425. It will be understood that input420can alternatively be a microphone for receiving voice commands. Processor410communicates with memory430via line435. Processor410also communicates with display screen440via line445. An antenna/receiver450, such as a GPS antenna/receiver is connected to processor410via line455. It will be understood that the antenna and receiver, designated by reference numeral450, are combined schematically for illustration, but that the antenna and receiver may be separately located components, and that the antenna may be a GPS patch antenna or a helical antenna. The electronic components further include I/O ports470connected to processor410via line475.

FIG. 4Bis a block diagram of one embodiment for the electronic components within the hardware ofFIGS. 3A-3Cand utilized by the GPS integrated PDA310according to the teachings of the present invention. The electronic components shown inFIG. 4Binclude a processor436which is connected to the GPS antenna414through GPS receiver438via line441. The processor436interacts with an operating system (such as PalmOS; Pocket PC, and others) that runs selected software depending on the intended use of the PDA310. Processor436is coupled with memory442such as RAM via line444, and power source446for powering the electronic components of PDA310. The processor436communicates with touch sensitive display screen426via data line448.

The electronic components further include two other input sources that are connected to the processor436. Control buttons428are connected to processor436via line451and a map data cartridge433inserted into cartridge bay432is connected via line452. A conventional serial I/O port454is connected to the processor436via line456. Cellular antenna416is connected to cellular transceiver458, which is connected to the processor436via line466. Processor436is connected to the speaker/headphone jack434via line462. The PDA310may also include an infrared port (not shown) coupled to the processor436that may be used to beam information from one PDA to another.

As will be understood by one of ordinary skill in the art, the electronic components shown inFIGS. 4A and 4Bare powered by a power source in a conventional manner. As will be understood by one of ordinary skill in the art, different configurations of the components shown inFIGS. 4A and 4Bare considered within the scope of the present invention. For example, in one embodiment, the components shown inFIGS. 4A and 4Bare in communication with one another via wireless connections and the like. Thus, the scope of the navigation device of the present invention includes a portable electronic navigational aid device.

According to the teachings of the present invention, the electronic components embodied inFIGS. 4A and 4Bare adapted to provide an electronic navigational aid device with efficient route path generation and communication. That is, according to the teachings of the present invention a processor410is provided with the electronic navigational aid device. A memory430is in communication with the processor. The memory430includes cartographic date, a current device location, and a generated route to a desired destination stored therein. The cartographic data include data indicative of thoroughfares of a plurality of types. A display440is in communication with the processor410and is capable of displaying the cartographic data to a user. The electronic navigational aid device processes a user's travel along the generated route using a set of processing algorithms and cartographic data stored in memory to operate on signals (e.g., GPS signals, received from the antenna/receiver450or any wireless signals) as the same will be known and understood by one of ordinary skill in the art upon reading this disclosure.

As shown inFIGS. 4A and 4B, the device further includes a display440in communication with the processor410and the memory430. The display440is adapted to display a “convergence” and/or a “solution,” as the terms have been described herein, between any two of the number of locations. According to the teachings of the present invention, the device incorporates these and other functions as will be explained in more detail below in connection withFIGS. 6-9.

Moreover, it will be readily appreciated that the various electrical components shown inFIGS. 4A and 4Bneed not be physically connected to one another since wireless communication among the various depicted components is permissible and intended to fall within the scope of the present invention.

FIG. 5is a block diagram of an embodiment of a navigation system according to the teachings of the present invention. The navigation system includes a server502. According to one embodiment, the server502includes a processor504operably coupled to memory506, and further includes a transmitter508and a receiver510to send and receive communication signals. The transmitter508and receiver510are selected or designed according to the communication requirements and the communication technology used in the communication design for the navigation system. The functions of the transmitter508and the receiver510can be combined into a single transceiver.

The navigation system further includes a mass data storage512coupled to the server502via communication link514. The mass data storage512contains a store of navigation data. One of ordinary skill in the art will understand, upon reading and comprehending this disclosure, that the mass data storage512can be separate device from the server502or can be incorporated into the server502.

The navigation system further includes a navigation device516adapted to communicate with the server502through the communication channel518. According to one embodiment, the navigation device516includes a processor and memory, as previously shown and described with respect to the block diagrams ofFIGS. 4A and 4B. Furthermore, the navigation device516includes a transmitter520and receiver522to send and receive communication signals through the communication channel518. The transmitter520and receiver522are selected or designed according to the communication requirements and the communication technology used in the communication design for the navigation system. The functions of the transmitter520and receiver522can be combined into a single transceiver.

Software stored in the server memory506provides instructions for the processor504and allows the server502to provide services to the navigation device516. One service provided by the server502involves processing requests from the navigation device516and transmitting navigation data from the mass data storage512to the navigation device516. According to one embodiment, another service provided by the server502includes processing the navigation data using various algorithms for a desired application, and sending the results of these calculations to the navigation device516.

The communication channel518is the propagating medium or path that connects the navigation device516and the server502. According to one embodiment, both the server502and the navigation device516include a transmitter for transmitting data through the communication channel and a receiver for receiving data that has been transmitted through the communication channel.

The communication channel518is not limited to a particular communication technology. Additionally, the communication channel518is not limited to a single communication technology; that is, the channel518can include several communication links that use a variety of technology. For example, according to various embodiments, the communication channel is adapted to provide a path for electrical, optical, and/or electromagnetic communications. As such, the communication channel includes, but is not limited to, one or a combination of the following: electrical circuits, electrical conductors such as wires and coaxial cables, fiber optic cables, converters, radio-frequency (RF) waveguides, the atmosphere, and empty space. Furthermore, according to various embodiments, the communication channel includes intermediate devices such as routers, repeaters, buffers, transmitters, and receivers, for example.

In one embodiment, for example, the communication channel518includes telephone and computer networks. Furthermore, in various embodiments, the communication channel516is capable of accommodating wireless communication such as radio frequency, microwave frequency and infrared communication, and the like. Additionally, according to various embodiments, the communication channel516accommodates satellite communication.

The communication signals transmitted through the communication channel518include such signals as may be required or desired for a given communication technology. For example, the signals can be adapted to be used in cellular communication technology, such as time division multiple access (TDMA), frequency division multiple access (FDMA), code division multiple access (CDMA), global system for mobile communications (GSM), and the like. Both digital and analog signals can be transmitted through the communication channel518. According to various embodiments, these signals are modulated, encrypted and/or compressed signals as can be desirable for the communication technology.

The mass data storage includes sufficient memory for the desired navigation application Examples of mass data storage include magnetic data storage media such as hard drives, optical data storage media such as CD ROMs, charge among data storage media such as Flash memory, and molecular memory. Moreover, as one skilled in the art will readily appreciate the mass storage need not be a single device as a plurality of storage devices can be logically associated to form a distributed mass storage device of the present invention.

According to one embodiment of the navigation system, the502server includes a remote server accessed by the navigation device516through a wireless channel. According to other embodiments of the navigation system, the server502includes a network server located on a local area network (LAN), wide area network (WAN), a virtual private network (VPN) and server farms.

According to another embodiment of the navigation system, the server502includes a personal computer such as a desktop or laptop computer. In one embodiment, the communication channel518is a cable connected between the personal computer and the navigation device. According to one embodiment, the communication channel518is a wireless connection between the personal computer and the navigation device516.

FIG. 5presents yet another embodiment for a collective set of electronic components adapted to the present invention. As one of ordinary skill in the art will understand upon reading this disclosure, the navigation system ofFIG. 5is adapted to the present invention in a manner distinguishable from that described and explained in detail in connection withFIGS. 4A and 4B.

The mass storage device512connected to the server can include volumes more cartographic and route data than that which is able to be maintained on the navigational device516itself. In this embodiment, the server502processes the majority of a user's travel along the route using a set of processing algorithms and the cartographic and route data stored in memory512and can operate on signals e.g. GPS signals, originally received by the navigational device516. Similar to the navigational device ofFIGS. 4A and 4B, the navigation device516in the system is outfitted with a display524and GPS capabilities526.

FIG. 6shows a block diagram for one embodiment of a navigation device600according to the teachings of the present invention. The navigational device600includes a processor630, a memory620in communication with the processor630, wherein the device630dynamically generates a route path640using the processor630and the memory620from a moveable location650associated with the device600to a destination670. Furthermore, the navigational device600illustrated inFIG. 6, can be embodied in previously presentedFIGS. 4A,4B, and5.

The route path640is dynamically generated by repetitively expanding one or more adjacent locations. Adjacent locations can in one embodiment be thoroughfare intersections directly connected to a last selected least cost adjacent location660. As will be readily appreciated by those skilled in the art, there can be a variety of ways to electronically represent intersections or thoroughfares with cartographic data of the present invention and all are intended to fall within the scope of the present invention.

In one embodiment, adjacent locations or intersections are represented as unique nodes with each node having a node identification number. These node identifications can then be stored in a data structure such as an array, where direct access to the node is acquired by accessing the element of the array referenced by the node identification number. For example, a node having a node identification of5and having additional cartographic data associated with the node can directly access the 5thelement of array “A” to acquire the relevant cartographic data with the a single reference of A[5], or A[5−1] where the array begins with a 0thelement.

Once a node's cartographic data are directly referenced, an additional data structure is immediately available to acquire additional relevant data such as all the node identifications connected to the referenced node, distance from the referenced node to each connected node, thoroughfare classifications associated with the thoroughfare used to connect the referenced node to each connected node, historic elapsed time of travel data associated with traveling from the referenced node to each connected node, a particular user's travel time or speed in traveling from the referenced node to each of the connected nodes, and like. Further, as one of ordinary skill in the art will appreciate, a user can-be proximate to the device. However, the invention is not so limited.

Additionally, the device's600moveable location650can equally be associated with a nearest node identification, and the device's600destination670likewise associated with a node identification. By manipulating the cartographic data, as node identification numbers directly indexed and referenced to acquire additional cartographic data, the problem associated with generating the route path640is reduced to manipulating numbers (e.g, node identifications).

In this way, the device600can use any recognized triangulation algorithm or any other algorithm to readily identify it's present moveable location650and optionally the device's speed of travel, which is dynamically changing as the device600moves. Furthermore, a user inputs or otherwise provides to the device600a destination670. Nearly instantaneously the processor630, identifies a node identification associated with the present moveable location650and a second node identification associated with the destination670.

Next, the processor630in cooperation with the memory620using a set of executable instructions begins an evaluation to generate the route path640. This can be a single evaluation starting with the moveable location650progressing towards the destination670, or starting with the destination670and progressing towards the moveable location650. Alternatively, the evaluation can be two concurrent evaluations occurring at both the moveable location650and the destination670until a developing route path640converges or intersects at one or more node identifications.

As a single evaluation or as multiple evaluations progresses, each then existing node identification is expanded to produce its adjacencies (e.g., connected node identifications). A cost value is assigned to each expanded or opened node identification, this cost in one embodiment is a single integer value, although as one skilled in the art will appreciate the value can include multiple data types or structures of data and the present invention is not intended to be constrained by any particular implementation of a cost value. The cost for each opened node can be readily calculated in a variety of ways, such as by adding the distance from the last selected node which was inserted into the route path640to the opened node being evaluated plus adding a linear distance associated with traveling in a straight line from the opened node to the destination670. Alternatively, time of travel can be used to determine a cost value associated with an opened node, a combination of distance and time of travel, user's or operator's habits in traveling, traversing or directing the device to the opened node, and others.

Once an opened adjacent node has a cost associated with it, the estimated cost relative to moving the device600from the moveable location650to the destination670, it is inserted into a first data structure665. Once all opened adjacent nodes are inserted into the first data structure665, the first location or first node of that data structure is the least cost node. This least cost node becomes a selected least cost adjacent location660and can eventually comprise at least a portion of the dynamically generated route path640.

As one skilled in the art will readily appreciate, this single data structure organized to always have the least cost node as its root or first node, provides direct access to selecting an optimal node while generating the route path640, while reducing a capacity requirement of the memory620since parallel or multiple data structures are not required. In other words, without the least cost node being the root node double keys will need to be maintained in parallel data structures resulting in wasted memory, since the node identification as well as the cost node will need maintained in an efficient and readily accessible data structure. As one skilled in the art will appreciate, having the node identification permits more efficient and rapid searching to determine if a node under evaluation has already been explored.

Furthermore, the moveable location650, the selected least cost adjacent locations660, and the destination670can be stored in a separate second data structure680until the route path640is generated. In this way the route path640is readily assembled and communicated to the display610of the device600. As will be appreciated the display can be operable to include an interface device612which audibly communicates at least portions of the route path640to the device. Accordingly, the display610can be audibly enabled as well as graphically enabled.

Moreover, in one embodiment the first data structure665is a treap organized as a binary tree (e.g., node identifications used to keep binary order) but in heap order (e.g., with respect to cost nodes), such that the root is always the least cost node. A treap data structure includes a binary tree organized in heap and binary tree order, such that the least cost node of the treap data structure is always the root node of the data structure. Further, the second data structure in another embodiment is a standard binary tree having an additional key which identifies the sequence with which each node was inserted into the binary tree. In this way, the binary tree when recursively traversed can be put in sequence order to provide the appropriate route path640to the display610of the device600, if desired. Of course, not all nodes in the binary tree need to be included in the route path640and selection of nodes to include within the route path640can be customized as needed.

As previously discussed a variety of configurations to device600can be made without departing from the scope of the present invention. For example, the device600can be permanently affixed to a transportation vehicle, detachably affixed to a transportation vehicle, a portable handheld device, an intelligent appliance, a computing device, an intelligent apparel worn by a person or animal and the like. Moreover, the memory620can be remote from the processor630. And, the device600can be equipped to transmit to a separate device the generated route path640. All of these configurations now known, or hereafter developed are intended to fall within the tenets of the present invention.

FIG. 7is one diagram of one example embodiment of a first data structure700according to the teachings of the present invention. One data structure which can be used by the present invention in one embodiment is a treap data structure, such as the example treap data structure700depicted in FIG.7.

In this embodiment, which is provided by way of illustration only, the treap700is represented by T1760and includes a root node or first location710having an order pair4(712) and0(714). The root note710has two children, a left child720having an ordered pair2(722) and10(724), and a right child750having an ordered pair5(752) and25(754). The right child750has no children of its own, it is therefore said to be a leaf node. However, the left child720includes both a left child740having an ordered pair1(742) and15(744), and a right child730having an ordered pair3(732) and30(734).

The distinguishing feature of the treap700is that the structure always maintains a typical binary tree order using the first order pair value as a first key, such that a child node to the left of a parent node has a first ordered pair value which is less than that of its parent. And, a child node to the right of a parent node has a first ordered pair value which is greater than that of its parent. Moreover, the treap700maintains the root node710of the binary tree as a least cost node of the entire treap700structure similar to a heap, such that the second ordered pair value of root node710is0(714) and the lowest cost value of the entire treap700structure. A heap order is such that the children of a parent node always have a higher cost than the parent node from which they derive. As one skilled in the art will readily recognizes this structure and order is readily maintained by using pointer data structures, and the binary tree structure is rotated as nodes are inserted or deleted from the treap700to maintain the appropriate order.

In this way, in one embodiment by using the treap700data structure the least cost node associated with generating a route path can always be accessed with using a single reference to the treap700to obtain the least cost node. This reduces processing complexity, reduces duplicative data structures thereby reducing memory capacity requirements and overall improves processing throughput when generating the route path since a single reference obtains the least cost node.

FIG. 8is one diagram for one embodiment of a first data structure800after performing delete860and insert870operations on the first data structure800in accordance with the teachings of the present invention.

Before performing delete860and insert870operations on treap800, the treap800appears as it did inFIG. 7, T1760, after the operations treap800appears as T2having a root node810with an ordered pair of2(812) and10(814). The root node includes a left child820having an ordered pair of1(822) and15(824), and a right child840having an ordered pair5(842) and25(844). The left child820has no children. The root's810right child844has a right child850having an ordered pair6(852) and80(854), and a left child860having ordered pair3(862) and30(864).

As is readily observable T1760had its root710removed in T2880with the delete operation860, and by rotating T1760, T2880now includes a root810having its second ordered pair value of10(814), which is the least cost node of treap800. Moreover, the insert operation870resulted in T2880having a rightmost leaf node850with its highest first ordered pair value of6(852) for the entire treap800, thus maintaining binary tree order as well.

FIG. 9shows one diagram of one embodiment for a navigational system900according to the teachings of the present invention. The system900includes storage910adapted to store navigation data934, a server920adapted to communicated with the storage910through a communications channel COM1912, and a navigation device930through communications channel COM2922.

The navigation device930further includes a processor936in communication with a memory938and is adapted to retrieve navigation data934from the server920though COM2922. The navigation device's930processor936and memory938cooperate using a set of executable instructions to generate a projected route932using the navigation data934which include a starting location940one or more available locations942and an ending location946. Further, each available location942has an associated cost944which is calculated in relation to selecting a particular available location942to generate a least cost projected route932.

The available locations942are evaluated in one embodiment after a last least cost location has been selected and inserted into a second data structure952. All available locations942connected or associated with the last least cost node selected are evaluated and inserted into a first data structure948such that a first location950of the first data structure948is always a least cost location associated with the entire then existing first data structure948. As previously presented the cartographic data acquisition and cost value assignment can be achieved in a variety of ways and inserted into a variety of first data structures948, such as that presented herein and above.

The communication channels COM1912and COM2922need not be hardwired as any single wireless channel or combination of hardwired and wireless channels can be implemented without departing from the present invention. Further, although system900depicts the project route932being generated entirely within navigation device930as one skilled in the art will readily appreciate, this generation can occur in concert with the server920. Moreover, server920can be a server in close proximity to navigation device930such that COM2922is achieved using infrared or radio frequency communications. Further, COM2could be an Internet or peer-to-peer connection between the server920and the navigation device930. It is readily apparent that a variety of configurations, now known or hereafter developed, are intended to fall within the scope of the present invention.

The first data structure948in one embodiment can be a treap data structure and the second data structure952can be a binary tree. Also, locations are inserted into the binary tree once selected as the first node950of the first data structure948(e.g., treap) such that a complete project route932can be generated by traversing the second data structure952(e.g., binary tree).

Moreover, the start location940can be dynamically changing as the navigation device930travels along a present projected route932or deviates from the projected route932. Initially, when starting to generate a projected route932the starting location940is inserted into the second data structure952along with the ending location946, comparisons to available adjacent locations942can be made by proceeding from the starting location940towards the ending location946, or by proceeding from the ending location946towards the starting location940. Alternatively, comparisons can be made in parallel until one or more convergences of locations produce one or more solutions for a projected route932, with the least cost solution being selected as the project route932.

Further, as will be readily apparent to those skilled in the art the starting location940may not be a location identified as an intersection or node identification as previously presented, however all available and connected node identifications can be readily obtained by the starting location's940address or location. In this way, the optimal projected route932may not always be immediately in a direction heading towards the ending location946, as some backward travel may produce the most optimal projected route932.

FIG. 10shows a block diagram of one embodiment of functional data1000according to the teachings of the present invention. The functional data1000includes a beginning node1012representative of an initial geographic location, a destination node1018representative of a desired geographic location, and optimal route1010which includes the beginning node1012, one or more selected intermediated nodes1014-1016from one or more available nodes1030, and the destination node1018.

Each of the available nodes1030become available for inspection and possible selection into the optimal route1010once a last selected node has been placed into the dynamically generated optimal route1010. Initially, the optimal route1010comprises a second data structure1020having the beginning node1012and the destination node1018. Furthermore, initially a first data structure1050is empty or null. Next, either the beginning node1012or the destination node1018are available for inspection, or both if analysis is proceeding in parallel from the beginning node1012and the destination node1018as presented above. As a node is inspected, all connected or adjacent nodes become available from the available nodes1030and a cost1040is associated with each available node. These inspected available nodes1030are then inserted into a first data structure1050, such that the first node of the first data structure1050is always the least cost node of the first data structure1050.

As inspection proceeds, the second data structure1020will include the beginning node1012, one or more selected intermediate nodes1014-1016and the destination node1018. Further, when traversed the second data structure1020can produce an ordered path resulting in an optimal route1010, although in some embodiments the ordered path need not be an optimal route. In some embodiments, the first data structure1050is a treap and the second data structure1020is a binary tree. Additionally, the second data structure1020need not include only nodes associated with the optimal route1010generated, since multiple routes may be present within the second data structure1020, and further optimization techniques can be used to selective pick nodes within the second data structure1020for generating the optimal route1010. Further, additional cartographic data1064can be obtained from a third data structure1060which is organized such that direct access is achieved with any node by using a unique node identification1062, as discussed above.

As will be readily apparent to those skilled in the art, the functional data1000embodied inFIG. 10will substantially decrease memory requirements associated with a navigational device and correspondingly increase processing throughput when generating optimal routes, such as optimal route1010. Memory is reduced by maintaining a single data structure of adjacent nodes in binary tree order for node identifications and heap order for node costs, in this way multiple parallel data structures are unnecessary to maintain two keys on the nodes being evaluated during route generation. As is apparent, processing throughput is increased because the least cost node is quickly found.

FIG. 11shows one flow diagram for one embodiment of a method1100for generating a projected route according to the teachings of the present invention. Initially, a set of executable instructions receives a start location and an ending location in step1102. As will be appreciated, the set of executable instructions performing the method1100ofFIG. 11need not reside on a single processor and the memory required to execute the same can be distributed, local, volatile, non volatile, or combinations of all of the above.

In step1104, one or more available locations are identified as existing near or in close proximity to the starting location. Moreover, the costs associated with the locations are computed or otherwise determined. The identified locations are then inserted into the first data structure such that a first location of a first data structure is always associated with the least cost location of the first data structure.

Next, in step1106, a current least cost node is pulled from the root node of the first data structure for processing. In some embodiments, the first data structure is a treap data structure, such that the root node of the first data structure is always the least code node of the first data structure. In this way, ready access to the current least cost node is quickly and efficiently obtained

In step1108all nodes adjacent to the current least cost node are identified and further examined in step1110. Each examined adjacent node that is not already present in the first data structure or a second data structure are inserted into the first data structure, while maintaining the structure of the first data structure, such that the root node remains the least cost node of the first data structure. The second data structure, which is associated with previously removed nodes from the first data structure.

The current least cost node is then moved from the first location of the first data structure to the second data structure in step1112. This removal operation results in the a new lease cost node being assembled into the root node location of the first data structure. Next, the second data structure is inspected to determine if any of the nodes in the second data structure is the destination node in step1114. If a node within the second data structure is the destination node then a route has been resolved, and the resolved route, which represents a path between the start and ending locations, is built in step1116. In some embodiments, the resolved route is built by traversing in reverse from the destination node located in the second data structure back through segments which were followed to reach it. However, if the destination node was not located in the second data structure in step1114then node expansion continues back at step1106.

As previously discussed, a least cost location can be determined by determining the time or distance of travel from a last selected adjacent location to a last least cost location of the first data structure, this cost can also include an estimated travel time or distance of travel associated with least cost location to the ending location, this cost calculation can occur in step1112for the first evaluation and step1114for the second concurrent evaluation.

In still more embodiments, the second data structure can comprise an additional data structure such as, and by way of example only, a binary tree or a list of binary trees. Furthermore, as one skilled in the art will readily appreciate, the unidirectional approach to calculating a navigation route using the first data structure (e.g., treap and the like) described in method1100, is provided for purposes of illustration only, since it is readily appreciated that any bi-directional algorithm will benefit from the teachings of the present invention. Similarly, route calculation algorithms that find many potential routes before selecting the best-fit route, can also benefit.

Correspondingly, all navigation related algorithms using a first data structure (e.g., treap and the like) to improve operational performance and reducing memory requirements are intended to fall within the scope of the present invention. Additionally, method1100can be used in connection with any navigation device or devices to assist with navigation, and any such device including method1100are intended to fall within the scope of the present invention.

Furthermore, in one embodiment the projected route can comprise an additional data structure such as a binary tree and the selected locations can comprise treap data structures. Also, method1100can be used in connection with any navigation device or devices assisting with navigation.

Another embodiment of the present invention, provides for efficient purging of nodes being evaluated for purposes of generating a projected route. As was previously discussed, cartographic data is voluminous including a large number of nodes and potential pathways from a starting location to an ending location. Moreover, many navigational devices implementing route generating algorithms include very limited processor and memory resources. Further, the more processor and memory resources provided within a navigational device, the physical size of the device and the expense of the device increases.

One common approach for these existing algorithms, is to layer the cartographic data as a node network. The lowest layer of the network includes least significant roadways relative to the examined network, while the highest layer includes most significant roadways relative to the examined network. For example a first layer L0, in some embodiments includes residential roadways, while a highest layer LN−1, where n is >0, includes major interstate thoroughfares. As is apparent, the amount of navigable features at the lowest layer is often more voluminous then at the highest layer, since clearly more navigable choices occur within lower layers of the network.

Accordingly, one embodiment of the present invention, optimally reduces the memory requirements of any navigational device using the tenets of the present invention by using the first data structure of the present invention to house the navigational network, wherein lower layers of the network are dynamically purged from the first data structure, when the route generation algorithm transitions to a higher layer within the navigation network for purposes of generating the projected route. Once the route generation algorithm transitions to a higher layer within the network, expansion of any node occurring at the layer which the algorithm transitions from will not result in any matches for purposes of generating the projected route. Accordingly, considerable memory and processing time required by the route generation algorithm are reduced by pruning (e.g., purging, removing, deleting, and the like) the network layer which the algorithm transitions from.

If the first data structure is not pruned then space within the first data structure is wasted. Furthermore, operations inserting and removing nodes from the first data structure become more processor intensive since a larger number of nodes will need to be rearranged so that the lease cost node is the root node of the first data structure. With the present embodiment, by programming the first data structure in the manner described above, remaining nodes in the first data structure will all reside on at least one thoroughfare that has a routing layer one layer higher than the current routing layer, for purposes of route generation.

Further and in still more embodiments, precious memory space, required by a navigational device having a route generation algorithm of the present invention, is further conserved by allowing a pointer associated with managing and accessing the second data structure to be configured as a variable length pointer, based on the initialized size of the second data structure. In this way, precious additional bytes of space are not wasted on a pointer when upon initialization of the second data structure, the exact byte size of the pointer, used to manage the second data structure, can be readily determined.

As one skilled in the art will readily appreciate, the byte size of the pointer determines the addressable address space which the pointer can access within the second data structure. Therefore, once given the size of the second data structure, or after determining the size of the second data structure, the required byte size of the pointer can be readily calculated. Furthermore, by saving even only a few bytes of memory space within the navigational device processor performance of any route generation algorithm is improved.

As one of ordinary skill in the art will understand upon reading this disclosure, the electronic components of the device shown inFIGS. 4A and 4Band components of the system shown inFIG. 5can be embodied as computer hardware circuitry or as a computer-readable program, or a combination of both. In another embodiment, the system inFIG. 5is implemented in an application service provider (ASP) system.

More specifically, in the computer-readable program embodiment, the programs can be structured in an object-orientation using an object-oriented language such as Java, Smalltalk, C++, and others, and the programs can be structured in a procedural-orientation using a procedural language such as C, PASCAL, and others. The software components communicate in any of a number of means that are well-known to those skilled in the art, such as application program interfaces (A.P.I.) or interprocess communication techniques such as remote procedure call (R.P.C.), common object request broker architecture (CORBA), Component Object Model (COM), Distributed Component Object Model (DCOM), Distributed System Object Model (DSOM) and Remote Method Invocation (RMI).

Of course it is readily appreciated by one skilled in the art that any programming methodology, programming language, programming interface, operating system, or computing environment, now known or hereafter developed can be readily deployed, without departing from the tenets of the present invention and all such implementation specific embodiments are intended to fall within the broad scope of the present invention.

CONCLUSION

The above systems, devices and methods have been described, by way of example and not by way of limitation, with respect to reducing memory capacity requirements, increasing processor throughput, and improving overall ease of user interaction with a navigation device. That is, the systems, devices, functional data, and methods provide for generating a projected route in connection with a navigational device which is more efficient and accurate than current systems, devices, and methods, without requiring more expensive system resources. The systems, devices, functional data, and methods of the present invention offer an improved generated projected route which provide more understandable, accurate, memory efficient, and timely capabilities in a navigation device while utilizing less resources.