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

• US 7,739,040 B2
• Filed: 06/30/2006
• Issued: 06/15/2010
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J.
• Primary Examiner(s): Bolda; Eric
• Assistant Examiner(s): Diacou; Ari M
• Application Number:
  US11/428,216
• Publication Number:
  US 20080004794A1
• Time in Patent Office: 1,446 Days
• Field of Search: 701/204, 701/209, 701/210
• US Class Current: 701/210
• 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 route planning system comprising a computer storage medium encoded with the following computer-executable components:

a receiver component that, when executed, receives a request for directions for a journey between a beginning point and a destination point;

an analysis component that, when executed;

searches for routes between the beginning point and the destination point and identifies a plurality of options, each option comprising a candidate route between the beginning point and the destination point and a journey start time, the analysis component computing an estimated travel time associated with each of the plurality of options based at least in part upon contextual information; and

outputs two or more selected options of the plurality of options, the selected options being determined as a function of expected cost incurred by the user with respect to at least one of time before a start of the journey and time after arrival at the destination point for each of the plurality of options.

2. The route planning system of claim 1, the analysis component considers one or more times to start the journey and predicts times when the user is expected to reach different portions of a route when identifying the plurality of options.

3. The route planning system of claim 1, the analysis component searches over a plurality of possible journey start times in connection with identifying the plurality of options.

4. The route planning system of claim 1, wherein the expected cost is a function of at least one of expected time of arriving before a target arrival time, and expected time of arriving after a target arrival time.

5. The route planning system of claim 4, wherein the analysis component determines the expected cost through receipt of user preferences regarding time of travel and departure time.

6. The route planning system of claim 1, wherein the analysis component comprises a portion of an alarm system, the alarm system alerting a driver as to one or more journey start times.

7. The route planning system of claim 1, the analysis component considers probability distributions over flows for road segments when identifying the one or more candidate routes and the one or more journey start times of the plurality of options, wherein the distributions are a function of contextual observations that include at least one of time of day, day of week, calendar information, flows seen at earlier times, and flows in other parts of a traffic system.

8. The route planning system of claim 7, wherein:

the analysis component predicts future of traffic flows for road segments at times that the user is predicted to reach the road segments, and

directions are output to the user based at least in part upon the predictions.

9. The route planning system of claim 1, wherein the analysis component is disposed within a portable device.

10. The route planning system of claim 1, further comprising a profile matching component that assigns a driving profile to an initiator of the request, the analysis component determines the expected cost incurred by the user with respect to the one or more candidate routes and the one or more journey start times based at least in part upon the assigned driving profile.

11. The system of claim 1, wherein the receiver component receives multiple intermediate points in addition to the beginning point and the destination point, the analysis component determines expected amounts of travel times with respect to traveling from the beginning point to the multiple intermediate points to the destination point for multiple contexts.

12. The system of claim 11, further comprising a dialog component that requests time-related information from an initiator of the request with respect to the multiple intermediate points.

13. The system of claim 1, wherein the analysis component utilizes at least one of a Dykstra search algorithm, an A* search algorithm, a variant of a Dykstra search algorithm, and a variant of an A* search algorithm in connection with identifying the one or more candidate routes and the one or more journey start times between the beginning point and the destination point.

14. A route planning system, comprising:

computer-implemented means for receiving a request for directions between a beginning point and a destination point; and

computer-implemented means for;

determining a plurality of options, each option comprising a candidate route between the beginning point and the destination point and a candidate journey start time,

computing an estimated travel time for each of the plurality of options, and

providing one or more of the plurality of options based on evaluation of a utility of the option, the utility being evaluated based on one or more of an expected cost of a journey over the candidate route to a user given the candidate journey start time of the option and an expected utility of the journey over the candidate route to the user given the journey start time, the utility being based on value to the user of at least one of time before the candidate journey start time and time after arrival at the destination,

wherein the expected cost is determined based on user preferences regarding time of travel and departure time.

15. A computer storage medium encoded with computer-executable components that, when executed, implement a method of operating a route planning system, the method comprising:

receiving from a user a request for directions between a beginning point and a destination point;

associating a driving profile with the user;

searching for routes between the beginning point and the destination point;

identifying a plurality of options, each option comprising a candidate route between the beginning point and the destination point and a journey start time for the candidate route; and

providing one or more options to the user, the provided options being selected based at least in part upon an estimated utility metric associated with the user and the one or more selected options, the utility metric being based on value to the user of at least one of time before the candidate journey start time and time after arrival at the destinations,

wherein the estimated utility metric associated with the user with respect to the one or more options and the one or more journey start times is based at least in part upon the driving profile associated with the user.

16. The computer storage medium of claim 15, wherein

searching for routes comprises:

analyzing at least one of the sensed and inferred contextual information;

predicting traffic flows at road segments at future times based at least in part upon the analysis; and

outputting the one or more routes based at least in part upon the predicted traffic flows.

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

analyzing driving preferences associated with the user; and

determining the estimated utility metric based at least in part upon the driving preferences.

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

determining an expected cost of a journey; and

outputting a route and a journey start time between the beginning point and the destination point based at least in part upon the expected cost.

19. The computer storage medium of claim 15, wherein the method further comprises:

recommending to the user to perform another task prior to one of beginning a journey and continuing a journey.

20. The computer storage medium of claim 15, wherein the method further comprises:

alerting the user when to begin travel between the beginning point and the destination point given one or more of observed and predicted traffic flows.

21. A route planning system comprising a computer storage medium encoded with the following computer-executable components:

a receiver component that, when executed, receives a request for directions for a journey between a beginning point and a destination point;

an analysis component that, when executed;

searches for routes between the beginning point and the destination point and identifies a plurality of options, each option comprising a candidate route between the beginning point and the destination point and a journey start time, the analysis component computing an estimated travel time associated with each of the plurality of options based at least in part upon contextual information; and

outputs one or more selected options of the plurality of options, the selected options being determined as a function of expected cost incurred by the user with respect to at least one of time before a start of the journey and time after arrival at the destination point for each of the plurality of options,

wherein the expected cost is a function of at least expected time of arriving before a target arrival time.