PLANNING UNDER DESTINATION UNCERTAINTY

• US 20140278091A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J., Krumm, John C.
• Granted Patent: US 9,958,288 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: G01C 21/3697 Output of additional, non-guidance related information, e.g. low fuel level G01C21/3679 takes precedence
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

The subject disclosure is directed towards resolving an uncertain transportation context by suggesting one or more potential diversions. An automated routing system may generate routing information that includes map data as well as a location of a diversion having an expected cost in compliance with the uncertain transportation context. Such a diversion may be a waypoint that satisfies one or more user needs given an unknown/uncertain destination.

Claims

1. In a computing environment, a method performed at least in part on at least one processor, comprising, generating routing information based upon destination uncertainty for a vehicle, including, processing a transportation context associated with the vehicle, identifying a set of candidate diversions given the destination uncertainty corresponding to the transportation context, and examining subsets of the set of candidate diversions to determine whether at least one subset corresponds to an expected cost of complying with the transportation context.

2. The method of claim 1 further comprising generating routing information comprising the at least one subset of candidate diversions, including identifying a plurality of candidate destinations that are within reach of a vehicle, computing a probability for each candidate destination, and establishing the set of candidate diversions for the plurality of candidate destinations.

3. The method of claim 1 further comprising selecting one or more candidate diversions of the set of candidate diversions, the one or more potential diversions correspond to a minimum expected cost given the uncertain transportation context.

4. The method of claim 1 further comprising updating expected costs corresponding to the subsets of candidate diversions.

5. The method of claim 1 further comprising computing an expected value corresponding to a destination inquiry.

6. The method of claim 5 further comprising producing an expression associated with the destination inquiry via one or more input/output devices, and in response to answer data related to the destination inquiry, generating at least one of a suggested route or a suggested diversion.

7. The method of claim 1, wherein examining the subsets of the candidate diversions further comprises inferring a primary destination based upon user related data.

8. The method of claim 1 further comprising generating routing information for at least one subset of candidate diversions, including returning to a start position.

9. The method of claim 1, wherein examining the subsets of the candidate diversions further comprises using divergence model data to estimate the expected cost associated with each candidate diversion.

10. In a computing environment, an automated routing system comprising, an interface component coupled to an estimator component, wherein the interface component is configured to process data corresponding to one or more uncertain destinations, wherein the estimator component is configured to generate routing information, based upon the one or more uncertain destinations, which comprises at least one diversion between a start position and a candidate destination, wherein the interface component is further configured to present the routing information via one or more output devices.

11. The system of claim 10, wherein the estimator component is further configured to model divergence using a plurality of data sources corresponding to a plurality of waypoints within a geographic area or a driving time interval.

12. The system of claim 10, wherein the interface component is further configured to present map data comprising a suggested route and a voice recording when a vehicle is currently in motion.

13. The system of claim 10, wherein the estimator component is further configured to generate the routing information comprising one or more candidate diversions for a group of vehicles associated with the uncertain transportation context.

14. The system of claim 10, wherein the interface component is further configured to produce an audio/visual expression on an output device that corresponds to a suggested diversion associated with a minimum expected cost.

15. The system of claim 10, wherein the estimator component is further configured to compute an expected value corresponding to a destination inquiry for resolving the one or more uncertain destinations.

16. The system of claim 10, wherein the estimator component is further configured to identify a vehicle service station between the start position and a candidate destination, and communicate a reserve request to the vehicle service station.

17. The system of claim 10, wherein the estimator component is further configured to prune the one or more uncertain destinations in response to vehicle movement.

18. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising:

processing a transportation context corresponding to a vehicle, wherein the transportation context indicates destination uncertainty;

identifying candidate diversions that satisfy the transportation context;

performing a cost benefit analysis on the candidate diversions using a divergence model, including computing a first minimum expected cost for the candidate diversions;

computing an expected value of presenting a destination inquiry to resolve the destination uncertainty, including computing a second minimum expected cost for the candidate diversions given a known destination, and if the first minimum expected cost exceeds the second minimum expected cost, modifying the cost benefit analysis; and

selecting one of the candidate diversions based upon estimated savings over other candidate diversions.

19. The one or more computer-readable media of claim 18 having further computer-executable instructions comprising:

If a difference between the first minimum expected cost and a second minimum expected cost exceeds a cost of interrupting the user, generating an the destination inquiry on an input/output device;

processing user selection of a destination;

suggesting a waypoint diversion en route to the destination based upon user related data.

20. The one or more computer-readable media of claim 18 having further computer-executable instructions comprising:

accessing a plurality of data sources associated with the uncertain transportation context, the plurality of data sources comprising at least one of driver history, vehicle-related data, candidate diversion-related statistics and current environment data.