COMPUTATION OF TRAVEL ROUTES, DURATIONS, AND PLANS OVER MULTIPLE CONTEXTS

• US 20080004794A1
• Filed: 06/30/2006
• Published: 01/03/2008
• 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.
• Granted Patent: US 7,739,040 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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 the following computer-executable components:

a receiver component that receives a request for directions between a beginning point and a destination point; and

an analysis component that searches for routes between the beginning point and the destination point and identifies one or more candidate routes and one or more journey start times between the beginning point and the destination point based at least in part upon contextual information, the one or more output candidate routes and the one or more journey start times are determined as a function of at least one of expected utility to a user and expected cost incurred by the user with respect to the one or more candidate routes and the one or more journey start times.

2. The route planning system of claim 1, the analysis component considers the 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 one or more candidate routes and the one or more times to start the journey.

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 one or more candidate routes and the one or more journey start times.

4. The route planning system of claim 1, the expected utility is a function of at least one of time available before departing on a journey, 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, the analysis component determines the expected utility through receipt of user preferences regarding time of travel and departure time.

6. The route planning system of claim 1, an alarm system comprises the analysis component, the alarm system alerts 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, 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, the analysis component predicts future of traffic flows for road segments at times that the user is predicted to reach the road segments, directions are output to the user based at least in part upon the predictions.

9. The route planning system of claim 1, a portable device comprises the analysis component.

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 at least one of the expected utility to the user and 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, 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, 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 methodology for determining identifying a route for travel, comprising:

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

searching for routes between the beginning point and the destination point based at least in part upon at least one of sensed and inferred contextual information;

identifying at least one of a plurality of candidate routes between the beginning point and the destination point and a plurality of journey start times for a candidate route based at least in part upon the search; and

selecting one or more routes to provide to a user that requests the directions based at least in part upon an estimated utility metric associated with the user requesting the directions and the at least one of a plurality of candidate routes between the beginning point and the destination point and the plurality of journey start times for the candidate route.

15. The methodology of claim 14, further comprising:

analyzing the 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.

16. The methodology of claim 14, further comprising:

analyzing driving preferences associated with the user; and

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

17. The methodology of claim 14, further comprising:

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.

18. The methodology of claim 14, further comprising recommending to the user to perform another task prior to one of beginning a journey and continuing a journey.

19. The methodology of claim 14, further comprising alerting the initiator of the request with respect to when to begin travel between the beginning point and the destination point given one or more of observed and predicted traffic flows.

20. 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 candidate route between the beginning point and the destination point and a candidate journey start time based at least in part upon contextual information and one or more of an expected cost of a journey over the candidate route to a user given the candidate journey start time and an expected utility of the journey over the candidate route to the user given the journey start time.