Transport-dependent prediction of destinations

• US 8,538,686 B2
• Filed: 09/09/2011
• Issued: 09/17/2013
• Est. Priority Date: 09/09/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gruen, Robert W., Krumm, John C.
• Primary Examiner(s): Marc, McDieunel
• Application Number:
  US13/228,460
• Publication Number:
  US 20130066548A1
• Time in Patent Office: 739 Days
• Field of Search: 701/208, 701/426, 701/467, 701/468, 701/533, 222/153.145, 222/457, 222/523, 222/541.7, 340/990, 340/994, 340/995.24, 342/463, 342/464, 342/457, 190/102, 190/108, 235/375, 235/384, 705/5
• US Class Current: 701/426
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement

Abstract

A destination analysis module is described which estimates at least one destination of a user given a partial path taken by the user within a geographic area. The destination analysis module operates by detecting a mode of transportation that a user uses to traverse the path (e.g., automobile, public transportation, walking, etc.). The destination analysis module then loads a model associated with the mode of transportation into a destination prediction module and estimates at least one destination based on the path and the model. The model has various components that depend on the mode of transportation, such as routing network information and prior probability information.

Claims

1. A method, implemented by at least one computer, for predicting at least one destination of a user, comprising:

receiving position information at a particular time, describing a position of the user within a geographic area;

updating, based on the position information, a current state of a path taken by the user within the geographic area; and

estimating at least one destination of the user based on the path and a model, the model being associated with a determined mode of transportation that the user is using to traverse the path, the model being selected from among plural models associated with plural respective modes of transportation,

said receiving, updating, and estimating being performed using said at least one computer,

said at least one computer including at least one of (a) and/or (b), where (a) corresponds to one or more processing devices and (b) corresponds to one or more hardware logic components.

2. The method of claim 1, wherein the geographic area is discretized into a plurality of map location elements, and wherein the path is represented as a set of map location elements that are traversed by the path.

3. The method of claim 1, wherein a set of possible modes of transportation correspond to:

at least one user-controlled vehicular mode of transportation;

at least one public mode of transportation; and

at least one pedestrian mode of transportation.

4. The method of claim 1, wherein said estimating uses Bayes rule to determine the destination of the user.

5. The method of claim 1, wherein the model that is loaded includes a likelihood component, the likelihood component providing information that enables the destination prediction module to determine a likelihood of the path given a particular candidate destination.

6. The method of claim 5, wherein the likelihood component includes routing network information, the routing network information describing routes within the geographic area that are available to the mode of transportation, together with costs associated with those routes.

7. The method of claim 6, wherein the costs in the routing network information have a cost type, and wherein the cost type is chosen based on the mode of transportation.

8. The method of claim 7, wherein the cost type is chosen from among:

time of traversal;

physical distance; and

financial cost.

9. The method of claim 5, wherein the likelihood component includes an efficiency parameter that describes an efficiency at which users advance to destinations within the geographic area, wherein the efficiency parameter has a value that is chosen based on the mode of transportation.

10. The method of claim 1, wherein the model that is loaded includes at least one prior probability component, said at least one prior probability component describing prior probability information that enables the destination prediction module to determine whether a particular candidate destination represents an actual destination, independent of the influence of the path.

11. The method of claim 10, wherein said at least one prior probability component describes probabilities associated with trip durations within the geographic area, with respect to the mode of transportation.

12. The method of claim 10, wherein said at least one prior probability component describes probabilities based on points of interest within the geographic area, with respect to the mode of transportation.

13. The method of claim 10, wherein said at least one prior probability component describes probabilities based on previous destinations visited by the user, with respect to the mode of transportation.

14. The method of claim 10, wherein said at least one prior probability component describes probabilities for types of ground cover within the geographic area, with respect to the mode of transportation.

15. The method of claim 10, wherein the prior probability information imparted by said at least one prior probability component is qualified by at least one parameter, wherein said at least one parameter has a value which is chosen based on the mode of transportation.

16. The method of claim 1, wherein, if the determined mode of transportation is a newly encountered mode, loading the model associated with the determined mode of transportation into a destination prediction module, for use by said estimating.

17. At least one computer for predicting at least one destination, comprising:

a path assessment module configured to identify a current state of a path C taken by a user within a geographic area, based on successive instances of position information that describe the path;

a transportation mode determination module configured to determine a mode of transportation that a user is using to traverse the path C;

a configuration module configured to make a model associated with the mode of transportation available for use in predicting destinations;

a destination prediction module configured to estimate at least one destination of the user based on the path C and the model,

the destination prediction module model estimating each destination based on p(C|c*) and p(c*),

where p(c*|C) represents a probability that a particular candidate destination c* represents an actual destination of the user, given the path C,

p(C|c*) represents a likelihood of the path C given the particular candidate destination c*, where p(C|c*) is dependent on the mode of transportation,

p(c*) represents a prior probability that the particular candidate destination c* represents the actual destination of the user, where p(c*) is dependent on the mode of transportation, and

said at least one computer including at least one of (a) and/or (b), where (a) corresponds to one or more processing devices and (b) corresponds to one or more hardware logic components.

18. The destination analysis module of claim 17, wherein the model specifies routing network information for use in computing p(C|c*), the routing network information describing routes within the geographic area that are available to the mode of transportation, together with costs associated with those routes.

19. The destination analysis module of claim 17, wherein model specifies prior probability information for use in computing p(c*), the prior probability information describing one or more of:

probabilities associated with trip durations within the geographic area, with respect to the mode of transportation,

probabilities based on points of interest within the geographic area, with respect to the mode of transportation,

probabilities based on previous destinations visited by the user, with respect to the mode of transportation, and

probabilities for types of ground cover within the geographic area, with respect to the mode of transportation.

20. A physical and tangible computer readable storage medium device for storing computer readable instructions, the computer readable instructions implementing a method when executed by one or more processing devices, the method comprising:

receiving position information at a particular time, describing a position of a user within a geographic area;

updating, based on the position information, a current state of a path taken by the user within the geographic area;

receiving a determination of a mode of transportation that the user is using to traverse the path, to provide a determined mode of transportation; and

estimating at least one destination of the user based on the path and a model, the model being associated with the determined mode of transportation.