Planning under destination uncertainty

• US 9,958,288 B2
• Filed: 03/14/2013
• Issued: 05/01/2018
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Horvitz, Eric J., Krumm, John C.
• Primary Examiner(s): WHITTINGTON, JESS G
• Application Number:
  US13/831,483
• Publication Number:
  US 20140278091A1
• Time in Patent Office: 1,874 Days
• 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 for generating routing information based upon destination uncertainty for a vehicle, the method performed at least in part on at least one processor, the method comprising:

processing a transportation context associated with the vehicle, the transportation context comprising a set of rules defined by a user, the set of rules defining cost thresholds associated with candidate destinations;

identifying a plurality of candidate destinations;

determining, from the plurality of candidate destinations, an inferred primary destination;

generating at least one destination-centric route to the inferred primary destination;

while the vehicle is in route on the at least one destination-centric route, identifying a set of candidate diversions given the destination uncertainty, the transportation context, and the inferred primary destination, the set of candidate diversions associated with the inferred primary destination and located away from the at least one destination-centric route;

examining subsets of the candidate diversions to determine whether at least one subset corresponds to an expected cost of complying with the transportation context;

generating an opportunistic route through at least one candidate diversion of the at least one subset of the candidate diversions and to the inferred primary destination;

comparing a first value of confirming, with the user, the opportunistic route through the at least one candidate diversion against a second value of not confirming the opportunistic route with the user, the second value being based at least in part on additional driving time for diverting to the at least one candidate diversion in view of an uncertainty of the at least one candidate diversion;

upon comparing the first value with the second value, confirming or not confirming the opportunistic route; and

presenting the opportunistic route on a map.

2. The method of claim 1 further comprising generating routing information comprising the at least one subset of candidate diversions, including computing a probability for one or more candidate destinations, 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 of candidate diversions, the one or more candidate diversions correspond to a minimum expected cost given the transportation context.

4. The method of claim 1 further comprising updating expected costs corresponding to the subsets of the set 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 set of candidate diversions further comprises inferring the inferred primary destination based upon user related data.

8. The method of claim 1 further comprising generating routing information from the at least one candidate diversion back to a start position.

9. The method of claim 1, wherein examining the subsets of the updated set of candidate diversions further comprises estimating expected divergence costs associated with one or more of the subsets of the updated set of candidate diversions.

10. The method of claim 1 further comprising:

upon determining that the at least one candidate diversion, pruning the updated set of candidate diversions to exclude one or more other candidate diversions.

11. In a computing environment, an automated routing system comprising:

a memory area storing transportation context and routing information, the transportation context comprising a set of rules defined by a user, the set of rules defining cost thresholds associated with candidate destinations; and

a processor programmed to;

process data, using an interface component, corresponding to one or more candidate destinations;

generate at least one destination-centric route, using the interface component, to an inferred primary destination of the one or more candidate destinations;

while a vehicle is in route on the at least one destination-centric route, generate opportunistic routing information, using an estimator component, based upon the inferred primary destination and the transportation context, the opportunistic routing information including at least one first candidate diversion between a start position and the inferred primary destination of the one or more candidate destinations;

receive the opportunistic routing information by an output component;

compare a first value of confirming, with the user, the opportunistic route through the at least one first candidate diversion against a second value of not confirming the opportunistic route with the user, the second value being based at least in part on additional driving time for diverting to the at least one first candidate diversion in view of an uncertainty of the at least one first candidate diversion;

upon comparing the first value with the second value, confirm or not confirming the opportunistic route; and

present the opportunistic route on a map.

12. The system of claim 11, wherein the processor is further programmed to estimate, using the estimator component, expected divergence costs associated with the at least one first candidate diversions using a plurality of data sources corresponding to a plurality of waypoints within a geographic area or a driving time interval.

13. The system of claim 11, wherein the processor is further programmed to, by using the output component, receive map data from an interface component, and present a portion of the map data on the map, the map data including a suggested route and a voice recording when a vehicle is currently in motion.

14. The system of claim 11, wherein the processor is further programmed to, by using the output component, receive an audio/visual expression from the interface component, and present the audio/visual expression, the audio/visual expression corresponding to a suggested diversion associated with a minimum expected cost.

15. The system of claim 11, wherein the processor is further programmed to compute, using the estimator component, an expected value corresponding to a destination inquiry for resolving the one or more candidate destinations.

16. The system of claim 11, wherein the processor is further programmed to identify, using the estimator component, a vehicle service station between the start position and the one or more candidate destinations, and communicate a reserve request to the vehicle service station.

17. The system of claim 11, wherein the processor is further programmed to prune the one or more candidate destinations in response to vehicle movement.

18. One or more computer-readable hardware devices having computer-executable instructions, which upon execution perform operations, comprising:

processing a transportation context corresponding to a vehicle, wherein the transportation context does not include a certain destination and thereby indicates destination uncertainty, the transportation context comprising a set of rules defined by a user, the set of rules defining cost thresholds associated with candidate destinations;

while the vehicle is in route to a destination inferred from the transportation context, identifying a plurality of candidate destinations;

identifying candidate diversions that satisfy the transportation context, the candidate diversions associated with the plurality of candidate destinations;

while the vehicle is in route to the known destination, selecting one of the candidate diversions based upon the transportation context;

generate an opportunistic route through the one of the candidate diversions and to the inferred primary destination of the plurality of candidate destinations;

comparing a first value of confirming, with the user, the opportunistic route through the one of the candidate diversions against a second value of not confirming the opportunistic route with the user, the second value being based at least in part on additional driving time for diverting to the one of the candidate diversions in view of an uncertainty of the one the candidate diversions;

upon comparing the first value with the second value, confirming or not confirming the opportunistic route; and

presenting the opportunistic route on a map.

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

presenting a destination inquiry on an input/output device;

processing user selection of a destination; and

suggesting at least one of the candidate diversions en route to the destination based upon user related data.

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

accessing a plurality of data sources associated with the 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.