Method and system for route calculation in a navigation application

• US 6,192,314 B1
• Filed: 03/25/1998
• Issued: 02/20/2001
• Est. Priority Date: 03/25/1998
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: McDonough, William, Khavakh, Asta, Voloshin, Oleg, Wang, Yaoguang
• Primary Examiner(s): Issing, Gregory C.
• Application Number:
  US09/047,698
• Time in Patent Office: 1,063 Days
• Field of Search: 701/209, 701/202, 701/208
• US Class Current: 701/209
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• 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

A program and method for route calculation for use with a navigation system and used with a map database that represents a road network in a geographic region. A route calculation program is adapted to find at least one solution route between a first location on a road network and a second location on the road network. The route calculation program includes a first search tree associated with the first location and a second search tree associated with the second location. Each search tree is adapted to hold gates. Each of the gates represents a physical position on the road network and a direction from the position to another location along a path on the road network. The route calculation program also includes at least one priority queue associated with one of the search trees. The priority queue assigns a priority to one of the gates in the associated search tree based upon an evaluation using a search algorithm. The gate identified as having a higher priority than any other gate in its respective search tree is expanded to determine one or more successor gates thereof. Each of these successor gates so formed is compared to the gates in the other search tree. The process of growing at least one of the search trees by expanding the gate in the search tree that has a higher priority than any other gate in the search tree is continued until a gate in one search tree corresponds to at least one gate in the other search tree.

Claims

1. A route calculation program for use in a navigation system used with a map database stored on a computer readable storage medium, the route calculation program adapted to find a solution route between a first location on a road network represented by said map database and a second location on the road network represented by said map database, wherein said road network is represented in said map database by data that represent each segment of each road between endpoints thereof that correspond to intersections of said segment of road with other segments of roads, said route calculation program comprising:

at least one search tree adapted to hold a plurality of gate data structures, each of said gate data structures representing a physical position on the road network represented by said map database and a direction from said position to another location on said road network represented by said map database, wherein one of said Rate data structures is a seed gate data structure that represents said first location as a position along a segment of a road between endpoints thereof and a direction from said position along said represented segment of road; and

a priority queue referencing said gate data structures in said at least one search tree and assigning a priority to one of said gate data structures;

wherein said route calculation program is adapted to expand said one of said gate data structures to determine successor gate data structures thereof and to compare each of said successor gate data structures to gate data structures associated with said second location.

2. The invention of claim 1 further comprising a focus, said focus representing a physical location relative to which said gate data structures in said at least one search tree are evaluated to determine said priority.

3. The invention of claim 2 wherein said focus is configurable.

4. The invention of claim 1 wherein said route calculation program is further adapted to invoke a search algorithm to perform said evaluation for assigning said priority.

5. The invention of claim 4 wherein said algorithm is configurable.

6. The invention of claim 4 wherein said search algorithm is one of the A* algorithm and the Dykstra algorithm.

7. The invention of claim 1 wherein said map database includes a plurality of road segment data records each of which represents a road segment of said road network,

wherein said plurality of gate data structures comprise seed gate data structures and other-than-seed gate data structures,

wherein the physical position represented by each of said other-than-seed gate data structures corresponds to an endpoint of a road segment, and

wherein the physical position represented by each of said seed gate data structures corresponds to a position along a road segment between endpoints thereof.

8. A route calculation tool program for use in a navigation system used with a map database that represents a road network in a geographic region, wherein said road network is said may database by data that represent each segment of road between endpoints thereof that correspond to intersections of said segment of road with other segment of roads, said route calculation tool program comprising:

a first search tree associated with an origin and a second search tree associated with a destination, wherein each of said search trees includes gate data structures each of which represents a position on a road network represented by said map database and a direction by which said position is accessible in a desired direction of travel, and wherein one of said gate data structures in said first search tree is a seed gate data structure that represents said origin as a first position along a first segment of a road between endpoints thereof and a direction from said position along said first segment of a road and wherein one of sad gate data structures in said second search tree is a seed gate data structure that represents the destination as a second position along a second segment of a road between endpoints thereof and a direction from said second position along said second segment of a road;

wherein the route calculation tool program includes at least one priority queue that references one of said gate data structures in one of said search trees; and

wherein said route calculation tool program expands said one gate data structure referenced by said priority queue to form successor gate data structures thereof whereby a solution route is obtained by at least one gate data structure in said first search tree corresponding to at least one gate data structure in said second search tree.

9. The invention of claim 8 wherein each of said search trees further comprises a focus, each focus representing a physical location relative to which each of said gate data structures in its respective search tree is evaluated to determine said priority.

10. The invention of claim 9 wherein said focus is configurable.

11. The invention of claim 9 wherein the physical location represented by the focus of said first search tree corresponds to a position represented by a gate data structure in said second search tree.

12. A method of performing a route calculation function using a navigation system that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, comprising the steps of:

identifying at least one seed gate associated with a first location in said geographic region through which a solution route is constrained to pass, wherein said seed gate comprises an associated locus representing a position along a portion of a road represented by a road segment record and a seed gate target node corresponding to a node of the road segment record, said seed gate target node representing an endpoint of the portion of a road represented by said road segment record by which said location is accessible in a desired direction of travel;

expanding said at least one seed gate to form at least one successor gate, wherein each successor gate so formed comprises an associated node corresponding to the target node of the seed gate which was expanded to form said successor gate and a successor gate target node, said successor gate target node corresponding to a node of a road segment record that represents a portion of a road which is accessible in the desired direction of travel between the positions represented by the associated node and the target node of the successor gate;

comparing each successor gate formed by said expanding step to corresponding gates associated with a second location in said geographic region through which said solution route is constrained to pass and outputting a solution route if a match is found;

if a match is not found in said comparing step, evaluating each successor gate to determine one successor gate having a higher priority than any other successor gate;

expanding said one successor gate having the higher priority than any other successor gate to form at least one additional successor gate, wherein each additional successor gate comprises an associated node corresponding to the target node of the successor gate which was expanded to form said additional successor gate and a target node of the successor gate, said target node of said successor gate corresponding to a node of a road segment record that represents a portion of a road which is accessible in the desired direction of travel between the positions represented by the associated node and the target node of the additional successor gate;

comparing each successor gate formed by said expanding step to said second location in said geographic region through which said solution route is constrained to pass and outputting a solution route if a match is found; and

if a match is not found in said second comparing step, continuing to perform said evaluating, expanding, and comparing steps until a match is found.

13. The method of claim 12 wherein said step of expanding said one successor gate further comprising the steps of

evaluating a rank of a road segment along a potential successor gate; and

suppressing from consideration said potential gate if said rank is below a predetermined threshold.

14. The method of claim 13 wherein said step of suppressing is performed selectively upon segments meeting predetermined criteria.

15. A method of providing partial solution routes using a navigation system that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, comprising the steps of:

identifying at least one seed gate associated with a first location in said geographic region through which a solution route is constrained to pass, wherein said seed gate comprises an associated locus representing a position along a portion of a road represented by a road segment record and a seed gate target node corresponding to a node of the road segment record, said seed gate target node representing an endpoint of the portion of a road represented by said road segment record by which said location is accessible in a desired direction of travel;

expanding said at least one seed gate to form at least one successor gate, wherein each successor gate so formed comprises an associated node corresponding to the target node of the seed gate which was expanded to form said successor gate and a successor gate target node, said successor gate target node corresponding to a node of a road segment record that represents a portion of a road which is accessible in the desired direction of travel between the positions represented by the associated node and the target node of the successor gate;

comparing each successor gate formed by said expanding step to a second location in said geographic region through which said solution route is constrained to pass;

evaluating each successor gate to determine one successor gate having a higher priority than any other successor gate;

expanding said one successor gate having the higher priority than any other successor gate to form at least one additional successor gate, wherein each additional successor gate comprises an associated node corresponding to the target node of the successor gate which was expanded to form said additional successor gate and a target node of the successor gate, said target node of said successor gate corresponding to a node of a road segment record that represents a portion of a road which is accessible in the desired direction of travel between the positions represented by the associated node and the target node of the additional successor gate; and

prior to finding a match when comparing each successor gate formed by said expanding step to said second location in said geographic region through which said solution route is constrained to pass, outputting a partial solution route comprised of a list of segments corresponding to at least some of the gates which had been expanded based upon having a higher priority than any other gate.

16. A route calculation tool program for use in a navigation system and adapted to calculate a route between a first location and a second location, said route calculation tool program comprising:

object logic operatively executed by a processor of said navigation system, the object logic comprising a plurality of independent program objects, wherein each program object receives input data and provides output data according to a property of the program object, wherein said route calculation tool program comprises;

at least one of the program objects comprising a route calculation program object operatively adapted to receive a first waypoint program object representing said first location and a second waypoint program object representing said second location;

wherein said route calculation program object further comprises;

an outbound search tree program object including at least one seed gate and successor gates thereof, wherein said at least one seed gate represents a position along a road segment from which the first location can be exited, said position derived from said first waypoint program object;

an inbound search tree program object including said at least one seed gate and successor gates thereof, wherein said at least one seed gate represents a position along a road segment into which the second location can be entered, said position derived from said second waypoint program object;

an outbound priority queue program object including prioritized references to unexpanded gates in said outbound search tree program object; and

an inbound priority queue object including prioritized references to unexpanded gates in said inbound search tree program object; and

wherein at least one of said search tree program object is adapted to grow by expanding the gates therein to find a solution route when said search tree program objects include at least one common gate.

17. The invention of claim 16 wherein said route calculation program object is further adapted to receive a vehicle object containing parameters of a vehicle in which said navigation system is installed, and wherein said route calculation program object utilizes said parameters in selecting gates to be expanded.

18. The invention of claim 16 wherein said route calculation object is further adapted to receive a configuration object containing parameters input via said user interface, and wherein said route calculation object utilizes said parameters in selecting gates to be expanded.