Generating personalized routes with route deviation information

• US 10,274,328 B2
• Filed: 08/22/2016
• Issued: 04/30/2019
• Est. Priority Date: 08/22/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Grochocki, Jr., David, Salowitz, Elizabeth, Diaz, Ana Lilia Otero, Sethi, Kshitij, Mehta, Kshitij, West, Jeff
• Primary Examiner(s): Antonucci, Anne M
• Application Number:
  US15/243,631
• Publication Number:
  US 20180051997A1
• Time in Patent Office: 981 Days
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• 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/3676 Overview of the route on the road map

Abstract

A navigation device may include one or more input devices, a processor, and one or more output devices. A navigation device may read stored map information and stored route deviation information including one or more deviation segments having a divergence location, a deviation path, a reconvergence location, and deviation segment data. The processor of the navigation device may then generate a route and route data. Upon determining that each of the one or more deviation segments intersects the route and a predetermined subset of the deviation segment data matches a corresponding subset of the route data, the navigation device may generate a personalized route by replacing a route portion between a first intersection point and a last intersection point with a corresponding deviation portion for each intersecting deviation segment. The one or more output devices may then output the route and the one or more personalized routes.

Claims

1. A navigation device, comprising:

one or more input devices configured to receive a starting location and an ending location;

a processor configured to;

receive a user profile including route deviation information corresponding to a user, map information, and peer-generated route deviation information generated by a plurality of peer navigation devices;

generate a route with route data based at least on the map information, the starting location, and the ending location;

based on the route deviation information corresponding to the user, identify one or more travel patterns of the user;

identify a subset of the peer-generated route deviation information that is relevant to the one or more travel patterns of the user, the subset of the peer-generated route deviation information including one or more deviation segments and deviation segment data;

determine if the one or more deviation segments intersect the route at a plurality of intersection points including a divergence location and a reconvergence location, and if a predetermined subset of the deviation segment data matches a corresponding subset of the route data; and

upon determination that the one or more deviation segments intersect the route at the plurality of intersection points and the predetermined subset of the deviation segment data matches the corresponding subset of the route data, generate one or more alternative routes for the user by replacing a route portion between a first intersection point and a last intersection point of the plurality of intersection points with a corresponding deviation portion for each intersecting deviation segment; and

one or more output devices configured to output the route and the one or more alternative routes generated for the user.

2. The navigation device of claim 1, wherein the one or more input devices are further configured to receive user preferences from the user, and wherein the user preferences comprise at least an option to select the predetermined subset of the deviation segment data.

3. The navigation device of claim 1, wherein the deviation segment data includes information about each deviation segment and a context in which the deviation segment is used.

4. The navigation device of claim 1, wherein the one or more deviation segments include a deviation path, and wherein the deviation path extends between the divergence location and the reconvergence location.

5. The navigation device of claim 4, wherein the deviation path extends between the divergence location and the reconvergence location and a predetermined distance in a plurality of directions from one or both of the divergence location and the reconvergence location.

6. The navigation device of claim 1, further comprising one or more location sensors from which the navigation device determines at least a travel path of the one or more location sensors.

7. The navigation device of claim 6, wherein the processor is further configured to:

determine if the travel path deviates from the one or more alternative routes;

upon determining that the travel path deviates from the one or more alternative routes, update the route deviation information corresponding to the user.

8. The navigation device of claim 1, wherein the route deviation information corresponding to the user is generated by the navigation device at a time prior to identifying the one or more travel patterns of the user.

9. The navigation device of claim 1, wherein the one or more input devices are further configured to receive user preferences, the user preferences comprising at least an option to receive the peer-generated route deviation information from one or more predetermined groups.

10. The navigation device of claim 1, wherein one or more output devices are further configured to output the one or more alternative routes generated for the user with an indication that the one or more alternative routes generated for the user are different from the route.

11. A method implemented at least in part by a navigation device, the method comprising:

receiving a request to generate a route from a starting location to an ending location;

receive a user profile including route deviation information corresponding to a user, map information, and peer-generated route deviation information generated by a plurality of peer navigation devices;

receiving user preferences from the user, the user preferences comprising at least an option to share the route deviation information corresponding to the user with one or more predetermined groups of other users to generate one or more personalized routes for those other users;

generating the route with route data based at least on the map information, the starting location, and the ending location;

based on the route deviation information corresponding to the user, identifying one or more travel patterns of the user;

identifying a subset of the peer-generated route deviation information that is relevant to the one or more travel patterns of the user, the subset of the peer-generated route deviation information including one or more deviation segments and deviation segment data;

determining if the one or more deviation segments intersect the route at a plurality of intersection points including a divergence location and a reconvergence location, and if a predetermined subset of the deviation segment data matches a corresponding subset of the route data;

upon determination that the one or more deviation segments intersects with the route at the plurality of intersection points and the predetermined subset of the deviation segment data matches the corresponding subset of the route data, generating one or more alternative routes for the user by replacing a route portion between a first intersection point and a last intersection point of the plurality of intersection points with a corresponding deviation portion for each intersecting deviation segment; and

outputting the route and the one or more alternative routes generated for the user to an output device.

12. The method of claim 11,

wherein the predetermined subset of the deviation segment data is determined based on the user preferences.

13. The method of claim 11, wherein the deviation segment data includes information about each deviation segment and a context in which the deviation segment is used.

14. The method of claim 11, wherein the one or more deviation segments include a deviation path, and wherein the deviation path extends between the divergence location and the reconvergence location.

15. The method of claim 14, wherein the deviation path further extends a predetermined distance in a plurality of directions from one or both of the divergence location and the reconvergence location.

16. The method of claim 11, further comprising:

receiving at least a location of the navigation device; and

determining a travel path of the navigation device.

17. The method of claim 16, further comprising:

determining if the travel path deviates from the one or more alternative routes; and

upon determining that the travel path deviates from the one or more alternative routes, updating the route deviation information corresponding to the user.

18. The method of claim 11, wherein the user preferences further comprise an option to receive the peer-generated route deviation information from one or more predetermined groups.

19. A method implemented at least in part by a navigation device, the method comprising:

receiving a request to generate a route from a starting location to an ending location;

receiving a user profile including route deviation information corresponding to a user, map information, and peer-generated route deviation information generated by a plurality of peer navigation devices;

receiving user preferences from the user, the user preferences comprising at least an option to share the route deviation information corresponding to the user with one or more predetermined groups of other users to generate one or more personalized routes for those other users;

generating the route with route data based at least on the map information, the starting location, and the ending location;

based on the route deviation information corresponding to the user, identifying one or more travel patterns of the user;

identifying a subset of the peer-generated route deviation information that is relevant to the one or more travel patterns of the user, the subset of the peer-generated route deviation information including one or more deviation segments and deviation segment data;

determining if the one or more deviation segments intersect the route at a plurality of intersection points including a divergence location and a reconvergence location, and if a predetermined subset of the deviation segment data matches a corresponding subset of the route data;

upon determination that the one or more deviation segments intersects with the route at the plurality of intersection points and the predetermined subset of the deviation segment data matches the corresponding subset of the route data, generating one or more alternative routes for the user by replacing a route portion between a first intersection point and a last intersection point of the plurality of intersection points with a corresponding deviation portion for each intersecting deviation segment;

outputting at least the route and the one or more alternative routes generated for the user to an output device;

receiving at least a location of the navigation device;

determining a travel path of the navigation device;

determining if the travel path deviates from the one or more alternative routes; and

upon determining that the travel path deviates from the one or more alternative routes, updating the route deviation information corresponding to the user.