Methods for predicting destinations from partial trajectories employing open- and closed-world modeling methods

Patent metadata

Field	Value
Publication number	US-10746561-B2
Application number	US-201113190121-A
Country	US
Kind code	B2
Filing date	Jul 25, 2011
Priority date	Sep 29, 2005
Publication date	Aug 18, 2020
Grant date	Aug 18, 2020

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.

First claim

What is claimed is:

1. A physical memory device that stores 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 input data indicating at least one of specialized knowledge of the user, historical driving efficiencies, or historical driving times;
determining travel data during a trip in progress that does not have a user-specified destination provided;
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 to determine a plurality of likelihoods, 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;
predicting one or more destinations for the trip based on the likelihoods for the plurality of candidate destinations;
causing a content provider to determine relevant information associated with the one or more predicted destinations; and
presenting the relevant information to the user.

2. The physical memory device of claim 1 , wherein said predicting comprises:
probabilistically predicting the one or more destinations according to Bayes rule.

3. The physical memory device of claim 1 , the method further comprising:
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 physical memory device of claim 1 , wherein the relevant information associated with the one or more predicted destinations includes at least one of warnings of traffic, construction, safety issues ahead, advertisements being displayed, directions, routing advice, or updates.

5. The physical memory device of claim 4 , the method further comprising:
tailoring the relevant information provided by the content component based on user related preferences.

6. The physical memory device of claim 1 , wherein said predicting comprises:
predicting the one or more destinations during travel utilizing real time location data.

7. The physical memory device of claim 1 , the method further comprising:
generating a probabilistic grid associated with a map of a geographic location used to predict the one or more destinations.

8. The physical memory device of claim 1 , the method further comprising:
generating routes likely to be utilized to travel to candidate destinations; and
determining time estimates associated with the routes.

9. The physical memory device of claim 1 , the method further comprising:
integrating open world and closed world analyses into a location forecast; and
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 destination of a user, comprising:
with a computer that includes at least one processor and at least one memory that stores instructions executable by the computer:
generating a probabilistic grid associated with a geographic location using the computer;
evaluating data associated with a trip in progress that does not have a user-specified destination provided using the computer to determine a likelihood for each of a plurality of candidate cells in the probabilistic grid based at least in part on the data to determine a plurality of likelihoods, 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;
predicting one or more destinations related to the trip utilizing the grid and the likelihoods using the computer;
causing a content provider to determine relevant information associated with the one or more predicted destinations; and
presenting the relevant information to the user.

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 , wherein the relevant information associated with the one or more predicted destinations includes at least one of warnings of traffic, construction, safety issues ahead, advertisements being displayed, directions, routing advice, or updates.

14. The method of claim 10 , wherein:
said 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.

Assignees

• Krumm John C
• Horvitz Eric J
• Microsoft Technology Licensing Llc

Inventors

• Krumm John C
• Horvitz Eric J

Classifications

• G08G1/0968

  Systems involving transmission of navigation instructions to the vehicle · CPC title

• G01C21/34

  Route searching; Route guidance · CPC title

• G08G1/0969 Primary

  having a display in the form of a map · CPC title

• G01C21/26

  specially adapted for navigation in a road network · CPC title

• H04W4/02

  Services making use of location information · CPC title