Computation of travel routes, durations, and plans over multiple contexts

• US 8,473,197 B2
• Filed: 12/15/2011
• Issued: 06/25/2013
• Est. Priority Date: 06/30/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J.
• Primary Examiner(s): Hellner, Mark
• Assistant Examiner(s): Diacou, Ari M
• Application Number:
  US13/327,653
• Publication Number:
  US 20120089322A1
• Time in Patent Office: 558 Days
• Field of Search: 701414-416, 701/423, 701/453
• US Class Current: 701/423
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement

Abstract

A route planning system comprises a receiver component that receives a request for directions between a beginning point and a destination point. An analysis component analyzes a traffic system representation that varies as context varies and outputs expected amounts of travel time between the beginning point and the destination point for multiple contexts based at least in part upon the analysis. A method is described herein that includes techniques for searching over routes and trip start times simultaneously so as to identity start times and routes associated with maximal expected value, or equivalently minimum expected cost, given preferences encoded about one or more of the leaving time, the travel time, and the arrival time.

Claims

1. An apparatus for providing a travel route, comprising:

a processor; and

a memory communicatively coupled to the processor, the memory having stored therein computer-executable instructions configured to implement components comprising;

a receiver component configured to receive a request for directions between an origination point and a destination point; and

an analysis component configured to identify a journey between the origination and destination points, the journey comprising a route and a start time of travel along the route, the analysis component configured to;

identify, by a search, a plurality of candidate journeys between the origination point and the destination point, the search being based at least in part on contextual information,

calculate a plurality of expected durations corresponding to the plurality of candidate journeys, an expected duration of a candidate journey depending on a route of the journey, on a start time of the journey, and on at least a portion of the contextual information, and

select the journey from the plurality of candidate journeys based on the plurality of expected durations;

the analysis component at least configured to predict one or more characteristics of traffic flow at one or more road segments at one or more future times based at least in part on the contextual information to calculate the plurality of expected durations, including being configured to predict a time at which traffic flow on a road segment will return to a free-flowing state after being in a jammed state.

2. The apparatus of claim 1, wherein the contextual information comprises at least one of a sensed traffic flow or a predicted traffic flow along a road segment.

3. The apparatus of claim 1, wherein the contextual information comprises traffic information obtained from a plurality of sensors associated with a plurality of road segments.

4. The apparatus of claim 1, wherein the contextual information comprises information obtained from a plurality of sensors associated with a plurality of automobiles.

5. The apparatus of claim 4, wherein the information obtained from the plurality of sensors associated with the plurality of automobiles comprises at least one of location information and velocity information.

6. The apparatus of claim 1, wherein the analysis component accesses a traffic system representation at least to calculate the expected durations, the traffic system representation having the form of a weighted graph that includes a plurality of nodes, edges, and weights, each edge having a corresponding weight and each node having a corresponding weight, each node of the weighted graph representing an intersection, each edge of the weighted graph representing a corresponding road segment, and each weight of the weighted graph representing an average travel speed.

7. The apparatus of claim 6, wherein the analysis component is configured to alter the weights of the weighted graph based on the contextual information, and to determine a route between the origination point and the destination point having a lowest total weight in the weighted graph.

8. A computer-readable storage medium comprising computer-executable instructions that, when executed by a processor, perform a method comprising:

receiving a request for directions between an origination point and a destination point; and

identifying a journey between the origination and destination points, the journey comprising a route and a start time of travel along the route, said identifying the journey comprising;

identifying, by searching, a plurality of candidate journeys between the origination point and the destination point, the searching being based at least in part on contextual information,

calculating a plurality of expected durations corresponding to the plurality of candidate journeys, an expected duration of a candidate journey depending on a route of the journey, on a start time of the journey, and on at least a portion of the contextual information, and

selecting the journey from the plurality of candidate journeys based on the plurality of expected durations;

said calculating comprises predicting one or more characteristics of traffic flow at one or more road segments at one or more future times based at least in part on the contextual information, and said predicting comprises predicting a time at which traffic flow on a road segment will return to a free-flowing state after being in a jammed state.

9. The computer-readable storage medium of claim 8, wherein the contextual information comprises at least one of a sensed traffic flow or a predicted traffic flow along a road segment.

10. The computer-readable storage medium of claim 8, wherein the contextual information comprises traffic information obtained from a plurality of sensors associated with a plurality of road segments.

11. The computer-readable storage medium of claim 8, wherein the contextual information comprises information obtained from a plurality of sensors associated with a plurality of automobiles.

12. The computer-readable storage medium of claim 11, wherein the information obtained from the plurality of sensors associated with the plurality of automobiles comprises at least one of location information and velocity information.

13. The computer-readable storage medium of claim 8, wherein said calculating a plurality of expected durations comprises:

accessing a traffic system representation at least to calculate the expected durations, the traffic system representation having the form of a weighted graph that includes a plurality of nodes, edges, and weights, each edge having a corresponding weight and each node having a corresponding weight, each node of the weighted graph representing an intersection, each edge of the weighted graph representing a corresponding road segment, and each weight of the weighted graph representing an average travel speed.

14. The computer-readable storage medium of claim 13, wherein said calculating a plurality of expected durations further comprises:

altering the weights of the weighted graph based on the contextual information; and

determining a route between the origination point and the destination point having a lowest total weight in the weighted graph.

15. A computer-implemented method, comprising:

receiving a request for directions between an origination point and a destination point; and

identifying a journey between the origination and destination points, the journey comprising a route and a start time of travel along the route, said identifying the journey comprising;

identifying, by searching, a plurality of candidate journeys between the origination point and the destination point, the searching being based at least in part on contextual information,

calculating a plurality of expected durations corresponding to the plurality of candidate journeys, an expected duration of a candidate journey depending on a route of the journey, on a start time of the journey, and on at least a portion of the contextual information, and

selecting the journey from the plurality of candidate journeys based on the plurality of expected durations;

said calculating comprises predicting one or more characteristics of traffic flow at one or more road segments at one or more future times based at least in part on the contextual information, and said predicting comprises predicting a time at which traffic flow on a road segment will return to a free-flowing state after being in a jammed state.

16. The method of claim 15, wherein the contextual information comprises at least one of a sensed traffic flow or a predicted traffic flow along a road segment.

17. The method of claim 15, wherein the contextual information comprises at least one of:

traffic information obtained from a plurality of sensors associated with a plurality of road segments, or

information obtained from a plurality of sensors associated with a plurality of automobiles.

18. The method of claim 17, wherein the information obtained from the plurality of sensors associated with the plurality of automobiles comprises at least one of location information and velocity information.

19. The method of claim 15, wherein said calculating a plurality of expected durations comprises:

accessing a traffic system representation at least to calculate the expected durations, the traffic system representation having the form of a weighted graph that includes a plurality of nodes, edges, and weights, each edge having a corresponding weight and each node having a corresponding weight, each node of the weighted graph representing an intersection, each edge of the weighted graph representing a corresponding road segment, and each weight of the weighted graph representing an average travel speed.

20. The method of claim 19, wherein said calculating a plurality of expected durations further comprises:

altering the weights of the weighted graph based on the contextual information; and

determining a route between the origination point and the destination point having a lowest total weight in the weighted graph.