System for recalculating a path

• US 6,038,509 A
• Filed: 01/22/1998
• Issued: 03/14/2000
• Est. Priority Date: 01/22/1998
• Status: Expired due to Term

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Etak, Inc. (TomTom NV)
• Inventors: Fernandez, Rodney Jude, Poppen, Richard Frederick
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Arthur, Gertrude
• Application Number:
  US09/012,062
• Time in Patent Office: 782 Days
• Field of Search: 701/200, 701/23, 701/25, 701/26, 701/201, 701/208, 701/209, 701/210, 701/211, 701/221, 701/224, 340/990, 340/995, 340/988, 370/238, 370/255, 370/400
• US Class Current: 701/210
• 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 typical pathfinding system provides a user with a set of directions for following a path from an origin to a destination in a network. If the user deviates from the path, the system for recalculating a path determines a new path which directs the user from the user'"'"'s new location, which is off the original path, to the destination. To decrease the amount of time needed to determine the new path to the destination, the system adds links to the network. Each of the added links connect nodes from the original path directly to the destination. A new path is determined from the new location to the destination using the augmented network.

Claims

1. A method of finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising the steps of:

augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and

determining said new path from said new origin to said destination using said electronic representation of said network with said new links.

2. A method according to claim 1, wherein:

said electronic representation of said network being stored in a first set of one or more processor readable files and said new links stored in a second set of one or more processor readable files.

3. A method according to claim 1, further including the step of:

editing said new path to only include travel along original links.

4. A method according to claim 1, further including the step of:

reporting said new path.

5. A method according to claim 1, further including the step of:

determining said new origin.

6. A method according to claim 5, wherein:

said step of determining said new origin estimates said new origin to be a location where a user will be at a future time.

7. A method according to claim 1, wherein:

said subset of said original nodes being rejoining nodes.

8. A method according to claim 1, wherein:

said step of augmenting includes identifying rejoining nodes, each of said new links being connected from one of said rejoining nodes to said destination.

9. A method according to claim 1, wherein:

each node of said subset of said original nodes does not have a direct link to said destination prior to said step of augmenting.

10. A method according to claim 1, wherein:

each node of said subset of said original nodes does not have a direct link to said destination prior to said step of augmenting and is within a predetermined distance from said new origin.

11. A method according to claim 1, wherein:

said subset being defined to include original nodes having a lower bounds which is less than any upper bounds of original nodes that do not have a link directly to said destination.

12. A method according to claim 1, further including the step of:

receiving operator input, wherein said deviation from said original path occurring after travel to a first node and before travel to a second node and said step of determining said new path does not utilize a link representing a path to said second node in response to said operator input.

13. A method according to claim 1, wherein:

an original node having an original link directly to said destination and not being visited prior to said deviation has a corresponding costs for traversing said original link;

said step of augmenting includes editing said corresponding cost.

14. A method according to claim 1, wherein:

said step of augmenting includes assigning costs to said new links.

15. A method according to claim 14, wherein:

each new link being associated with an original node; and

said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path.

16. A method according to claim 15, wherein:

said cost is travel time.

17. A method according to claim 15, wherein:

said cost is distance.

18. A method according to claim 15, wherein:

said constant is equal to one.

19. A method according to claim 15, wherein:

said constant is greater than or equal to zero; and

said constant is less than or equal to one.

20. A method according to claim 15, further including the steps of receiving operator input;

and

determining said constant based on said operator input.

21. A method according to claim 1, wherein:

said step of augmenting includes removing an original link.

22. A method according to claim 21, further including the step of:

receiving operator input, said step of removing an original link being based on said operator input.

23. A method according to claim 1, further including the steps of:

identifying rejoining nodes, each of said new links being connected from one of said rejoining nodes to said destination;

editing said new path to only include travel along original links; and

reporting said new path;

wherein said electronic representation of a network is an electronic map, said step of augmenting includes assigning costs to said new links, each new link being associated with an original node, said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path, and said constant is greater than or equal to zero and less than or equal to one.

24. A method according to claim 1, wherein:

said electronic representation of a network is an electronic map.

25. A method according to claim 24, further including the step of:

editing said new path to only include travel along original links.

26. A method according to claim 24, wherein:

said step of augmenting includes assigning costs to said new links.

27. A method according to claim 26, wherein:

each new link being associated with an original node; and

said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path.

28. A method of finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising the steps of:

augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and

determining said new path from said new origin to said destination using said electronic representation of said network with said new links, said deviation from said original path occurring after travel to a first node and before travel to a second nodes, said step of determining said new path does not utilize a link representing travel from said first node to said second node.

29. A processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming a processor to perform a method for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, said method comprising the steps of:

augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and

determining said new path from said new origin to said destination using said electronic representation of said network with said new links.

30. A processor readable storage medium according to claim 29, wherein, said method further includes the step of:

editing said new path to only include travel along original links.

31. A processor readable storage medium according to claim 29, wherein, said method further includes the step of:

reporting said new path.

32. A processor readable storage medium according to claim 29, wherein, said method further includes the step of:

determining said new origin.

33. A processor readable storage medium according to claim 29, wherein:

each node of said subset of said original nodes does not have a direct link to said destination prior to said step of augmenting.

34. A processor readable storage medium according to claim 29, wherein:

each node of said subset of said original nodes does not have a direct link to said destination prior to said step of augmenting and is within a predetermined distance from said new origin.

35. A processor readable storage medium according to claim 29, wherein:

said subset being defined to include original nodes having a lower bounds which is less than any upper bounds of original nodes that do not have a link directly to said destination.

36. A processor readable storage medium according to claim 29, wherein, said method further includes the step of:

receiving operator input, wherein said deviation from said original path occurring after travel to a first node and before travel to a second node and said step of determining said new path does not utilize a link representing a path to said second node in response to said operator input.

37. A processor readable storage medium according to claim 29, wherein:

said step of augmenting includes assigning costs to said new links.

38. A processor readable storage medium according to claim 37, wherein:

each new link being associated with an original node; and

said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path.

39. A processor readable storage medium according to claim 29, wherein:

said electronic representation of a network is an electronic map.

40. A processor readable storage medium according to claim 39, wherein, said method further includes the steps of:

identifying rejoining nodes, each of said new links being connected from one of said rejoining nodes to said destination,

editing said new path to only include travel along original links; and

reporting said new path;

wherein said step of augmenting includes assigning costs to said new links, each new link being associated with an original node, said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path, and said constant is greater than or equal to zero and less than or equal to one.

41. A processor readable storage medium according to claim 39, wherein, said method further includes the step of:

editing said new path to only include travel along original links.

42. A processor readable storage medium according to claim 39, wherein:

said step of determining includes assigning costs to said new links.

43. A processor readable storage medium according to claim 39, wherein:

each new link being associated with an original node; and

said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path.

44. A system for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising:

means for augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and

means for determining said new path from said new origin to said destination using said electronic representation of said network with said new links.

45. A system according to claim 44, further including:

means for reporting said new path, said electronic representation of said network being an electronic map.

46. A system for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising:

one or more processor readable storage mediums for storing said electronic representation of said network; and

a processor, in communication with said one or more processor readable mediums, said processor programmed to;

augment said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination, and

determine said new path from said new origin to said destination using said electronic representation of said network with said new links.

47. A system according to claim 46, wherein:

said electronic representation of said network is an electronic map.

48. A system according to claim 47, further including:

a display, in communication with said processor, for reporting said new path.

49. A system according to claim 47, wherein:

said processor further programmed to edit said new path to only include travel along original links.

50. A system according to claim 47, wherein:

each node of said subset of said original nodes does not have a direct link to said destination prior to adding said new links.

51. A system according to claim 47, wherein:

said deviation from said original path occurring after travel to a first node and before travel to a second node; and

said new path does not include a link representing travel from said first node to said second node.

52. A system according to claim 47, wherein:

said processor further programmed to assign costs to said new links.