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

• US 20100185388A1
• Filed: 01/22/2010
• Published: 07/22/2010
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Eric J Horvitz
• Inventors: Horvitz, Eric J.
• Granted Patent: US 8,090,530 B2
• Time in Patent Office: Days
• US Class Current: 701/204
• 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 method of identifying a route for travel, the method comprising:

with at least one processor;

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

accessing user preferences for the user, the user preferences comprising preferences about at least one of a start time, an arrival time and a probability of arriving within a time window;

searching for at least one candidate route between the beginning point and the destination point, the searching being based at least in part upon at least one of sensed and inferred contextual information, each of the at least one candidate routes having a start time associated therewith; and

selecting at least one of the at least one candidate routes to provide to the user, the selected at least one of the at least one candidate routes being selected based at least in part upon the user preferences.

2. The method of claim 1, 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.

3. The methodology of claim 1, wherein:

the method further comprises computing, for each of the at least one candidate routes, a value of an estimated utility metric based on the user preferences; and

selecting at least one of the at least one candidate routes comprises selecting based on the values of the estimated utility metrics computed for each of the at least one candidate routes.

4. The method of claim 1, 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.

5. The method of claim 1, further comprising recommending to the user to perform another task prior to one of beginning a journey and continuing a journey.

6. The method of claim 1, wherein:

the at least one of sensed and inferred contextual information comprises one or more of observed and predicted traffic flows; and

the method further comprises alerting the user with respect to when to begin travel between the beginning point and the destination point based on the start time associated with the selected at least one of the at least one candidate routes.

7. The method of claim 6, wherein the alerting comprises triggering an alarm clock to generate an alarm at a time based on the start time associated with the selected at least one of the at least one candidate routes.

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

receiving a request for directions for a journey, the journey comprising visits at each of a plurality of destination points;

accessing timing information associated with at least a portion of the plurality of destination points;

searching for at least one candidate route passing through each of the plurality of destination points, the searching being based at least in part upon at least one of sensed and inferred contextual information, each of the at least one candidate routes having a start time associated therewith; and

selecting at least one of the at least one candidate routes to provide to the user, the selecting comprising selecting based at least in part upon the timing information.

9. The computer-readable medium of claim 8, wherein the timing information comprises hours of operation of a business at a destination point of the plurality of destination points.

10. The computer-readable medium of claim 9, wherein accessing timing information related to hours of operation of the business comprises accessing the timing information over the Internet.

11. The computer-readable medium of claim 8, wherein the timing information comprises user input indicating an expected duration of a stop at least one of the plurality of destination points.

12. The computer-readable medium of claim 8, wherein searching for at least one candidate route passing through each of the plurality of destination points comprises computing a plurality of candidate routes based on traffic information and time of day.

13. The computer-readable medium of claim 8, further comprising providing to the user the selected at least one of the at least one candidate routes by presenting an order in which the plurality of destination points are to be visited.

14. The computer-readable medium of claim 8, wherein:

selecting at least one of the at least one candidate routes to provide to the user comprises selecting a plurality of candidate routes; and

the method further comprises presenting the plurality of selected candidate routes to the user by presenting each of the plurality of candidate routes in connection with a start time and an expected duration.

15. The computer-readable medium of claim 8, wherein

selecting at least one of the at least one candidate routes to provide to the user comprises selecting based on a probability of arriving at a destination of the plurality of destinations at a time being consistent with the timing information.

16. A method of operating a system that provides a route for travel, the method comprising:

with at least one processor;

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

receiving user inputs, the user inputs indicating a preference of a user of arriving at a destination before a target arrival time or a preference of the user of arriving at a destination after a target arrival time;

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

selecting at least one of the at least one candidate routes to provide to the user, the selected at least one of the at least one candidate routes being selected based at least in part upon the user inputs.

17. The method of claim 16, wherein:

the method further comprises;

receiving an input indicating a target arrival time;

accessing historical data; and

based at least in part on the historical data, computing for each of the plurality of candidate routes, a scheduled time of arrival and a probability of arrival by the scheduled arrival time; and

selecting each of the at least one of the at least one candidate routes comprises selecting a candidate route based at least in part on the candidate route having a scheduled arrival time and a probability of arrival by the scheduled arrival time consistent with the user inputs.

18. The method of claim 17, wherein receiving user inputs comprises receiving user inputs describing a preference for time available before a start of a meeting or appointment.

19. The method of claim 17, wherein receiving user inputs comprises receiving user inputs describing a cost to the user of arrival at times relative to a start of a meeting or appointment.

20. The method of claim 17, wherein receiving user inputs comprises receiving user inputs indicating a minimum probability of arriving at a specified time.