METHODS FOR PREDICTING DESTINATIONS FROM PARTIAL TRAJECTORIES EMPLOYING OPEN- AND CLOSED-WORLD MODELING METHODS

• US 20110282571A1
• Filed: 07/25/2011
• Published: 11/17/2011
• Est. Priority Date: 09/29/2005
• 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 10,746,561 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/24 specially adapted for cosmonautical navigation
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/024 Guidance services

Abstract

The claimed subject matter provides systems and/or methods that facilitate inferring probability distributions over the destinations and/or routes of a user, from observations about context and partial trajectories of a trip. Destinations of a trip are based on at least one of a prior and a likelihood based at least in part on the received input data. The destination estimator component can use one or more of a personal destinations prior, time of day and day of week, a ground cover prior, driving efficiency associated with candidate locations, and a trip time likelihood to probabilistically predict the destination. In addition, data gathered from a population about the likelihood of visiting previously unvisited locations and the spatial configuration of such locations may be used to enhance the predictions of destinations and routes.

Claims

1. At least one computer-readable storage medium encoded with instructions that, when executed perform a method that facilitates determining one or more destinations of a user, the method comprising:

receiving input data about the user, the user data indicating at least one of;

the user'"'"'s specialized knowledge or historical driving efficiencies or historical driving times; and

determining travel data during a trip;

determining a likelihood for each of a plurality of candidate destinations based at least in part on the received input data about the user and the travel data, the likelihood indicating, for each of the plurality of candidate destinations, a likelihood that the candidate destination is the destination of the trip, the likelihood being a trip time likelihood based at least in part on an estimated time to a candidate destination and an elapsed trip time; and

predicting one or more destinations for the trip based on the likelihoods for the plurality of candidate destinations.

2. The system of claim 1, wherein:

the destination estimator component utilizes Bayes rule to probabilistically predict the one or more destinations.

3. The system of claim 1, further comprising:

a fusing component that enables selecting at least one of a personal destinations prior, a ground cover prior, an efficient driving likelihood, and a trip time likelihood to combine to probabilistically predict the one or more destinations.

4. The system of claim 1, further comprising:

a content component that provides relevant information associated with the one or more predicted destinations, the content component provides at least one of warnings of traffic, construction, safety issues ahead, advertisements being displayed, directions, routing advice, and updates.

5. The system of claim 4, further comprising:

a customization component that tailors the relevant information provided by the content component based on user related preferences.

6. The system of claim 1, wherein:

the destination estimator component predicts the one or more destinations during travel utilizing real time location data.

7. The system of claim 1, further comprising:

a grid component that generates a probabilistic grid associated with a map of a geographic location that is employed by the destination estimator component to predict the one or more destinations.

8. The system of claim 1, further comprising:

a route planning component that generates routes likely to be utilized to travel to candidate destinations and determines time estimates associated with the routes.

9. The system of claim 1, wherein:

the destination estimator component integrates open world and closed world analyses into a location forecast, where the destination estimator component performs forecasting about a likelihood of a driver visiting a previously unobserved location and spatial relationships of new locations, given prior observations of locations.

10. A method that facilitates determining a user'"'"'s destination, comprising:

generating a probabilistic grid associated with a geographic location;

evaluating data associated with a trip to determine a likelihood for each of a plurality of candidate cells in the probabilistic grid based at least in part on the data, the likelihood indicating, for each of the plurality of candidate destinations, a likelihood that the destination of the trip is within the candidate cell, the likelihood being a trip time likelihood based at least in part on an estimated time to a destination within the candidate cell and an elapsed trip time; and

predicting one or more destinations related to the trip utilizing the grid and the likelihoods.

11. The method of claim 10, further comprising:

selecting a cell based on the likelihood.

12. The method of claim 10, further comprising:

predicting the one or more destinations as the trip is in progress.

13. The method of claim 10, further comprising:

providing relevant information associated with the one or more predicted destinations.

14. The method of claim 10, wherein:

predicting one or more destinations related to the trip utilizing the grid and the likelihoods comprises predicting one or more destinations based on the likelihoods and one or more priors.

15. The method of claim 10, further comprising:

generating the one or more priors based on one or more of a set of a user'"'"'s previous destinations and a probability that a cell is the destination based on ground cover within the cell.

16. The method of claim 10, further comprising generating the likelihood based on one or more of a change in time until an arrival at a candidate destination and an elapsed trip time.

17. At least one computer-readable storage device comprising computer executable instructions that, when executed, perform a method that facilitates determining one or more destinations of a user, the method comprising:

obtaining travel data during a trip;

determining a likelihood for each of a plurality of candidate destinations based at least in part on the travel data, the likelihood indicating, for each of the plurality of candidate destinations, a likelihood that the candidate destination is the destination of the trip, the likelihood being a trip time likelihood based at least in part on an estimated time to a candidate destination and an elapsed trip time; and

predicting one or more destinations for the trip based on the likelihoods for the plurality of candidate destinations.

18. The at least one computer-readable storage device of claim 17, wherein:

the likelihoods are determined using Bayes rule to probabilistically predict the one or more destinations.

19. The at least one computer-readable storage device of claim 17, further comprising:

selecting at least one of a personal destinations prior, a ground cover prior or an efficient driving likelihood to combine with the trip time likelihood to probabilistically predict the one or more destinations.

20. The at least one computer-readable storage device of claim 17, further comprising:

receiving relevant information associated with the one or more predicted destinations, the relevant information comprising at least one of warnings of traffic, construction, safety issues ahead, advertisements being displayed, directions and routing advice.