Planning under destination uncertainty

Patent metadata

Field	Value
Publication number	US-9958288-B2
Application number	US-201313831483-A
Country	US
Kind code	B2
Filing date	Mar 14, 2013
Priority date	Mar 14, 2013
Publication date	May 1, 2018
Grant date	May 1, 2018

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.

First claim

What is claimed is:

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 tr

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Horvitz Eric J
• Krumm John C

Classifications

• G01C21/3453

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G01C21/3617

  using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement · CPC title

• G01C21/3697

  Output of additional, non-guidance related information, e.g. low fuel level (G01C21/3679 takes precedence) · CPC title

• G06Q30/0283

  Price estimation or determination · CPC title

• G01C21/3679 Primary

  Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities (G01C21/3611 takes precedence) · CPC title