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

• US 9,008,960 B2
• Filed: 06/19/2013
• Issued: 04/14/2015
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Horvitz, Eric J.
• Primary Examiner(s): Diacou, Ari M
• Application Number:
  US13/922,002
• Publication Number:
  US 20130345966A1
• Time in Patent Office: 664 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. A system, comprising:

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

an analysis component configured to identify a journey between the origination and destination points in response to the request, the analysis component configured to predict one or more characteristics of traffic flow at one or more road segments at one or more future times to calculate one or more estimated times corresponding to the identified journey, including being configured to predict a future time at which a road segment of the one or more road segments will be jammed;

the analysis component configured to provide the identified journey and an estimated time for undertaking the identified journey to the user, the estimated time for undertaking the identified journey selected by the analysis component to enable the user to avoid the road segment when jammed.

2. The system of claim 1, wherein the analysis component is further configured to predict a future time at which the road segment is likely to open after being predicted to be jammed.

3. The system of claim 1, wherein the analysis component is further configured to determine a time to begin the identified journey that results in a least amount of travel time for the identified journey.

4. The system of claim 1, wherein the analysis component is further configured to determine a probability for the estimated time for undertaking the identified journey.

5. The system of claim 1, wherein the analysis component is further 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 estimated times corresponding to the plurality of candidate journeys, an estimated time 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 estimated times.

6. The system of claim 1, wherein the analysis component is further configured to access a traffic system representation to calculate the estimated time, 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, and each edge of the weighted graph representing a corresponding road segment.

7. A client device, comprising:

at least one processor; and

a user interface supported by the at least one processor that is configured to enable a user to submit a request for directions between an origination point and a destination point;

the user interface configured to, in response to the request, output a journey identified between the origination and destination points and an estimated time for undertaking the identified journey, the identified journey taking into account a probability of a road segment of the identified journey being open, after being in a jammed state, at an expected time to be reached by the user.

8. The client device of claim 7, wherein the user interface is further configured to provide an indication of whether the road segment is open or jammed to the user.

9. The client device of claim 7, wherein the user interface is further configured to indicate a time to begin the journey that results in a least amount of travel time for the journey.

10. The client device of claim 7, wherein the client device is configured to transmit the request to a server, and to receive the identified journey from the server in response to the transmitted request.

11. The client device of claim 7, further comprising:

an analysis component configured to identify the journey between the origination and destination points in response to the request, the analysis component configured to predict one or more characteristics of traffic flow at one or more road segments at one or more future times to calculate one or more estimated times corresponding to the identified journey, including being configured to predict a future time at which a road segment of the one or more road segments will be jammed.

12. The client device of claim 11, further comprising:

storage that stores a traffic system representation accessible by the analysis component to calculate the one or more estimated times, 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, and each edge of the weighted graph representing a corresponding road segment.

13. The client device of claim 11, wherein the analysis component is further configured to determine a probability for the estimated time for undertaking the identified journey.

14. The client device of claim 7, further comprising:

a sensor configured to determine a location of the user; and

the graphical user interface configured to indicate the determined location of the user with respect to the identified journey.

15. A computer 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 submitted by a user;

identifying a journey between the origination and destination points in response to the request at least by predicting one or more characteristics of traffic flow at one or more road segments at one or more future times to calculate one or more estimated times corresponding to the identified journey, including predicting a future time at which a road segment of the one or more road segments will open from being jammed; and

providing the identified journey and an estimated time for undertaking the identified journey to the user.

16. The computer storage medium of claim 15, wherein said identifying a journey further comprises:

determining a probability for each of the one or more road segments of being jammed when expected to be reached by the user to determine a plurality of probabilities; and

considering the plurality of probabilities in selecting the identified journey and calculating the estimated time for undertaking the identified journey.

17. The computer storage medium of claim 15, the method further comprising:

determining a time to begin the identified journey that results in a least amount of travel time for the identified journey.

18. The computer storage medium of claim 15, the method further comprising:

determining a probability for the estimated time for undertaking the identified journey.

19. The computer storage medium of claim 15, wherein said identifying a journey further comprises:

identifying, 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,

calculating a plurality of estimated times corresponding to the plurality of candidate journeys, an estimated time 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 estimated times.

20. The computer storage medium of claim 15, further comprising:

accessing a traffic system representation to calculate the estimated time, 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, and each edge of the weighted graph representing a corresponding road segment.