Enhanced user efficiency in route planning using route preferences

• US 10,024,675 B2
• Filed: 05/10/2016
• Issued: 07/17/2018
• 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
• Primary Examiner(s): ANTONUCCI, ANNE MARIE
• Application Number:
  US15/150,830
• Publication Number:
  US 20170328725A1
• Time in Patent Office: 798 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 route preference of the user;

generating a plurality of routes based on the routing request;

determining a preference weight of the route preference, the route preference corresponding to a 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;

forecasting a route characteristic corresponding to the route preference for each of a plurality of route components of a given route based on a respectively estimated time of traversal for the route component;

determining, for each route of the plurality of routes, a route score of the route based on the preference weight, wherein the route score of the given route is determined by weighting the route preference for each route component of the plurality of route components by the forecasted route characteristic of the route component;

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 route preference;

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 preference, 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 forecasted route characteristic of each route component is represented as a respective value and the subscore of the route component is determined by combining the respective value with the preference weight.

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

determining, for each route component of the plurality of route components of the given route, the respective estimated time of traversal of the route component based on a starting time for the given route and one or more expected traversal speeds for the given route prior to reaching the route component.

8. The computer-implemented method of claim 1, wherein the route preference corresponds to 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 the route preference corresponds to 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 the route preference corresponds to a preference to avoid one a hazard that corresponds to an inherent route component feature.

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

12. The computer-implemented method of claim 1, wherein the route preference corresponds to 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 route preference of the user;

generating a plurality of routes based on the routing request;

determining a preference weight of the route preference, the 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;

forecasting a route characteristic corresponding to the route preference for each of a plurality of route components of a given route based on a respectively estimated time of traversal for the route component;

determining, for each route of the plurality of routes, a route score of the route based on the preference weight, wherein the route score of the given route is determined by a respective subscore of each route component of the plurality of route components, the subscore being based on the forecasted route characteristic of the route component;

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 route preference;

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 the route characteristic is determined based on identifying an elevation of a given route component of plurality of route components of the given route.

16. The computer-implemented system of claim 13, wherein the route characteristic of each route component is determined by determining a direction of travel over the route component relative to the sun.

17. The computer-implemented system of claim 13, comprising:

determining, for each route component of the plurality of route components of the given route, the respective estimated time of traversal of the route component based on a starting time for the given route and one or more expected traversal speeds for the given route prior to reaching the route component.

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 a machine learning model using the extracted user events, the machine learning model corresponding to a route preference 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 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 route preference of the user;

generating a plurality of routes based on the routing request;

determining the preference weight using the updated machine learning model;

forecasting a route characteristic corresponding to the route preference for each of a plurality of route components of a given route based on a respectively estimated time of traversal for the route component;

forecasting, for each route component, of the plurality of route components, a respective time to travel over the route component based on the respectively estimated time of traversal for the route component;

based on an estimated time to travel over the route component;

determining, for each route of the plurality of routes, a route score of the route based on the determined preference weight, wherein the route score of the given route is determined by weighting the route preference for each route component of the plurality of route components by the forecasted route characteristic of the route component and by the forecasted respective time to travel over the route component;

selecting a suggested route from the plurality of routes based on the route score of the suggested 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.