Collaborative route planning for generating personalized and context-sensitive routing recommendations

• US 8,718,925 B2
• Filed: 05/14/2009
• Issued: 05/06/2014
• Est. Priority Date: 06/27/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Letchner, Julia M., Krumm, John C., Horvitz, Eric J.
• Primary Examiner(s): Hellner, Mark
• Application Number:
  US12/466,308
• Publication Number:
  US 20090271104A1
• Time in Patent Office: 1,818 Days
• Field of Search: 701/209, 701/207, 701/410, 701/424, 701/425, 340/990
• US Class Current: 701/410
• 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:

a processor;

a memory communicatively coupled to the processor, the memory having stored therein computer-executable instructions configured to implement the route planning system including;

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

a profile component that analyzes user-centric data and infers user preferences for directions based on the user-centric data by selecting a profile from a data repository based at least in part on the user-centric data indicating a correspondence between characteristics of the user and characteristics associated with the selected profile; and

a route planner that outputs directions between the first and second geographical points based at least in part upon the received request and the inferred user preferences.

2. The route planning system of claim 1, wherein the user-centric data comprises demographic data of a user initiating the request.

3. The route planning system of claim 2, wherein the demographic data comprises a history of web sites visited by the user.

4. The route planning system of claim 3, wherein the processor comprises a server accessible by the user via a network.

5. The route planning system of claim 3, wherein the route planner selectively outputs directions that avoid areas of high traffic congestion based on the demographic data.

6. The route planning system of claim 1, wherein the user-centric data comprises data from a user calendar.

7. The route planning system of claim 1, wherein the user-centric data comprises historical driving activity of a user initiating the request, the historical driving activity being selected to represent driving on routes familiar to the user.

8. The route planning system of claim 7, further comprising a monitoring component that monitors user activity, the monitoring component recording a trace log comprising data indicative of the historical driving activity.

9. The route planning system of claim 8, further comprising a segmentation component, the segmentation component identifying in the trace log events associated with a start and a stop for each of a plurality of individual journey.

10. The route planning system of claim 8, further comprising a profiling component that determines an inefficiency parameter associated with a driver, the inefficiency parameter indicating an average over each of the plurality of individual journeys, of a ratio between a duration of a fasted fastest expected route and a time spent by the driver on the journey.

11. The route planning system of claim 10, wherein:

the route planner models a traffic system related to the request, the route planner generates the directions using a weighted graph, where nodes of the graph represent intersections and edges represent road segments; and

weights associated with the nodes and edges are based at least in part on the inefficiency parameter for a driver associated with the request.

12. The route planning system of claim 1, wherein the user-centric data comprises an indication of driving experience.

13. The route planning system of claim 1, wherein the processor and memory are mounted within an automobile.

14. A method for operating a route planning system to output outputting directions between two geographic points comprising the following computer-executed acts:

with at least one processor;

tracking historical activity of a driver relating to access of electronic information outside the route planning system;

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

inferring user preferences based at least in part on the historical activity; and

creating driving directions from the first geographic point to the second geographic point based at least in part on the inferred user preferences.

15. The method of claim 14, wherein:

the method further comprises determining contextual data associated with the request; and

creating the driving directions comprises creating the driving directions based at least in part on the inferred user preferences and the contextual data.

16. The method of claim 14, wherein:

inferring user preferences further comprises inferring user preferences based at least in part on the historical driving activity comprises analyzing a log of driver activity, the analyzing comprising identifying in the log segments associated with individual journeys and analyzing characteristics of the individual journeys.

17. The method of claim 14, wherein:

the driver comprises a first driver;

the request comprises a first request;

the driving directions comprise first driving directions, the first driving directions indicating a first route between the first geographic point to the second geographic point; and

the method further comprises;

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

creating second driving directions for driving directions from the first geographic point to the second geographic point, the second driving directions indicating a second route between the first geographic point to the second geographic point.

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

tracking historical driving activity of a driver;

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

inferring user preferences based at least in part on the historical driving activity, the inferred user preferences being based on determined characteristics of a plurality of journeys, the determined characteristics of each of the journeys comprising an efficiency factor representing a comparison of an efficient route for the journey and actual driver behavior; and

creating driving directions from the first geographic point to the second geographic point based at least in part on the inferred user preferences.

19. The at least one computer storage medium of claim 18, wherein:

tracking historical driving activity of the driver includes;

analyzing trace logs with respect to the driver to identify indications of ends of individual journeys for the driver, each indication being based upon the driver'"'"'s automobile having stopped moving for a threshold amount of time;

segmenting the trace logs to represent the plurality of journeys; and

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

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

20. The at least one computer storage medium of claim 18, wherein:

inferring user preferences further comprises inferring user preferences for directions based on at least one of demographic data of a user initiating the request and data from a user calendar.