Systems and methods for a navigational device with improved route calculation capabilities

• US 20030158660A1
• Filed: 02/11/2003
• Published: 08/21/2003
• Est. Priority Date: 12/20/2001
• Status: Active Grant

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Childs, Michael, Krull, Jay Dee, Walters, Thomas H., Burgett, Scott M.
• Granted Patent: US 6,856,899 B2
• Time in Patent Office: Days
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents

Abstract

Systems, devices and methods are provided for an improved navigational route planning device which provides more understandable, accurate and timely route calculation capabilities. The navigational aid device with route calculation capabilities includes a processor connected to a memory. The memory includes cartographic data and a desired destination, the cartographic data including data indicative of thoroughfares of a plurality of types. A display is connected to the processor and is capable of displaying the cartographic data. The device is adapted to calculate a route to navigate to the desired destination. And, the device is adapted to adjust a starting point for the route calculation to an appropriate location such that the device is on the route at a time when the route calculation is completed. The device processes travel along the route, recognizes when the device has deviated from the route, and calculates a new route to navigate to the desired destination.

Claims

1. An electronic navigational aid device with route calculation capabilities, comprising:

a processor;

a memory adapted to communicate with the processor, the memory having cartographic data and a desired destination, the cartographic data including data indicative of thoroughfares of a plurality of types;

a display connected to the processor and capable of displaying the cartographic data;

wherein the device is adapted to calculate a route to navigate to the desired destination; and

wherein the device is adapted to adjust a starting point for the route calculation to an appropriate location such that the device is on the route at a time when the route calculation is completed.

2. The device of claim 1, wherein the device determines data indicative of a set of travel habits for the device on each of the plurality of types of thoroughfares and stores the travel habit data in the memory.

3. The device of claim 1, wherein the device regularly calculates the device'"'"'s current position and processes the device'"'"'s travel along the route.

4. The device of claim 3, wherein the display continuously displays the device'"'"'s position and uses audio instructions to navigate to the starting point of the route calculation as well as to navigate along the route.

5. The device of claim 1, wherein the device determines a calculation time for processing the route and determines a travel speed for the device, and wherein the device uses this information to adjust the starting point for the route calculation.

6. The device of claim 5, wherein the travel speed for the device is determined based on the greater of a current travel speed of the device and either of a learned travel speed or an estimated travel speed of the device for a current thoroughfare on which the device is located or traveling.

7. The device of claim 1, wherein the device includes a portable electronic navigational aid device.

8. The device of claim 6, wherein the portable electronic navigational aid device includes a personal digital assistant (PDA).

9. The device of claim 6, wherein the portable electronic navigational aid device includes a wireless communications device.

10. An electronic navigational aid device with route calculation capabilities, comprising:

a processor;

a memory in communication with the processor, the memory having cartographic data and a route stored therein to navigate from a beginning position to a desired destination, the cartographic data including data indicative of thoroughfares of a plurality of types;

a display in communication with the processor and capable of displaying the cartographic data, the route to the desired destination, and the device'"'"'s position;

wherein the device processes the device'"'"'s location and provides location data to the display; and

wherein the device recognizes when the device has deviated from the route and calculates a new route to navigate to the desired destination, wherein the device adjusts a starting point for the new route calculation to an appropriate location such that the device is on the new route at a time when the route calculation is completed.

11. The device of claim 10, wherein in calculating the new route the device determines a travel speed of the device to determine how far the device will travel on the current thoroughfare before a the new route calculation can be completed.

12. The device of claim 11, wherein in calculating the new route the device estimates a first route calculation time for processing the new route based on a complexity of the thoroughfares from a current position of the device to the desired destination, and wherein the device uses the determined travel speed of the device and the first route calculation time to adjust the starting point for the new route calculation.

13. The device of claim 12, wherein if the device not on the new route after an actual first route calculation time then the device uses a second route calculation time and the device'"'"'s travel speed to set a new starting point for another new route calculation.

14. The device of claim 13, wherein the second route calculation time is equal to or greater than an actual first route calculation time.

15. The device of claim 10, wherein the device uses a set of criteria to analyze adjacency information and to determine a straightest path in order to adjust the starting point for the new route calculation.

16. The device of claim 10, wherein the starting point is at an end of a current thoroughfare on which the device is traveling.

22. The method of claim 16, wherein selecting a starting point includes using a set of criteria to analyze adjacency information and determine a straightest path in order to adjust the starting point.

17. A navigation aid method for performing a route calculation, comprising:

determining a travel speed of a navigation device,

estimating a calculation time for processing a first route of navigation from a first location of the device to a desired destination; and

selecting a starting point for the first route of navigation based on the determined travel speed of the device and the estimated calculation time for processing the first route of navigation.

18. The method of claim 17, wherein estimating a calculation time for processing the first route of navigation includes assessing a complexity of a route solution between the first location of the device and the desired destination.

19. The method of claim 17, wherein the method further includes detecting when the navigation device has deviated from the first route of navigation, determining a new second location of the device, and estimating a calculation time for processing a second route of navigation from the second location of the device to the desired destination.

20. The method of claim 19, wherein detecting when the device has deviated from the first route of navigation and determining the second location of the device includes using a global positioning system.

21. The method of claim 19, wherein estimating a calculation time for processing the second route of navigation includes using a calculation time which is equal to or greater than an actual previous route calculation time.

23. A navigation system, comprising:

a mass data storage adapted to store navigation data;

a server having a processor and memory, wherein the server is adapted to communicate with the mass data 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;

a display connected to the processor; and

a memory connected to the processor, the memory having cartographic data and a route to a desired destination stored therein, the cartographic data including data indicative of thoroughfares of a plurality of types;

wherein the system processes the navigation device'"'"'s travel along the route;

wherein the system recognizes when the device has deviated from the route and is adapted to calculate a new route to navigate the device to the desired destination using an exchange of data, via the communication channel, between the server, the mass storage device and the navigation device; and

wherein the system is adapted to adjust a starting point for the new route calculation to an appropriate location such that the device is on the new route at a time when the route calculation is completed.

24. The navigation system of claim 23, wherein the communication channel includes a wireless channel.

25. The navigation system of claim 23, wherein the server includes a remote server.

26. The navigation system of claim 23, wherein the server includes a processor adapted to respond to a request from the navigation device by performing calculations on the navigation data and transmitting results to the navigation device.

27. The navigation system of claim 23, wherein the navigation device adapted to communicate with and retrieve navigation data from the server using streaming data.

28. The navigation system of claim 23, wherein the navigation device adapted to communicate with and retrieve navigation data from the server using cellular communication technology.

29. A coded information signal embodied in a carrier wave, the coded information signal representing data, comprising:

coordinate data operable to determine a navigation device'"'"'s current location;

travel speed data operable to represent a navigation device'"'"'s travel speed;

processing time data operable to estimate a time for processing a route of navigation to a desired destination; and

starting point data operable to be selected for the route of navigation based on the travel speed data and the processing time data.

30. The coded information signal of claim 29, wherein the processing time data is determined by resolving a complexity for the route of navigation between the current location and the desired destination.

31. The coded information signal of claim 29 further comprising, detection data that is used to detect when the navigation device is off the route of navigation.

32. The coded information signal of claim 31, wherein the detection data is used with a new location of the navigation device to determine a new route of navigation based on the new location.

33. The coded information signal of claim 29, wherein the processing time data is determined by using a calculation time that is equal to or greater than a previous route calculation time.

34. The coded information signal of claim 29, wherein the starting point data is determined by using a set of criteria to analyze adjacency information and determine a straightest path.

35. The coded information signal of claim 29, wherein the processing time data is based on the complexity of thoroughfares from the current position to the desired position.

36. Functional data residing on a computer readable medium for performing route calculation, the data comprising:

coordinate data representing positions of a navigation device;

thoroughfare data representing thoroughfares associated with streets between a current position of the navigation device and a desired position of the navigation device;

speed data representing a velocity of the navigation device;

calculation data representing an estimated time for determining a route of the navigation device from its current position to the desired position; and

starting point data representing a starting point for the navigation device on the route.

37. The functional data of claim 36, wherein the positions are continually updated as the navigation device travels.

38. The functional data of claim 37, wherein the coordinate data is acquired from a Global Positioning Satellite (GPS) system.

39. The functional data of claim 37, wherein the positions of the navigation device are mapped to points on the route or points off the route as the navigation device travels, and wherein the points, the route, and a number of the thoroughfares are presented on a display in communication with the navigation device.

40. The functional data of claim 36, wherein the calculation data is determined by determining a complexity of a number of thoroughfares from the current position of the navigation device to the desired position of the navigation device.

41. The functional data of claim 36, wherein the calculation data is determined by selecting a time associated with a processing time needed to process a previous route, and wherein the time is at least as much as the processing time.

42. The functional data of claim 36, wherein the starting point data is determined by using the current position, the velocity, and the estimated time.

43. Functional data residing on a computer readable medium for performing route calculation, the data comprising:

calculation data representing an estimated processing time needed to determine a route of a navigation device from a current position to a desired position; and

starting point data representing a starting point on the route for the navigation device based on the estimated processing time, the current position, and a velocity of the navigation device.

44. The functional data of claim 43, wherein the functional data is processed on the navigation device.

45. The functional data of claim 43, wherein the functional data is remotely processed from the navigational device.

46. The functional data of claim 43, wherein the estimated processing time is determined based on a complexity of thoroughfares located between the current position and the desired position.

47. The functional data of claim 43, wherein the estimated processing time is at least as much as a previous processing time required to calculate a previous route.

48. The functional data of claim 43, wherein the starting point and the route are presented on a display interfaced with the navigation device.