Automated route determination to avoid a particular maneuver

• US 7,133,771 B1
• Filed: 12/30/2002
• Issued: 11/07/2006
• Est. Priority Date: 08/29/2002
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: America Online Inc. (Warner Bros. Discovery, Inc.)
• Inventors: Nesbitt, David W.
• Primary Examiner(s): BLACK, THOMAS G
• Application Number:
  US10/330,669
• Time in Patent Office: 1,408 Days
• Field of Search: 701/202, 701/200, 701/201, 701/205, 701/209, 701/210, 701/211, 731/78.R, 340/995.19, 340/995.2, 340/995.21, 340/995.23
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

A preferred route may be determined from an origin location to a destination location. The preferred route avoids a particular maneuver or particular maneuvers identified by a user. The determination is made by processing directed links (e.g., one-way edges) in a graph that includes one or more links and two or more nodes. The determination of a preferred route may include an estimate of the time required at one or more intersections along alternative routes and/or an estimate of the time required to travel the alternative routes based on the day of the week or the day of the year in which travel occurs. Individual routing preferences, such as a preference of a rural over an urban route and avoiding particular maneuvers in a route, also may be considered.

Claims

1. A computer-readable medium or propagated signal having embodied thereon a computer program configured to determine a preferred route using a computer-implemented routing system, the medium or signal comprising one or more code segments configured to:

access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

receive a user-selected indication of at least one maneuver to be avoided;

receive a user-selected indication of at least one feature to be avoided;

determine a preferred route from the origin to the destination wherein the preferred route does not include the at least one maneuver indicated by the received user-selected indication and does not include the at least one feature indicated by the received user-selected indication;

associate the user-selected indication of the at least one maneuver to be avoided with a user identity; and

store both the user-selected indication of the at least one maneuver to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one maneuver indicated by the stored user-selected indication of the at least one maneuver to be avoided, in response to a request received from the user identity.

2. The medium or signal of claim 1 wherein:

the one or more code segments are further configured to determine a first route from the origin to the destination, with the first route including maneuvers, and

the received user-selected indication is a user-selected indication of at least one maneuver of the first route to be avoided.

3. The medium or signal of claim 1 wherein the one or more code segments are further configured to communicate the first route from the routing system to a user system.

4. The medium or signal of claim 1 wherein the one or more code segments are further configured to repeat the receiving of the user-selected indication and the determining of a preferred route as additional user-selected indications are received.

5. The medium or signal of claim 1 wherein the routing system comprises a routing system provided through an Internet service provider.

6. The medium or signal of claim 1 wherein the routing system and a user system use the same processor.

7. The medium or signal of claim 1 wherein the one or more code segments configured to communicate the preferred route comprise one or more code segments configured to communicate the preferred route over a connection that is established using the Internet.

8. The medium or signal of claim 1 wherein the second preferred route from the second origin to a second destination is the same as the preferred route from the origin to the destination.

9. The medium or signal of claim 1 wherein the second preferred route from the second origin to a second destination is different from as the preferred route from the origin to the destination.

10. The medium or signal of claim 1 wherein the one or more code segments are further configured to:

enable the presentation of the stored user-selected indication of the at least one maneuver to be avoided to the user identity associated with the stored user-selected indication of the at least one maneuver to be avoided; and

enable the user identity to modify the stored user-selected indication of the at least one maneuver to be avoided.

11. The medium or signal of claim 2 wherein the one or more code segments are further configured to:

enable a user to view the first route and the preferred route; and

receive an indication, from the user, of a selected route wherein the selected route is one of the first route or the preferred route.

12. The medium or signal of claim 1 wherein a feature to be avoided comprises a road type to be avoided.

13. The medium or signal of claim 1 wherein a feature to be avoided comprises a type of terrain over which the route passes.

14. The system of claim 6 further comprising:

means for enabling a user to view the first route and the preferred route; and

means for receiving an indication, from the user, of a selected route wherein the selected route is one of the first route or the preferred route.

15. A system for determining a preferred route, the system comprising:

means for accessing an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

means for receiving a user-selected indication of at least one maneuver to be avoided;

means for receiving a user-selected indication of at least one feature to be avoided,

means for determining a preferred route from the origin to the destination wherein the preferred route does not include the at least one maneuver indicated by the received user-selected indication and does not include the at least one feature indicated by the received user-selected indication;

means for associating the user-selected indication of the at least one maneuver to be avoided with a user identity; and

means for storing both the user-selected indication of the at least one maneuver to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one maneuver indicated by the stored user-selected selected indication of the at least one maneuver to be avoided, in response to a request received from the user identity.

16. The system of claim 15 further comprising means for determining a first route from the origin to the destination, with the first route including maneuvers, wherein the received user-selected indication is a user-selected indication of at least one maneuver of the first route to be avoided.

17. The system of claim 15 further comprising means for communicating the first route from the routing system to a user system.

18. The system of claim 15 further comprising means for repeating the receiving of the user-selected indication and the determining of a preferred route as additional user-selected indications are received.

19. The system of claim 15 wherein the routing system comprises a routing system provided through an Internet service provider.

20. The system of claim 15 the routing system and a user system use the same processor.

21. The system of claim 15 further comprising means for communicating the preferred route over a connection that is established using the Internet.

22. The system of claim 15 wherein the second preferred route from the second origin to a second destination is the same as the preferred route from the origin to the destination.

23. The system of claim 15 wherein the second preferred route from the second origin to a second destination is different from as the preferred route from the origin to the destination.

24. The system of claim 15 comprising:

means for enabling the presentation of the stored user-selected indication of the at least one maneuver to be avoided to the user identity associated with the stored user-selected indication of the at least one maneuver to be avoided; and

means for enabling the user identity to modify the stored user-selected indication of the at least one maneuver to be avoided.

25. The system of claim 15 wherein a feature to be avoided comprises a road type to be avoided.

26. The system of claim 15 wherein a feature to be avoided comprises a type of terrain over which the route passes.

27. A computer-readable medium or propagated signal having embodied thereon a computer program configured to determine a preferred route using a computer-implemented routing system, the medium or signal comprising one or more code segments configured to:

access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

determine a first route from the origin to the destination, the first route including maneuvers;

receive a user-selected indication of at least one maneuver of the first route to be avoided;

determine a second route from the origin to the destination, with the second route not including the at least one maneuver indicated by the received user-selected indication;

enable a user to view the first route and the second route;

receive an indication, from the user, of a first preferred route wherein the first preferred route is one of the first route or the second route;

associate the user-selected indication of the at least one maneuver to be avoided with a user identity; and

store both the user-selected indication of the at least one maneuver to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one maneuver indicated by the stored user-selected indication of the at least one maneuver to be avoided, in response to a request received from the user identity.

28. The medium of claim 27 wherein the one or more code segments are further configured to communicate the first route and the second route from the routing system to a user system for display on a user system.

29. The medium of claim 27 wherein the one or more code segments are further configured to repeatedly receive of the user-selected indication and the determine a second route as additional user-selected indications are received.

30. The medium of claim 27 wherein the one or more code segments are further configured to:

receive a user-selected indication of at least one feature to be avoided; and

determine a third preferred route from the origin to the destination, with the third preferred route not including the at least one feature indicated by the received user-selected indication.

31. The medium of claim 30 wherein a feature to be avoided comprises a road type to be avoided.

32. The medium of claim 30 wherein a feature to be avoided comprises a type of terrain over which the route passes.

33. A system for determining a preferred route comprising:

means for accessing an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

means for determining a first route from the origin to the destination, the first route including maneuvers;

means for receiving a user-selected indication of at least one maneuver of the first route to be avoided;

means for determining a second route from the origin to the destination, with the second route not including the at least one maneuver indicated by the received user-selected indication;

means for enabling a user to view the first route and the second route;

means for receiving an indication, from the user, of a first preferred route wherein the first preferred route is one of the first route or the second route;

means for associating the user-selected indication of the at least one maneuver to be avoided with a user identity; and

means for storing both the user-selected indication of the at least one maneuver to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one maneuver indicated by the stored user-selected indication of the at least one maneuver to be avoided, in response to a request received from the user identity.

34. The system of claim 33 further comprising means for communicating the first route and the second route to a user system for display on a user system.

35. The system of claim 33 further comprising means for repeatedly receiving of the user-selected indication and determining a second route as additional user-selected indications are received.

36. The system of claim 33 further comprising:

means for receiving a user-selected indication of at least one feature to be avoided; and

means for using the routing system to determine a third preferred route from the origin to the destination, with the third preferred route not including the at least one feature indicated by the received user-selected indication.

37. The system of claim 36 wherein a feature to be avoided comprises a road type to be avoided.

38. The system of claim 36 wherein a feature to be avoided comprises a type of terrain over which the route passes.

39. A computer-readable medium or propagated signal having embodied thereon a computer program configured to determine a preferred route using a computer-implemented routing system, the medium or signal comprising one or more code segments configured to:

access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

receive a user-selected indication of at least one feature to be avoided;

determine a first preferred route from the origin to the destination, with the first preferred route not including the at least one feature indicated by the received user-selected indication;

associate the user-selected indication of the at least one feature to be avoided with a user identity; and

store both the user-selected indication of the at least one feature to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one feature indicated by the stored user-selected indication of the at least one feature to be avoided, in response to a request received from the user identity,

wherein a feature to be avoided comprises a type of terrain over which the route passes.

40. The medium of claim 39 wherein a feature to be avoided comprises a road type to be avoided.

41. The medium of claim 40 wherein the road type to be avoided comprises a rotary.

42. The medium of claim 39 wherein the type of terrain comprises mountainous terrain.

43. The medium of claim 39 wherein the one or more code segments are further configured to:

determine a first route from the origin to the destination, the first route including maneuvers;

receive a user-selected indication of at least one maneuver to be avoided;

determine the first preferred route from the origin to the destination, with the first preferred route not including the at least one maneuver indicated by the received user-selected indication and not including the at least one feature indicated by the received user-selected indication;

enable a user to view the first route and the first preferred route; and

receive an indication, from the user, of a selected route wherein the selected route is one of the first route or the first preferred route.

44. A system for determining a preferred route comprising:

means for accessing an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

means for receiving a user-selected indication of at least one feature to be avoided;

means for determining a first preferred route from the origin to the destination, with the first preferred route not including the at least one feature indicated by the received user-selected indication;

means for associating the user-selected indication of the at least one feature to be avoided with a user identity; and

means for storing both the user-selected indication of the at least one feature to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one feature indicated by the stored user-selected indication of the at least one feature to be avoided, in response to a request received from the user identity,

wherein a feature to be avoided comprises a type of terrain over which the route passes.

45. The system of claim 44 wherein a feature to be avoided comprises a road type to be avoided.

46. The system of claim 45 wherein the road type to be avoided comprises a rotary.

47. The system of claim 44 wherein the type of terrain comprises mountainous terrain.

48. The system of claim 44 further comprising:

means for determining a first route from the origin to the destination, the first route including maneuvers;

means for receiving a user-selected indication of at least one maneuver to be avoided;

means for using the routing system to determine the preferred route from the origin to the destination, with the preferred route not including the at least one maneuver indicated by the received user-selected indication and not including the at least one feature indicated by the received user-selected indication;

means for enabling a user to view the first route and the first preferred route; and

means for receiving an indication, from the user, of a selected route wherein the selected route is one of the first route or the first preferred route.

49. A method for determining a preferred route, the method comprising:

accessing an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

receiving a user-selected indication of at least one maneuver to be avoided;

receiving a user-selected indication of at least one feature to be avoided;

determining a preferred route from the origin to the destination wherein the preferred route does not include the at least one maneuver indicated by the recieved user-selected indication and does not included the at least one feature indicated by the received user-selected indication;

associating the user-selected indication of the at least one maneuver to be avoided with a user identity; and

storing both the user-selected indication of the at least one maneuver to be avoided and the association of the user-selected indication and the user identity for later use determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one maneuver indicated by the stored user-selected indication of the at least one maneuver to be avoided, in response to a request received from the user identity.

50. The method of claim 49 further comprising determining a first route from the origin to the destination, with the first route including maneuvers, wherein the received user-selected indication is a user-selected indication of at least one maneuver of the first route to be avoided.

51. The method of claim 49 further comprising communicating the first route from the routing system to a user system.

52. The method of claim 49 further comprising repeating the receiving of the user-selected indication and the determining of a preferred route as additional user-selected indication are received.

53. The method of claim 49 wherein the second preferred route from the second origin to a second destination is the same as the preferred route from the origin to the destination.

54. The method of claim 49 wherein the second preferred route from the second orogin to a second destination is different from the preferred route from the origin to the destination.

55. The method of claim 49 comprising:

enabling the presentation of the stored user-selected indication of the at least one maneuver to be avoided to the user identity associated with the stored user-selected indication of the at least one maneuver to be avoided; and

enabling the user identity to modify the stored user-selected indication of the at least one maneuver to be avoided.

56. The method of claim 49 further comprising:

enabling a user to view the first route and the preferred route; and

receiving an indication, from the user, of a selected route wherein the selected route is one of the first route or the preferred route.

57. The method of claim 49 wherein a feature to be avoided comprise a type of terrain over which the route passes.

58. An apparatus for determining a preferred route, the apparatus being configured to:

access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

receive a user-selected indication of at least one maneuver to be avoided;

receive a user-selected indication of at least one feature to be avoided;

determine a preferred route from the origin to the destination wherein the preferred route does not include the at least one maneuver indicated by the received user-selected indication and does not include the at least one feature indicated by the received user-selected indication;

associate the user-selected indication of the at least one maneuver to be avoided with a user identity; and

store both the user-selected indication of the at least one maneuver to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one maneuver indicated by the stored user-selected indication of the at least one maneuver to be avoided, in response to a request received from the user identify.

59. The apparatus of claim 58 further configured to determine a first route from the origin to the destination, with the first route including maneuvers, wherein the received user-selected indication is a user-selected indication of at least one maneuver of the first route to be avoided.

60. The apparatus of claim 58 further configured to communicate the first route from the routing system to a user system.

61. The apparatus of claim 58 further configured to repeat the receiving of the user-selected indication and the determining of a preferred route as additional user-selected indications are received.

62. The apparatus of claim 58 wherein the second preferred route from the second origin to a second destination is the same as the preferred route from the origin to the destination.

63. The apparatus of claim 58 wherein the second preferred route from the second origin to a second destination is different from the preferred route from the origin to the destination.

64. The apparatus of claim 58 further configured to:

enable the presentation of the stored user-selected indication of the at least one maneuver to be avoided to the user identity associated with the stored user-selected indication of the at least one maneuver to be avoided; and

enable the user identity to modify the stored user-selected indication of the at least one maneuver to be avoided.

65. The apparatus of claim 58 further configired to:

enable a user to view the first route and the preferred route; and

receive and indication, from the user, of a selected route wherein the selected route is one of the first route or the preferred route.

66. The apparatus of claim 58 wherein a feature to be be avoided comprises a type of terrain over which the route passes.

67. A method for determining a preferred route comprising:

accessing an origin and a destination in a routing graph representing an network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

determining a first route from the origin to the destination, the first route including maneuvers;

receiving a user-selected indication of at least one maneuver of the first route to be avoided;

determining a second route from the origin to the destination, with the second route not including the at least one maneuver indicated by the received user-selected indication;

enabling a user to view the first route and the second route;

receiving an indication, from the user, of a first preferred route wherein the first preferred route is one of the first route or the second route;

associating the user-selected indication of the at least one maneuver to be avoided with a user identity; and

storing both the user-selected indication of the at least one maneuver to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one maneuver indicated by the stored user-selected indication of the at least one maneuver to be avoided, in response to a request recieved from the user identity.

68. The method of claim 67 further comprising communicating the first route and the second route to a user system for display on a user system.

69. The method of claim 67 further comprising repeatedly receiving of the user-selected indication and determining a second route as additional user-selected indications are received.

70. The method of claim 67 further comprising:

receiving a user-selected indication of at least one feature to be avoided; and

using the routing system to determine a third preferred route from the origin to the destination, with the third preferred route not including the at least one feature indicated by the received user-selected indication.

71. The method of claim 70 wherein a feature to be avoided comprises a road type to be avoided.

72. The method of claim 70 wherein a feature to be avoided comprises a type of terrain over which the route passes.

73. An apparatus for determining a preferred route, the apparatus being configured to:

access an origin and a destination in a routing graph representing a network of roads and each node representing an intersection that includes at least one road;

determine a first route from the origin to the destination, the first route including maneuvers;

receive a user-selected indication of at least one maneuver of the first route to be avoided;

determine a second route from the origin to the destination, with the second route not including the at least one maneuver indicated by the received user-selected indication;

enable a user to view the first route and the second route;

receive an indication, from the user, of a first preferred route wherein the first route is one of the first route or the second route;

associate the user-selected indication of the at least one maneuver to be avoided with a user identity; and

store both the user-selected indication of the least one maneuver to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one maneuver indicated by the stored user-selected indication of the at least one maneuver to be avoided, in response to a request received from the user identity.

74. The apparatus of claim 73 further configured to communicate the first route and the second route to a user system for display on a user system.

75. The apparatus of claim 73 further configured to repeatedly receive of the user-selected indication and determine a second route as additional user-selected indications are received.

76. The apparatus of claim 73 further configured to:

receive a user-selected indication of at least one feature to be avoided; and

determine a third preferred route from the origin to the destination, with the third preferred route not including the at least one feature indicated by the received user-selected indication.

77. The apparatus of claim 76 wherein a feature to be avoided comprises a road type to be avoided.

78. The apparatus of claim 76 wherein a feature to be avoided comprises a type of terrain over which the route passes.

79. A method for determining a preferred route, the method comprising:

accessing an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing an intersection that includes at least one road;

receiving a user-selected indication of the at least one feature to be avoided;

determining a first preferred route from the origin to the destination, with the first preferred route not including the at least one feature indicated by the recieved user-selected indication;

associating the user-selected indication of the at least one feature to be avoided with a user identity; and

storing both the user-selected indication of the at least one feature to be avoided and the association of the user-selected indication and the user identity for later use in determining a second preferred route from a second origen to a second destination, with the second preferred route not including the at least one feature indicated by the stored user-selected indication of the at least one feature to be avoided, in response to a request recieved from the user identity,

wherein a feature to be avoided comprises a type of terrain over which the route passes.

80. The method of claim 79 wherein the type of terrain comprises mountainous terrain.

81. The method of claim 79 further comprising:

determining a first route from the origin to the destination, the first route including maneuvers;

associating the user

receiving a user-selected indication of at least one maneuver to be avoided;

determining the preferred route from the origin to the destination, with the preferred route not including the at least one maneuver indicated by the received user-selected indication and not including the at least one feature indicated by the received user-selected indication;

enabling a user to view the first route and the first preferred route; and

receiving an indication, from the user, of a selected route wherein the selected route is on of the first route or the first preferred route.

82. An apparatus for determining a preferred route, the apparatus being configured to;

access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, each link representing a road and each node representing and intersection that includes at least one road;

receive a user-selected indication of at least one feature to be avoided;

determine a first preferred route from the origin to the destination, with the first preferred route not including the at least one feature indicated by the recieved user-selected indication;

associated the user-selected indication if the at least one feature to be avoided with a user identity; and

store both the user-selected indication of the at least one feature to be avoided and the association of the user-selected indication and the user identify for later use in determining a second preferred route from a second origin to a second destination, with the second preferred route not including the at least one feature indicated by the stored user-selected indication of the at least one feature to be avoided, in response to a request received from the user identity,

wherein a feature to be avoided comprises a type of terrain over which the route passes.

83. The apparatus of claim 82 wherein the type of terrain comprises mountainous terrain.

84. The apparatus of claim 82 further configured to:

determined a first route from the origin to the destination, the first route including maneuvers;

receive a user-selected indication of at least one maneuver to be avoided;

determine the preferred route from the origin to the destination, with the preferred route not including the at least one maneuver indicated by the received user-selected indication and not including the at least one feature indicated by the received user-selected indication;

enable a user to view the first route and the first preferred route; and

receiving and indication, from the user, of a selected route wherein the selected route is one of the forst route or the first preferred route.