PDA systems, functional data, and methods for generating a route

• US 6,789,012 B1
• Filed: 10/11/2002
• Issued: 09/07/2004
• Est. Priority Date: 12/21/2001
• Status: Active Grant

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Childs, Michael E., Beesley, Darin J.
• Primary Examiner(s): ZANELLI, MICHAEL J
• Application Number:
  US10/269,530
• Time in Patent Office: 697 Days
• Field of Search: 701/208, 701/209, 701/211, 340/995.19, 707/104.1
• US Class Current: 701/209
• CPC Class Codes: G01C 21/34 Route searching; Route guidance

Abstract

PDA devices, systems, functional data and methods are provided for an improved route generation. A PDA with route generation capabilities includes a processor communicating with a memory. The memory includes a current location of the PDA, one or more available locations, and a destination of the PDA. A display communicates with the processor and is capable of communicating at least a portion of a generated route for the PDA. Available locations are repetitively inspected 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.

Claims

1. A personal digital assistant (PDA), comprising:

a calendar function;

an address book function;

a processor operably coupled to a memory and a display;

wherein the PDA dynamically generates a route path using the processor and the memory from a moveable location associated with the PDA to a destination of the PDA by repetitively dynamically expanding one or more adjacent locations and inserting the adjacent locations into a first data structure wherein one or more first locations of the first data structure are associated with 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; and

wherein at least a portion of the route path is dynamically communicated to the display.

2. The PDA of claim 1, further comprising an interface device operable to audibly communicate the route path.

3. The PDA of claim 1, wherein the first locations are removed from the first data structure as the first locations become part of the route path and the removed first locations combine to form a second data structure.

4. The PDA of claim 1, wherein the first data structure is a treap and the second data structure is a binary tree.

5. The PDA of claim 1, wherein the display regularly displays the moveable location relative to the destination.

6. The PDA of claim 1, wherein the PDA dynamically resolves the moveable location using a triangulation algorithm.

7. The PDA of claim 1, wherein the PDA includes a telecommunication functionality operable for transmitting and receiving voice data.

8. The PDA of claim 1, wherein the PDA includes a wireless communication device operable using Bluetooth technology.

9. A PDA system, comprising:

a storage device to store navigation data;

a server operable to communicate with the storage device; and

a PDA device operable to communicate with and retrieve navigation data from the server via a communication channel, wherein the PDA device includes a processor in communication with a memory, wherein the processor and memory cooperate to;

generate a projected route from a starting location, one or more available locations, and an ending location, wherein each available location has an associated cost;

evaluate each available location as the projected route 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; and

insert a adjacent locations into a first data structure such that a first location of the first data structure is a least cost location of the data structure, and wherein the first data structure is a treap data structure.

10. The system of claim 9, wherein the communication channel includes a wireless channel.

11. The system of claim 9, wherein the projected route is stored as a second data structure.

12. The system of claim 11, wherein the second data structure is a binary tree.

13. A PDA having functional data for selecting an optimal route, the functional data comprising:

a beginning node representative of an initial geographic location;

a destination node representative of a desired geographic location;

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; and

one or more available nodes wherein each available node includes a cost associated therewith including each available node in the path as one of the selected intermediate nodes, wherein 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, and wherein the first data structure is a treat) data structure.

14. The PDA having the functional data of claim 13, further comprising a second data structure operable to house the beginning node, the selected intermediate nodes, and the destination node.

15. The PDA having the functional data of claim 14, wherein the second data structure is a binary tree.

16. The PDA having the functional data of claim 15, wherein the binary tree is traversed to generate the optimal route.

17. The PDA having the functional data of claim 13, wherein one or more of the available nodes become available for inspection only when adjacent to a last selected node.

18. The PDA having the functional data of claim 13, further comprising:

a third data structure operable to include a unique identification for the beginning node, the available nodes, and the ending node and operable to include cartographic data associated with each unique identification.

19. The PDA having the functional data of claim 13, wherein the organization of the first data structure decreases a memory requirement associated with generating the optimal route in a navigation device.

20. A method in a PDA of generating a projected route, comprising:

in a PDA, receiving an initial starting location and an ending location;

identifying one or more available locations existing between the starting location and the ending location;

beginning with the stating location and proceeding to the ending location initiating a first evaluation by selecting one or more adjacent locations from the available locations and as one or more of the adjacent locations are selected inserting each of the selected adjacent locations into a first data structure, wherein a first location of the first data structure is always associated with a least cost location of the first data structure, and wherein the first data structure is a treap data structure; and

generating the projected route 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.

21. The method of claim 20, wherein the method further includes providing the projected route to a display of the PDA.

22. The method of claim 20, further comprising:

concurrent with the first evaluation, initiating a second evaluation beginning with the ending location;

proceeding to the starting location and selecting one or more second adjacent locations from the available locations and as one or more of the second adjacent locations are selected;

inserting each of the second selected adjacent locations into a second data structure, wherein a first location of the second data structure is always a least cost location of the second data structure; and

detecting when a convergence exists in the first evaluation and the second evaluation and using the first evaluation and the second evaluation in forming the projected route.

23. The method of claim 22, wherein the proceeding with the evaluations occur dynamically as the starting location changes.

24. The method of claim 20, further comprising:

determining the least cost location of the first data structure by determining a time or a distance of travel from a last selected adjacent location to a last least cost location of the first data structure.

25. The method of claim 24, wherein the determining the least cost location includes adding an estimated travel time or distance associated with traveling from the least cost location to the ending location with the time or distance of travel from the last selected adjacent location to the last least cost location of the first data structure.

26. The method of claim 20, wherein in generating the projected route the starting location, one or more of the selected adjacent locations, and the ending location comprise a second data structure.

27. The method of claim 26, wherein generating the projected route includes a binary tree which is the second data structure.

28. The method of claim 20, wherein the method is used in a PDA having Bluetooth capabilities.

29. A personal digital assistant (PDA), comprising:

a calendar function;

an address book function;

a processor operably coupled to a memory and a display;

means for dynamically generating a route path using the processor and the memory from a moveable location associated with the PDA to a destination of the PDA by repetitively dynamically expanding one or more adjacent locations and inserting the adjacent locations into a first data structure wherein one or more first locations of the first data structure are associated with 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; and

means for dynamically communicating at least a portion of the route path to the display.