Loop-based route finding and navigation

• US 7,831,386 B2
• Filed: 01/05/2007
• Issued: 11/09/2010
• Est. Priority Date: 11/17/2006
• Status: Active Grant

• Current Assignee: ZAMA Innovations LLC
• Original Assignee: Ian Cummings
• Inventors: Cummings, Ian
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Sample, Jonathan L
• Application Number:
  US11/620,330
• Publication Number:
  US 20080120027A1
• Time in Patent Office: 1,404 Days
• Field of Search: None
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A navigation system and method uses loops as opposed to existing search techniques to more expeditiously find routes on a map from a starting point to a destination. Roads on a map are traced to form one or more continuous loops. Information regarding the loops is stored for future reference. A starting point and at least one destination are specified, and loops that connect the loops containing the starting point and destination are determined. A route is then formulated from the starting point to the destination using road segments or intersections where the identified loops are mutually contiguous. A list is generated including the loops and the road segments associated therewith. The road segments of an initial loop are examined and, if a road segment or intersection common to a next loop is identified, the road segments of that loop are examined, and so on, until a route from the starting point to the destination is found. Alternatively the route may be formulated by searching for routes along the roads that form one or more continuous loops connecting the starting point and the destination. Various speed-up algorithms and/or heuristics may be applied to the route formulation. The method finds application is many fields of endeavor, including wireless client-server navigation; embedded/dedicated automotive navigation, and logistics control, to name a few.

Claims

1. A navigation method, comprising the steps of:

providing a map having a network of roads and intersections;

tracing the roads to form one or more continuous loops;

specifying a starting point and a destination on the map;

graphing the map such that the loops are represented as nodes and common roads or intersections between the loops are represented as edges; and

using a greedy, A*, SMA*, IDA*, or annealing search method on the graph to identify a set of one or more loops linked by mutually contiguous roads and/or intersections such that a route can be traced from the starting point to the destination along the roads and/or intersections comprising the identified loops.

2. The method claim 1, including the step of using a plurality of initial loops as the starting node of the search method.

3. The method of claim 1, including the step of searching for routes along the roads that form one or more continuous loops connecting the starting point and the destination.

4. The method claim 1, including the steps of:

designating one or more of the loops as major loops;

if a major loop is added to a candidate set of identified loops, adding only major loops to the candidate set until a major loop enclosing , including, or in proximity to the destination is found.

5. The method claim 1, including the steps of:

designating one or more of the loops as major loops;

formulating a partial route beginning with the major loop including, enclosing, or in proximity to the starting point and ending with the major loop including, enclosing, or in proximity to the end point; and

formulating a final route from the major loops to the starting point and destination.

6. The method claim 1, including the steps of:

formulating two partial routes by simultaneously generated paths from the starting point to the destination and from the destination to the starting point; and

formulating a final route by finding a common loop between the two generated routes.

7. The method claim 1, including the step of applying one or more heuristics to the route formulation.

8. The method claim 1, including the step of disallowing intersections, maneuvers, roads, or loops.

9. The method claim 8, including the step of investigating a reverse path in the event that an intersection, maneuver, road, or loop is disallowed.

10. The method claim 1, including the step of using one or more heuristics to formulate a route around a barrier.

11. The method claim 1, including the step of deleting road segments that cancel.

12. The method claim 1, including the steps of:

specifying multiple destinations; and

using the steps to visit each of the destinations in a sequence specified by a user or algorithm.

13. The method claim 1, including the step of using real time, historical, predicted road traffic load or estimated travel times to improve route formulation.

14. The method claim 1, wherein the steps are used in conjunction with a wireless client-server navigation system.

15. The method claim 1, wherein the steps are used in conjunction with an automotive navigation system.

16. The method claim 1, wherein the steps are used in conjunction with a logistics control system.

17. The method claim 1, wherein the steps are used in conjunction with a fully automated guidance system.

18. The method claim 1, wherein the steps are used in conjunction with a traffic management system.

19. The method claim 1, including the steps of:

formulating an initial route; and

improving the route by adding, deleting, and/or substituting loops.

20. The method claim 19, including the step of applying one or more heuristics to improve the route.

21. The method claim 4, in which the network contains one or more limited-access roads that can be entered or exited only at a limited number of points, and in which one or more limited major loops are designated which consist partially or entirely of limited access roads, the method further comprising the steps of:

associating each limited major loop, and any loops in proximity to and/or enclosed by it, with one or more access points at which entry and/or exit from the limited major loop is allowed;

and if it is desirable to traverse the limited major loop;

generating a route from a loop containing the start point or other loop on the generated route to an access point on the limited major loop associated the with the starting point or another point on the generated route; and

if it is desirable to exit the limited major loop;

generating a route from the access point of the limited major loop associated with the loop containing the end point or another loop to which travel is desirable to the loop on which the end location lies or another loop to which travel is desirable.

22. The method of claim 21, further including the step of applying one or more rules to determine which access points of a limited major loop are associated with a loop.

23. The method of claim I, further including the steps of:

determining possible loops from the map; and

storing data describing the possible loops for future route generation.