Method and system for distributed navigation and automated guidance

• US 7,149,625 B2
• Filed: 05/29/2002
• Issued: 12/12/2006
• Est. Priority Date: 05/31/2001
• Status: Expired due to Fees

• Current Assignee: WRE-Hol LLC
• Original Assignee: WRE-Hol LLC
• Inventors: Mathews, Michael B., Littlewood, William A., Lomholt, Poul T.
• Primary Examiner(s): NGUYEN, CUONG H
• Application Number:
  US10/158,223
• Publication Number:
  US 20030060973A1
• Time in Patent Office: 1,658 Days
• Field of Search: 701/209, 701/200, 701/201, 701/205, 701/96, 731/781.2, 340/991, 340/993, 340/995.18, 340/995.2, 340/995.24
• US Class Current: 701/209
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network

Abstract

The present invention provides for distributed navigation and route guidance using networked computing devices. A computing device may host one or more navigation functional components. The location of a navigable object is sensed and communicated to associated navigation components in a communication network. The navigation components collectively provide guidance information to a navigable object controller. A navigable object controller directs the movement of an navigable object using guidance information to keep it on a specified route. The navigable object controller interacts with the distributed navigation system through an interface, which provides the appropriate presentation of guidance information and functions for the particular type of navigable object controller (e.g., human-machine interface, or system to system). The present invention provides the structures and methods for a flexible navigation and guidance system supporting a variety of network capabilities and computing devices using the same software implementation.

Claims

1. A distributed navigation system for providing navigation information to a navigable physical object, the system comprising:

(a) a navigation management component for managing the generation and transmission of navigation information to a navigable physical object;

(b) a navigation guidance interface component for;

(i) receiving a route definition pertaining to the navigable physical object; and

(ii) transmitting navigation information generated by the distributed navigation system to the navigable physical object controller;

(c) a guidance component for generating the navigation information for the navigable physical object;

(d) a navigation services component for providing routing information to the distributed navigation system; and

(e) a physical location sensor component for obtaining the physical location of the navigable physical object;

wherein the components of the distributed navigation system or software components distributed on a plurality of networked computers in a distributed network external to the navigable physical object; and

wherein the components of the distributed navigation system communicate among themselves through the distributed network using a computer network protocol.

2. The distributed navigation system of claim 1 further comprising a caching component for temporarily storing navigation information for the navigable physical object while communications between the distributed navigation system and the navigable physical object are interrupted.

3. The distributed navigation system of claim 1, wherein managing the generation and transmission of navigation information to a navigable physical object comprises:

(a) receiving the route definition pertaining to the navigable physical object;

(b) constructing a navigation route for the navigable physical object according to the route definition and the routing information;

(c) initiating the generation of navigation information for the navigable physical object; and

(d) initiating the transmission of the navigation information to the navigable physical object.

4. The distributed navigation system of claim 3, wherein generating the navigation information for the navigable physical object comprises generating the navigation information for the navigable physical object according to the physical location of the navigable physical object, the routing information, and the navigation route for the navigable physical object.

5. The distributed navigation system of claim 3, wherein the routing information provided by the navigation services component comprises:

(a) mapping and geocoding guidance information; and

(b) point-of-interest guidance information.

6. The distributed navigation system of claim 5 further comprising a mapping and geocoding services component for providing mapping and geocoding guidance information to the navigation services component.

7. The distributed navigation system of claim 5 further comprising a point-of-interest guidance component for providing point-of-interest guidance information to the navigation services component.

8. The distributed navigation system of claim 3, wherein the navigation information generated by the guidance component includes predictive navigation information comprising predictive guidance information for the navigable physical object, generated according to a prediction criterion, for guiding the navigable physical object according to the navigation route, and wherein the predictive navigation information is stored by the caching component for subsequent retrieval.

9. The distributed navigation system of claim 8, wherein the prediction criterion comprises a predicted physical location for the navigable physical object according to a speed and a heading of the navigable physical object.

10. The distributed navigation system of claim 8, wherein the prediction criterion comprises a predicted physical location for the navigable physical object according to a navigation route for the navigable physical object.

12. The distributed navigation system of claim 8, wherein the predictive navigation information is further generated according to previously generated navigation information.

13. The distributed navigation system of claim 8, wherein the navigation guidance interface component obtains the predictive navigation guidance information from the caching component when the predictive navigation information corresponds to the physical location of the navigable physical object.

14. The distributed navigation system of claim 1, wherein the components of the distributed navigation system are distributed on the plurality of networked computers in the distributed computer network according to the communication abilities of the plurality of networked computers.

15. The distributed navigation system of claim 14, wherein distributing the components of the distributed navigation system on the plurality of networked computers in the distributed computer network according to the communication abilities of the plurality of networked computers comprises distributing the components on a plurality of networked computers having low latency, high bandwidth connections to the network.

16. The distributed navigation system of claim 1, wherein the components of the distributed navigation system are distributed on the plurality of networked computers in the distributed computer network in order to optimize communication throughput among components of the distributed navigation system.

17. The distributed navigation system of claim 1, wherein the components of the distributed navigation system are distributed on the plurality of networked computers in the distributed computer network in order to optimize communication reliability to the navigation guidance interface.

18. The distributed navigation system of claim 1, wherein the distributed navigation system generates navigation information for a plurality of navigable physical objects.

19. The distributed navigation system of claim 18, wherein the navigation management component coordinates navigation information between a plurality of navigable physical objects, such that the physical location of and navigation information generated for a first navigable physical object is used in generating navigation information for a second navigable physical object.

20. The distributed navigation system of claim 18, wherein the components of the distributed navigation system are distributed on the plurality of networked computers in the distributed computer network in order to optimize communication throughput of navigation information for the plurality of navigable physical objects.

21. The distributed navigation system of claim 20, wherein distributing the components of the distributed navigation system on the plurality of networked computers in the distributed computer network in order to optimize communication throughput of navigation information for the plurality of navigable physical objects comprises distributing the components on a plurality of networked computers in the distributed computer network having low latency, high bandwidth network connections.

22. The distributed navigation system of claim 20, wherein distributing the components of the distributed navigation system on the plurality of networked computers in the distributed computer network in order to optimize communication throughput of navigation information for the plurality of navigable physical objects comprises distributing the components on a plurality of networked computers in the distributed computer network having highly reliable network connections.

11. A method for providing navigation information for a navigable physical object by a distributed navigation system, the distributed navigation system comprising a plurality of software components distributed on a plurality of computers external to the navigable physical object and communicating via a computer network protocol, the method comprising:

receiving a route definition pertaining to the navigable physical object;

constructing a navigation route for the navigable physical object according to the route definition;

generating navigation information for the navigable physical object according to the navigation route;

providing the navigation information to the navigable physical object;

generating predictive navigation information for the navigable physical object according to a prediction criteria;

storing the predictive navigation information in a cache component; and

providing the predictive navigation information from the cache component to the navigable physical object when the predictive navigation information corresponds to the physical location of the navigable physical object.

33. The method of claim 11, wherein the prediction criterion comprises a predicted physical location according to a speed and a heading for the navigable physical object.

45. The method of claim 11, wherein the prediction criterion comprises a predicted physical location according to a navigation route for the navigable physical object.

51. The method of claim 11 further comprising generating the predictive navigation information for the navigable physical object according to previously generated navigation information.

23. A method for providing navigation information for a navigable physical object by a distributed navigation system, wherein the components of the distributed navigation system are software components distributed on a plurality of networked computers in a computer network external to the navigable physical object, and wherein the components of the distributed navigation system communicate among each other using a computer network protocol, the method comprising:

(a) receiving, at a first component of the distributed navigation system, a route definition pertaining to a navigable physical object;

(b) constructing, at a second component of the distributed navigation system, a navigation route for the navigable physical object according to the route definition and routing information obtained from a third component of the distributed navigation system using a network protocol;

(c) sensing, at a third component of the distributed navigation system, the physical location of the navigable physical object;

(d) generating, at a fourth component of the distributed navigation system, navigation information for the navigable physical object according to the physical location of the navigable physical object, the routing information, and the navigation route; and

(e) transmitting the navigation information to the navigable physical object via the first component;

wherein the components of the distributed navigation system are distributed on at least two networked computers in the computer network external to the navigable physical object.

24. The method of claim 23 further comprising repeatedly generating and transmitting navigation information to the navigable physical object until a condition occurs.

25. The method of claim 24, wherein the condition occurs when the navigable physical object arrives at a destination identified in the route definition.

26. The method of claim 24, wherein the condition occurs when the distributed navigation system is directed to stop providing navigation information for the navigable physical object.

27. The method of claim 23, wherein the routing information comprises mapping and geocoding guidance information.

28. The method of claim 23, wherein the routing information comprises point-of-interest guidance information.

29. The method of claim 23, wherein providing navigation information for a navigable physical object to the navigable physical object further comprises:

storing the generated navigation information in a cache component when the distributed navigation system is unable to transmit the navigation information to the navigable physical object;

retrieving the stored navigation information from the cache component when the distributed navigation system is able to transmit the navigation information to the navigable physical object; and

transmitting the navigation information to the navigable physical object via the first component.

30. The method of claim 23, further comprising:

generating predictive navigation information for the navigable physical object according to a prediction criterion;

storing the predictive navigation information in a cache component;

retrieving the predictive navigation information from the cache component when the predictive navigation information corresponds to the physical location of the navigable physical object; and

transmitting the predictive navigation information to the navigable physical object.

31. The method of claim 30, wherein the prediction criterion comprises a predicted physical location according to a speed and a heading for the navigable physical object.

32. The method of claim 30, wherein the prediction criterion comprises a predicted physical location according to the navigation route for the navigable physical object.

34. The method of claim 30 further comprising generating the predictive navigation information for the navigable physical object according to previously generated navigation information.

35. The method of claim 23 further comprising generating navigation information for a plurality of navigable physical objects.

36. The method of claim 35, wherein generating navigation information for a plurality of navigable physical objects comprises generating navigation information for a plurality of navigable physical objects such that the navigation information generated for a first navigable physical object is used to generate navigation information for a second navigable physical object.

37. A method for providing navigation information for a navigable physical object by a distributed navigation system, comprising:

(a) receiving a route definition pertaining to the navigable physical object by a navigation guidance interface component of the distributed navigation system and transmitting the route definition to a navigation management component of the distributed navigation system;

(b) constructing, using the navigation management component, a navigation route for the navigable physical object according to the route definition and routing information, wherein the routing information is obtained from a navigation services component of the distributed navigation system, the routing information comprising;

(i) mapping and geocoding guidance information obtained from a mapping and geocoding services component of the distributed navigation system; and

(ii) point-of-interest guidance information obtained from a point-of-interest component of the distributed navigation system; and

(c) sensing the physical location of the navigable physical object with a physical location sensor of the distributed navigation system and transmitting the physical location to a guidance component of the distributed navigation system;

(d) generating navigation information for the navigable physical object, using a guidance component, according to the physical location of the navigable physical object, the routing information, and the navigation route; and

(e) transmitting the navigation information to the navigable physical object through the navigation guidance interface;

wherein the components of the distributed navigation system are distributed on a plurality of networked computers in a computer network external to the navigable physical object, and wherein the components of the distributed navigation system communicate via a computer network protocol.

38. The method of claim 37 further comprising repeatedly generating and transmitting navigation information for the navigable physical object until a condition occurs.

39. The method of claim 38, where the condition occurs when the navigable physical object arrives at a destination identified in the route definition.

40. The method of claim 38, where the condition occurs when the distributed navigation system is directed to stop providing navigation information for the navigable physical object.

41. The method of claim 37, wherein providing navigation information to a navigable physical object further comprises:

storing navigation information with a caching component of the distributed navigation system when the distributed navigation system is unable to transmit the navigation information to the navigable physical object through the navigation guidance interface;

obtaining the navigation information from the caching component when the distributed navigation system is able to transmit the navigation information to the navigable physical object through the navigation guidance interface; and

transmitting the navigation information to the navigable physical object through the navigation guidance interface.

42. The method of claim 37, wherein providing navigation information to a navigable physical object further comprises:

generating predictive navigation information for the navigable physical object according to a prediction criterion;

storing the predictive navigation information with a caching component of the distributed navigation system;

retrieving the predictive navigation information from the caching component when the predictive navigation information corresponds to the physical location of the navigable physical object; and

transmitting the predictive navigation information to the navigable physical object through the navigation guidance interface.

43. The method of claim 42, wherein the prediction criterion comprises a predicted physical location according to a speed and a heading for the navigable physical object.

44. The method of claim 42, wherein the prediction criterion comprises a predicted physical location according to a navigation route for the navigable physical object.

46. The method of claim 42 further comprising generating the predictive navigation information for the navigable physical object according to previously generated navigation information.

47. The method of claim 37 further comprises providing navigation information for a plurality of navigable physical objects.

48. The method of claim 47, wherein providing navigation information for a plurality of navigable physical objects comprises generating navigation information for a plurality of navigable physical objects such that navigation information generated for a first navigable physical object is used to generate navigation information for a second navigable physical object.

49. A computer-readable medium having computer-readable instructions which, when executed on a plurality of computers in a computer network, carry out the method comprising:

(a) receiving, at a first component of the distributed navigation system, a route definition pertaining to a navigable physical object;

(b) constructing, at a second component of the distributed navigation system, a navigation route for the navigable physical object according to the route definition and routing information from a third component of the distributed navigation system; and

(c) sensing, at a third component of the distributed navigation system, the physical location of the navigable physical object;

(d) generating, at a fourth component of the distributed navigation system, navigation information for the navigable physical object according to the physical location of the navigable physical object, the routing information, and the navigation route; and

(e) transmitting the navigation information to the navigable physical object via the first component;

wherein the components of the distributed navigation system are distributed on a plurality of computers in the computer network external to the navigable physical object, and communicate among each other using a computer network protocol.

50. A computer-readable medium having computer-readable instructions which, when executed on a plurality of computers in a computer network, carry out the method comprising:

(a) receiving a route definition pertaining to the navigable physical object by a navigation guidance interface component of the distributed navigation system and transmitting the route definition to a navigation management component of the distributed navigation system;

(b) constructing, using the navigation management component, a navigation route for the navigable physical object according to the route definition and routing information, wherein the routing information is obtained from a navigation services component of the distributed navigation system, the routing information comprising;

(i) mapping and geocoding guidance information obtained from a mapping and geocoding services component of the distributed navigation system; and

(ii) point-of-interest guidance information obtained from a point-of-interest component of the distributed navigation system;

(c) sensing the physical location of the navigable physical object with a physical location sensor component of the distributed navigation system;

(d) generating navigation information for the navigable physical object, using a guidance component, according to the physical location of the navigable physical object, the routing information, and the navigation route; and

(e) transmitting the navigation information to the navigable physical object through the navigation guidance interface;

wherein the components are distributed on the plurality of computers in the computer network, external to the navigable physical object, and communicate among each other using a computer network protocol.