COLLABORATIVE ROUTE PLANNING FOR GENERATING PERSONALIZED AND CONTEXT-SENSITIVE ROUTING RECOMMENDATIONS

• US 20070299599A1
• Filed: 06/27/2006
• Published: 12/27/2007
• Est. Priority Date: 06/27/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J., Krumm, John C., Letchner, Julia M.
• Granted Patent: US 7,610,151 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

A route-planning system is described that leverages a database of observations about routes taken by drivers in a region to generate context and/or preference sensitive routes. Contextual information such as time of day and day of week, along with such findings as the observed velocities on different roads and the efficiency of trips is noted from the database of trips to inform a route generation component. The route-generation component considers velocities, contextual information, and other findings to compute preferred routes for people requesting directions from a first geographical point to a second geographical point. In one usage, properties of a driver'"'"'s own prior routes are used to generate personalized routes, including routes between previously unobserved starting and ending locations. In another application, sets of observed routes of other drivers are used in a collaborative manner to generate recommended routes for a specific driver based on inferred preferences of the driver.

Claims

1. A route planning system comprising the following computer-executable components:

a receiver component that receives a request for directions from a first geographical point to a second geographical point; and

a context analyzer component that analyzes contextual data associated with the received request, the route planning system outputs directions between the first and second geographical points based at least in part upon the received request and the analyzed contextual data.

2. The route planning system of claim 1, further comprising a route planning model that includes a weighted graph that is representative of a traffic system, weights within the weighted graph are based at least in part upon one or more of the analyzed contextual data and user preferences.

3. The route planning system of claim 2, weights of the weighted graph are assigned based at least in part upon data collected from multiple drivers traversing through a road system, the directions between the first and second geographical points are output as a function of user preferences that are inferred through analysis of the collected data.

4. The route planning system of claim 2, the user preferences are explicitly provided to the route planning system.

5. The route planning system of claim 2, further comprising a monitoring component that monitors user activity, the user preferences are inferred based at least in part upon the monitored user activity.

6. The route planning system of claim 2, further comprising an updating component that receives data relating to roadways represented by the route planning model and alters weights of the graph based at least in part upon the received data.

7. 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 route planning system outputs directions between the first and second geographical points based at least in part upon the received request, the analyzed contextual data, and the assigned profile.

8. The route planning system of claim 1, further comprising a data collection component that receives data from one or more external data sources, the route planning system outputs directions between the first and second geographical points based at least in part upon the received request, the analyzed contextual data, and data received from the one or more external data sources.

9. The route planning system of claim 8, the external data sources are one or more of a calendar application, a website, a radio station, sensors configured to monitor traffic flow, and a television station.

10. The route planning system of claim 1, an automobile comprises the receiver component and the context analyzer component.

11. The route planning system of claim 1, a server comprises the receiver component and the context analyzer component.

12. The route planning system of claim 1, further comprising a route planning model that models a traffic system related to the request, the route planning model includes a weighted graph, where nodes of the graph represent intersections and edges represent road segments, weights associated with the nodes and edges alter as context changes.

13. A methodology for outputting directions between two geographic points comprising the following computer-executable acts:

receiving a request for driving directions from a first geographic point to a second geographic point;

determining contextual data associated with the request, the contextual data includes a time of day that an initiator of the request will be traveling from the first geographic point to the second geographic point; and

creating driving directions from the first geographic point to the second geographic point based at least in part on the time of day.

14. The methodology of claim 13, further comprising:

analyzing user-centric data associated with the initiator of the request;

assigning a driving profile to the initiator of the request; and

creating the driving directions from the first geographic point to the second geographic point based at least in part on the time of day and the assigned driving profile.

15. The methodology of claim 13, the contextual data includes a day of a week that the initiator of the request will be traveling from the first geographic point to the second geographic point, the driving directions are created based at least in part upon the day of the week that the initiator of the request will be traveling from the first geographic point to the second geographic point.

16. The method of claim 13, further comprising:

inferring demographic information associated with the initiator of the request; and

creating the driving directions based at least in part upon the inferred demographic information.

17. The method of claim 13, further comprising:

receiving trace logs with a respect to a plurality of drivers;

segmenting the trace logs to represent individual journeys of the drivers; and

creating the driving directions based at least in part upon the individual journeys of the drivers.

18. The method of claim 17, further comprising:

categorizing the segmented trace logs based upon context associated with the trace logs; and

creating the driving directions based at least in part upon the categorization.

19. A route planning system comprising the following computer-executable components:

means for receiving a request for driving directions between two geographic points;

means for determining contextual information associated with the request;

means for assigning a driving profile to an initiator of the request; and

means for creating driving directions between the two geographic points based at least in part upon the request, the contextual information, and the assigned driving profile.

20. The route planning system of claim 19, further comprising:

means for receiving data from a plurality of automobiles as they travel through a traffic system; and

means for leveraging the received information to create the driving directions for a user.