ENHANCED USER EFFICIENCY IN ROUTE PLANNING USING ROUTE PREFERENCES

• US 20170328725A1
• Filed: 05/10/2016
• Published: 11/16/2017
• Est. Priority Date: 05/10/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Schlesinger, Benny, Weinberg, Shira, Borsutsky, Yuval, Cohen, Avichai
• Granted Patent: US 10,024,675 B2
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/3438 Rendez-vous, i.e. searching a destination where several users can meet, and the routes to this destination for these users; Ride sharing, i.e. searching a route such that at least two users can share a vehicle for at least part of the route
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• 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

Abstract

In various implementations, routing factors are identified based on a routing request associated with a user, where the routing factors include route preferences of the user. Routes are generated based on the routing request. Preference weights are determined for the route preferences, where the preference weights correspond to machine learning models based on sensor data provided by one or more sensors in association with the user. Route scores are determined for the routes based on the preference weights. A suggested route is provided to a user device associated with the user, where the suggested route corresponds to a selected route of the routes and is provided based on the route score of the selected route.

Claims

1. A computer-implemented method comprising:

identifying routing factors based on a routing request associated with a user, the routing factors comprising a plurality of route preferences of the user;

generating a plurality of routes based on the routing request;

determining a preference weight of each route preference of the plurality of route preferences, each route preference corresponding to a respective machine learning model that determines the preference weight based on aggregated user events extracted from sensor data provided by one or more sensors in association with the user;

determining, for each route of the plurality of routes, a route score of the route based on the preference weight of each route preference of the plurality of route preferences;

selecting a suggested route from the plurality of routes based on the route score of the suggested route and based on a comparison between the suggested route and a reference route; and

providing the suggested route via a user device associated with the user, the suggested route corresponding to a selected route of the plurality of routes.

2. The computer-implemented method of claim 1, wherein the providing of the suggested route via the user device comprises one or more of displaying the suggested route on a user interface, providing turn-by-turn directions via the user interface, presenting the route on the user device, and providing the suggested route to a computer-controlled transportation vehicle.

3. The computer-implemented method of claim 1, further comprising:

generating the reference route independently of the plurality of route preferences;

determining a threshold value based on the reference route; and

selecting the suggested route for the transmitting based on a comparison between an estimated time to travel over the suggested route to the threshold value.

4. The computer-implemented method of claim 1, further comprising excluding a deficient route of the plurality of routes from being provided to the user device as the suggested route based on determining that at least one of an estimated time to travel over the deficient route, a distance of the deficient route, or a combination of the estimated time to travel and the distance exceeds a threshold value.

5. The computer-implemented method of claim 1, further comprising:

generating the reference route independently of the plurality of route preferences, the reference route being optimized to minimize time to travel over the reference route;

determining a threshold value based on the time to travel; and

excluding a deficient route of the plurality of routes from being transmitted to the user device as the suggested route based on determining that an estimated time to travel over the deficient route exceeds the threshold value.

6. The computer-implemented method of claim 1, wherein the determining of the route score comprises:

determining, for each route component of a plurality of route components of the route, a route preference subscore of the route component;

combining the route preference subscore of each route component of the plurality of route components into a route preference score that represents the route preference; and

applying the preference weight to the route preference score.

7. The computer-implemented method of claim 1, wherein the determining of the route score comprises:

determining, for each route component of a plurality of route components of the route, a respective estimated time of traversal of the route component;

forecasting, for each route component of a plurality of route components of the route, route characteristics of the route component based on the respective estimated time of traversal; and

determining the route score from the forecasted route characteristics of each of the plurality of route components.

8. The computer-implemented method of claim 1, wherein a given route preference of the plurality of route preferences corresponds a preference for main route components that on aggregate users traverse more frequently than non-main route components.

9. The computer-implemented method of claim 1, wherein a given route preference of the plurality of route preferences corresponds a preference to traverse familiar route components that on aggregate the user has traversed more frequently than unfamiliar route components.

10. The computer-implemented method of claim 1, wherein a given route preference of the plurality of route preferences corresponds a preference to avoid one a hazard that corresponds to an inherent route component feature.

11. The computer-implemented method of claim 1, wherein a given route preference of the plurality of route preferences corresponds a preference for safer areas during routes that is based on crime statistics.

12. The computer-implemented method of claim 1, wherein a given route preference of the plurality of route preferences corresponds a preference based on cellular reception during routes.

13. A computer-implemented system comprising:

one or more computer memory storing computer-useable instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising;

identifying routing factors based on a routing request associated with a user, the routing factors comprising a plurality of route preferences of the user;

generating a plurality of routes based on the routing request;

determining a preference weight of each route preference of the plurality of route preferences, each route preference corresponding to a respective machine learning model that determines the preference weight based on aggregated user events extracted from sensor data provided by one or more sensors in association with the user;

determining, for each route of the plurality of routes, a route score of the route based on the preference weight of each route preference of the plurality of route preferences;

selecting a suggested route from the plurality of routes based on the route score of the suggested route and based on a comparison between the suggested route and a reference route; and

transmitting the suggested route to a user device associated with the user, the suggested route corresponding to a selected route of the plurality of routes.

14. The computer-implemented system of claim 13, wherein the method further comprises:

generating the reference route independently of the plurality of route preferences;

determining a threshold value based on the reference route; and

selecting the suggested route for the transmitting based on a comparison between an estimated time to travel over the suggested route to the threshold value.

15. The computer-implemented system of claim 13, wherein a given route preference of the plurality of route preferences is based on identifying an elevation of a given route component of a plurality of route components of the route.

16. The computer-implemented system of claim 13, wherein a given route preference of the plurality of route preferences is based on determining a direction of travel over a route component of a plurality of route components of the route relative to the sun.

17. The computer-implemented system of claim 13, wherein the determining of the route score comprises:

determining, for each route component of a plurality of route components of the route, a respective estimated time of traversal of the route component;

forecasting, for each route component of a plurality of route components of the route, a weather condition of the route component based on the respective estimated time of traversal; and

determining the route score from the forecasted weather condition of each of the plurality of route components.

18. A computer navigation device comprising a user interface, one or more processors, and one or more computer memory storing computer-useable instructions that, when executed by the one or more processors, cause the one or more computing devices to perform a method comprising:

extracting user events from sensor data provided by one or more sensors of one or more devices in association with a user;

updating machine learning models using the extracted user events, each machine learning model corresponding to a respective route preference of a plurality of route preferences of the user and being configured to determine a preference weight based on aggregated user events extracted from sensor data provided by the one or more sensors in association with the user, the updating for each machine learning model incorporating the extracted user events into the aggregated user events thereby altering the preference weight;

receiving, via the user interface, a routing request from a user;

identifying routing factors based on the received routing request, the routing factors comprising the plurality of route preferences of the user;

generating a plurality of routes based on the routing request;

determining the preference weight of each route preference of the plurality of route preferences using the updated machine learning models;

determining, for each route of the plurality of routes, a route score of the route based on the preference weight of each route preference of the plurality of route preferences;

selecting a suggested route from the plurality of routes based on the route score of the suggested route and based on an estimated time to travel over the suggested route or a total distance of the suggested route being lower than corresponding features of the reference route; and

providing the suggested route via the user interface.

19. The one or more computer storage devices of claim 18, further comprising selecting the reference route for the comparison based on an estimated time to travel over the reference route.

20. The one or more computer storage devices of claim 18, further comprising generating the reference route, wherein the reference route is optimized to minimize a time of travel over the reference route.