Thin-client navigation and route guidance system

• US 6,892,133 B2
• Filed: 02/25/2002
• Issued: 05/10/2005
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: Alk Industries, Inc., ALK Technologies Incorporated (Trimble Inc.)
• Original Assignee: ALK Technologies Incorporated (Trimble Inc.)
• Inventors: Bernstein, David, Kornhauser, Alain L., Hornung, Mark A.
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US10/467,724
• Publication Number:
  US 20040078139A1
• Time in Patent Office: 1,170 Days
• Field of Search: 701/209, 701/201, 701/208, 701/210, 701/205, 701/211, 340/988, 340/990, 340/995.17, 340/995.23, 340/995.25
• 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
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A client/server navigation system utilizes partial route guidance trees, enabling a thin, mobile client to detect route deviation and provide alternate instructions while awaiting response from a server. The system (10) consists of a server (28) containing a network database and route-calculation program; a client (26) capable of obtaining (12) its current location and destination, displaying route instructions (22), and determining when it needs additional instructions from the server (20,24); and communication (30,32,34,36) between the client (26) and server (28). The invention allows for long routes and responsive operation on a small, low-powered client despite lags and lapses in communication.

Claims

1. A method (10) for guiding an object, person or vehicle to its destination along a network, comprising the following steps:

a. obtaining (12) destination location and determining or obtaining initial location;

b. determining (14) a complete route guidance tree, on a graph representing a network, from the initial location to the destination location;

c. extracting (16) from the complete route guidance tree a partial route guidance tree proximate to the initial location;

d. determining (18) the current location;

e. determining (20) whether the current location is in the scope of the partial route guidance tree;

f. if the current location is in the scope of the partial route guidance tree, extracting and displaying (22) the next maneuver from the partial route guidance tree, but if the current location is not in the scope of the partial route guidance tree, extracting (24) a partial route guidance tree proximate to the current location; and

,

g. repeating steps d through f until either the destination is reached or the method is interrupted.

2. The method as claimed in claim 1 wherein said graph representing a network represents directional segments as edges and the intersections between segments as vertices.

3. The method as claimed in claim 2 wherein proximate to is based on vertices within a predetermined number of edges of the current location.

4. The method as claimed in claim 2 wherein proximate to is based on vertices within a predetermined number of units of network cost from the current location.

5. The method as claimed in claim 2 wherein proximate to is based on vertices within a predetermined amount of estimated time from the current location.

6. The method as claimed in claim 1 wherein the graph representing the network represents directional segments as vertices and allowable movements between segments as edges.

7. The method as claimed in claim 6 wherein proximate to is based on vertices within a predetermined number of edges of the current location.

8. The method as claimed in claim 6 wherein proximate to is based on vertices within a predetermined number of units of network cost from the current location.

9. The method as claimed in claim 6 wherein proximate to is based on vertices within a predetermined amount of estimated time from the current location.

10. A system for guiding an object, person or vehicle to its destination along a network, comprising:

a. a server means (26) for storing a database representing a physical network, determining (14) a route guidance tree to a destination location on a graph representing that network, and extracting (16) the portion of the route guidance tree proximate to a particular location;

b. a communication means (30, 32, 34, 36) for passing information between the server means and at least one client means; and

,

c. a client means (26) for obtaining (12) destination location, determining (18) or obtaining the client'"'"'s current location, transmitting to the server means using the communication means the destination location and current location, receiving from the server means using the communication means a portion of the route guidance tree proximate to the current location, determining (20) whether the current location is in the scope of this route guidance tree, and either extracting (22) the next maneuver from this route guidance tree, or requesting (24) from the server means using the communication means (36) a further portion of the route guidance tree proximate to the current location.

11. The system as claimed in claim 10 wherein the physical network comprises roadways.

12. The system as claimed in claim 11 wherein the graph representing the physical network represents directional roadway segments as edges and the intersections between roadways as vertices.

13. The system as claimed in claim 12 wherein proximate to is based on vertices within a predetermined number of edges of the current location.

14. The system as claimed in claim 12 wherein proximate to is based on vertices within a predetermined number of units of network cost of the current location.

15. The system as claimed in claim 12 wherein proximate to is based on vertices within a predetermined amount of estimated time from the current location.

16. The system as claimed in claim 11 wherein the graph representing the physical network represents directional roadway segments as vertices and allowable movements between segments as edges.

17. The system as claimed in claim 16 wherein proximate to is based on vertices within a predetermined number of edges of the current location.

18. The system as claimed in claim 16 wherein proximate to is based on vertices within a predetermined number of units of network cost of the current location.

19. The system as claimed in claim 16 wherein proximate to is based on vertices within a predetermined amount of estimated time from the current location.

20. The system as claimed in claim 10 wherein proximate to is based on vertices within a predetermined number of edges of the current location.

21. The system as claimed in claim 10 wherein proximate to is based on vertices within a predetermined number of units of network cost from the current location.

22. The system as claimed in claim 10 wherein proximate to is based on vertices within a predetermined amount of estimated time from the current location.