Method and system for prediction-based distributed navigation

• US 6,807,483 B1
• Filed: 04/08/2003
• Issued: 10/19/2004
• Est. Priority Date: 10/11/2002
• Status: Active Grant

• Current Assignee: TeleNav Incorporated
• Original Assignee: Televigation Inc.
• Inventors: Jin, HaiPing, Chao, Yi-Chung, Dai, DongHai
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US10/408,325
• Time in Patent Office: 560 Days
• Field of Search: 701/201, 701/202, 701/207, 701/208, 701/209, 701/210, 701/211, 701/214, 340/991, 340/993, 340/995.12, 340/995.16, 340/995.17, 340/995.19, 340/995.25, 340/995.23, 340/995.27
• US Class Current: 701/210
• CPC Class Codes: G01C 21/00 Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 measuring distance traversed on the ground by a vehicle G01C22/00; control of position, course, altitude or attitude of vehicles G05D1/00; traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

Method and system for prediction-based navigation in a real-time distributed navigation system. In one embodiment, a server receives a request from a client comprising one or more position coordinates. The server estimates the user'"'"'s speed, estimates total elapsed time, calculates an optimal route to the destination and sends a set of routing directions to the client. Moreover, the server estimates a route origin within an estimated comfort zone in order to calculate the optimal route from the estimated origin to the destination.

Claims

1. A prediction-based navigation method in a distributed system comprising a client and a remote server, wherein the steps of providing prediction-based distributed navigation by the client comprises:

sending a request for a set of routing information to the server by the client, wherein the request comprises sending a set of position coordinates;

estimating an initial user position in response to receiving the client request and the set of position coordinates;

calculating a comfort zone range wherein the comfort zone range comprises a minimum and a maximum displacement value, wherein the minimum displacement is defined by a minimum weighted function, an initial user speed, and an estimated elapsed time, and the maximum displacement of the comfort zone range is defined by a maximum weighted function, the initial user speed, and the estimated elapsed time; and

generating a new set of routing information to a destination requested by the user using the calculated comfort zone range to estimate a route origin and accessing one or more databases to determine a set of routing directions from the estimated route origin to the destination.

2. The prediction-based distributed navigation method of claim 1 wherein each position coordinate comprises a corresponding time component.

3. The prediction-based distributed navigation method of claim 2, wherein the request for routing instructions further comprises an initial user velocity having a speed component and a heading component.

4. The prediction-based distributed navigation method of claim 3, wherein the initial user speed is derived from the initial user velocity.

5. The prediction-based distributed navigation method of claim 2, wherein an initial user velocity comprising a speed component and a heading component is derived from the set of position coordinates and corresponding time components.

6. The prediction-based distributed navigation method of claim 2, wherein an initial user speed is derived from the set of position coordinates and associated time components.

7. The prediction-based distributed navigation method of claim 1 wherein the maximum and minimum weighted functions comprise one or more weighted factors from a set of one or more weighted factors comprising a speed limit factor, a road condition factor, a traffic condition factor, a traffic signal factor, a weather factor, and a visibility factor.

8. The prediction-based distributed navigation method of claim 7 wherein each weighted factor comprises a variable multiplier.

9. The prediction-based distributed navigation method of claim 1 wherein the step of estimating the initial user position comprises providing the client a list of candidate locations to receive user selection input.

10. The prediction-based distribution navigation method of claim 1 wherein the step of estimating the initial user position comprises using a global positioning system in conjunction with the set of position coordinates.

11. The prediction-based distribution navigation method of claim 1 wherein the client communicates with the server via a wireless network.

12. The prediction-based distribution navigation method of claim 1 wherein the step of the server generating the new set of routing information comprises the server accessing one or more databases via a network.

13. The prediction-based distribution navigation method of claim 1 wherein the one or more databases accessed comprises a map database, a weather database, or a traffic database.

14. A prediction-based navigation method in a distributed system comprising a client and a remote server, wherein the steps of providing prediction-based distributed navigation by the client comprises:

a) sending a request for a set of routing information to the server by the client, wherein the request comprises sending a set of position coordinates;

b) estimating an initial user position in response to receiving the client request and the set of position coordinates;

c) determining if the initial user position is ambiguous;

d) if the initial user position is not ambiguous, calculating a comfort zone range wherein the comfort zone range comprises a minimum and a maximum displacement value, wherein the minimum displacement is defined by a minimum weighted function, an initial user speed, and an estimated elapsed time, and the maximum displacement of the comfort zone range is defined by a maximum weighted function, the initial user speed, and the estimated elapsed time; and

e) generating a new set of routing information to a destination requested by the user using the calculated comfort zone range to estimate a route origin and accessing one or more databases to determine a set of routing directions from the estimated route origin to the destination.

15. The prediction-based distributed navigation method of claim 14 wherein each position coordinate comprises a corresponding time component.

16. The prediction-based distributed navigation method of claim 15, wherein the request for routing instructions further comprises an initial user velocity having a speed component and a heading component.

17. The prediction-based distributed navigation method of claim 16, wherein the initial user speed is derived from the initial user velocity.

18. The prediction-based distributed navigation method of claim 15, wherein an initial user velocity is derived from the set of position coordinates and corresponding time components.

19. The prediction-based distributed navigation method of claim 15, wherein an initial user speed is derived from the set of position coordinates and associated time components.

20. The prediction-based distribution navigation method of claim 15, wherein the initial user position is ambiguous, further comprising the step of sending a list of candidate locations to the user for selection.

21. The prediction-based distribution navigation method of claim 20, wherein the user selects a location from the list of candidate locations.

22. The prediction-based distribution navigation method of claim 21, wherein the client periodically acquires a set of most recent user position coordinates and sends the position coordinates to the server.

23. The prediction-based distribution navigation method of claim 22, wherein the server updates the user initial position to a new value according to the user-selected location from the list of candidate locations and the most recently acquired position coordinates from the client.

24. The prediction-based distribution navigation method of claim 20, wherein the user does not select a location from the list of candidate locations within an allotted timeout period.

25. The prediction-based distribution navigation method of claim 24, further comprising the step of selecting a location from the candidate list as a default selection.

26. The prediction-based distribution navigation method of claim 25, wherein the client periodically acquires a set of most recent user position coordinates and sends the position coordinates to the server.

27. The prediction-based distribution navigation method of claim 26, wherein the server updates the user initial position to a new value according to the default location selection from the list of candidate locations and the most recently acquired position coordinates from the client.

28. A prediction-based distributed navigation system comprising:

a client for sending a request for a set of routing information, wherein the request comprises sending a set of position coordinates; and

a server for receiving the request from the client, calculating a comfort zone range wherein the comfort zone range comprises a minimum and a maximum displacement value, and generating a new set of routing information to a destination requested by the client using the calculated comfort zone range to estimate a route origin and accessing one or more databases to determine a set of routing directions from the estimated route origin to the destination.

29. The prediction-based distributed navigation system of claim 28, further comprising a wireless carrier coupled to the client on a first end for receiving the request from the client and coupled to the server on a second end for relaying the request from the client to the server.

30. The prediction-based distributed navigation system of claim 29, further comprising one or more direct links coupled to the wireless carrier on a first end for receiving the request from the wireless carrier and coupled to the server on a second end for relaying the request from the wireless carrier to the server.

31. The prediction-based distributed navigation system of claim 29, further comprising a gateway coupled to the wireless carrier on a first end for receiving the request from the wireless carrier and coupled to the server on a second end for relaying the request from the wireless carrier to the server.

32. The prediction-based distributed navigation system of claim 31, further comprising a network coupled to the gateway on a first end for receiving the request from the gateway and coupled to the server on a second end for relaying the request from the gateway to the server.

33. A prediction-based distributed navigation system comprising:

a server for receiving a navigation request, calculating a comfort zone range wherein the comfort zone range comprises a minimum and a maximum displacement value, generating a new set of routing information to a requested destination using the calculated comfort zone range to estimate a route origin and accessing one or more databases to determine a set of routing directions from the estimated route origin to the destination; and

a client for receiving the set of routing directions from the server.

34. The prediction-based distributed navigation system of claim 33, further comprising one or more direct links coupled on a first end to the server for receiving the routing directions and coupled on a second end to the client for relaying the routing directions.

35. The prediction-based distributed navigation system of claim 34, further comprising a wireless carrier coupled on a first end to the direct links for receiving the routing directions and coupled on a second end to the client for relaying the routing directions.

36. The prediction-based distributed navigation system of claim 33, further comprising a network coupled on a first end to the server for receiving the routing directions and coupled on a second end to the client for relaying the routing directions.

37. The prediction-based distributed navigation system of claim 36, further comprising a gateway coupled on a first end to the network for receiving the routing directions and coupled on a second end to the client for relaying the routing directions.

38. The prediction-based distributed navigation system of claim 37, further comprising a wireless carrier coupled on a first end to the gateway for receiving the routing directions and coupled on a second end to the client for relaying the routing directions.