Generating personalized routes with route deviation information

Patent metadata

Field	Value
Publication number	US-10274328-B2
Application number	US-201615243631-A
Country	US
Kind code	B2
Filing date	Aug 22, 2016
Priority date	Aug 22, 2016
Publication date	Apr 30, 2019
Grant date	Apr 30, 2019

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.

First claim

The invention claimed is:

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 locatio

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Grochocki Jr David
• Salowitz Elizabeth
• Diaz Ana Lilia Otero
• Sethi Kshitij
• Mehta Kshitij
• West Jeff

Classifications

• G01C21/3423

  Multimodal routing · CPC title

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/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 title

• G01C21/3676 Primary

  Overview of the route on the road map · CPC title

• G01C21/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 title