ROUTE PREDICTION

• US 20100010733A1
• Filed: 07/09/2008
• Published: 01/14/2010
• Est. Priority Date: 07/09/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krumm, John Charles
• Granted Patent: US 9,846,049 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

Driving history of a user with regard to a particular road intersection can be collected and retained in storage. A Markov model can be used to predict likelihood of the user making a particular decision regarding the intersection. A highest likelihood decision can be identified and used to create a travel route. In addition, contextual information can be taken into account when creating the route, such as time of day, road conditions, user situation, and the like.

Claims

1. A system, comprising:

an analysis component that evaluates travel history of an entity; and

a calculation component that uses a Markov model to compute a route likelihood as a function of a result of the evaluation.

2. The system of claim 1, the entity is a user, a user classification, a vehicle, or a combination thereof.

3. The system of claim 1, further comprising a recognition component that identifies a potential travel space of the entity.

4. The system of claim 3, further comprising a partition component that divides potential travel space into segments, the calculation component computes the route likelihood through computation of how the entity travels upon termination of a segment.

5. The system of claim 1, the route likelihood is probability a user takes different outcomes of at least one travel decision point.

6. The system of claim 5, further comprising a designation component that identifies a highest probability outcome of at least one travel decision point.

7. The system of claim 6, further comprising a creation component that produces an estimated route based upon highest probability of at least one travel decision point.

8. The system of claim 7, the creation component produces the estimated route based upon highest probability of at least one travel decision point and at least one contextual circumstance.

9. The system of claim 1, outcomes of travel decision points are independent of one another, the route likelihood is a function of an outcome of at least two travel decision points.

10. A method, comprising:

identifying a journey resolution position, the journey resolution position includes at least two results; and

determining likelihood of at least one of the results of the journey resolution position occurring through use of a Markov model.

11. The method of claim 10, further comprising determining likelihood of all realistic results of the journey resolution position occurring through use of a Markov model.

12. The method of claim 10, further comprising analyzing a journey area, a result of the analysis is used to identify the journey resolution position.

13. The method of claim 10, the Markov model uses previous journey experience to determine likelihood of at least one of the results.

14. The method of claim 10, further comprising creating a route based upon the highest sequential determined likelihoods.

15. The method of claim 10, further comprising observing how an entity responds to the journey resolution position.

16. The method of claim 15, further comprising updating a history for the entity based upon the observation.

17. A system, comprising:

means for dividing a travel area into at least one travel decision point;

means for analyzing history concerning at least one travel decision point;

means for determining likelihood of outcomes of the travel decision point through use of a Markov model and a product of the historical analysis;

means for monitoring a result of at least one travel decision point; and

means for retaining the result in conjunction with the history.

18. The system of claim 17, further comprising means for predicting the travel area, the travel area divided is the predicted travel area.

19. The system of claim 18, further comprising means for creating a travel route based upon a highest result of the determined likelihood for each travel decision point.

20. The system of claim 19, the travel route is created based upon a highest result of the determined likelihood for each travel decision point and contextual information.