Route prediction

• US 9,846,049 B2
• Filed: 07/09/2008
• Issued: 12/19/2017
• Est. Priority Date: 07/09/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Krumm, John Charles
• Primary Examiner(s): Obaid, Fateh M
• Application Number:
  US12/170,068
• Publication Number:
  US 20100010733A1
• Time in Patent Office: 3,450 Days
• Field of Search: None
• 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:

one or more processors; and

memory storing one or more components that are executable by the one or more processors, the one or more components comprising;

a communication component to obtain global positioning data of an entity;

an observation component to track a journey of the entity;

a recognition component to identify a potential travel space of the entity such that the potential travel space is identified by determining a set radius from a location of the entity or a number of intersections around a location of the entity, the potential travel space including potential travel paths;

a partition component to divide the potential travel paths into a set of future segments defined by at least one travel decision point within the potential travel space;

an analysis component to evaluate travel history of the entity, wherein the travel history of the entity is determined at least partially based on the global positioning data obtained by the communication component; and

a calculation component to;

define a particular number of most recently traveled segments used to compute a route likelihood over the set of future segments, wherein an individual segment is defined by two travel decision points and wherein the most recently traveled segments are obtained through at least one of the communication component or the observation component;

determine, based at least in part on the travel history of the entity, a direction of travel of the entity based at least in part on observing the particular number of most recently traveled segments traveled by the entity during a current journey using the observation component; and

compute the route likelihood of the entity over the set of future segments based at least in part on the direction of travel by computing a probability that the entity will select different outcomes of the at least one travel decision point.

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

3. The system of claim 1, further comprising a designation component to identify a highest probability outcome of the at least one travel decision point.

4. The system of claim 3, further comprising a creation component to produce an estimated route based upon the highest probability outcome of the at least one travel decision point.

5. The system of claim 4, wherein the creation component is further configured to produce the estimated route based upon the highest probability outcome of the at least one travel decision point and at least one contextual circumstance.

6. The system of claim 1, wherein the potential travel space includes at least two travel decision points that do not define a same segment, and wherein a first probability the entity selects different outcomes of a first travel decision point of the at least two travel decision points is independent of a second probability the entity selects different outcomes of a second travel decision point of the at least two travel decision points.

7. The system of claim 1, wherein the calculation component is further configured to use a Markov model to compute the route likelihood of the entity over the set of future segments.

8. A method, comprising:

obtaining global positioning data of an entity;

tracking a journey of the entity;

identifying a potential travel space of the entity such that the potential travel space is identified by determining a set radius from a location of the entity or a number of intersections around a location of the entity, wherein the potential travel space includes potential travel paths;

dividing the potential travel paths into a set of future segments defined by at least one travel decision point within the potential travel space;

determining a particular number of most recently traveled segments most recently traveled by the entity based on at least one of the obtained global positioning data or the tracked journey of the entity, the determined particular number of most recently traveled segments being used to compute a route likelihood over the set of future segments, wherein an individual segment is defined by two travel decision points;

evaluating, using one or more processors, travel history of the entity based on at least in part on the tracked journey;

determining, using at least one of the one or more processors and based at least in part on the travel history of the entity, a direction of travel of the entity based at least in part on observing the particular number of most recently traveled segments traveled by the entity during a current journey using at least in part the tracked journey of the entity; and

computing, using at least one of the one or more processors, the route likelihood of the entity over the set of future segments based at least in part on the direction of travel by computing a probability that the entity will select different outcomes of the at least one travel decision point.

9. The method of claim 8, further comprising using a Markov model to compute the route likelihood of the entity over the set of future segments.

10. The method of claim 8, wherein the potential travel space includes at least two travel decision points that do not define a same segment, and wherein a first probability the entity takes different outcomes of a first travel decision point of the at least two travel decision points is independent of a second probability the entity takes different outcomes of a second travel decision point of the at least two travel decision points.

15. The method of claim 8, further comprising:

producing an estimated route based upon the computed route likelihood of the entity over the set of future segments;

determining that a probability of the entity traveling the estimated route meets or exceeds a threshold probability; and

at least partly in response to the determining, automatically adapting a vehicle to an expected operating condition without user intervention.

16. The method of claim 15, wherein automatically adapting the vehicle comprises at least one of:

engaging a turn signal for the vehicle;

pointing headlights of the vehicle;

darkening a windshield of the vehicle;

deactivating a cylinder of an engine of the vehicle;

or

pre-braking the vehicle.

11. A method, comprising:

obtaining global positioning data of an entity;

tracking a journey of the entity;

identifying a potential travel space of the entity such that the potential travel space is identified by determining a set radius from a location of the entity or a number of intersections around a location of the entity, wherein the potential travel space includes potential travel paths;

dividing the potential travel paths into a set of future segments defined by at least one travel decision point within the potential travel space;

determining a particular number of most recently traveled segments by the entity based on the global positioning data, the determined particular number of most recently traveled segments being used to compute a route likelihood, wherein an individual segment is defined by two travel decision points;

evaluating, using one or more processors, travel history of the entity based on at least partially on the tracked journey;

determining, using at least one of the one or more processors and based at least in part on the travel history of the entity, a direction of travel of the entity based at least in part on observing the particular number of most recently traveled segments traveled by the entity during a current journey;

computing, using at least one of the one or more processors, the route likelihood of the entity as a probability the entity will travel different segments among the set of future segments from at least one travel decision point, wherein the set of future segments is determined based at least in part on the direction of travel; and

identifying a highest probability outcome of the at least one travel decision point.

12. The method of claim 11, further comprising producing an estimated route based upon the highest probability outcome of the at least one travel decision point.

13. The method of claim 11, further comprising:

determining that a probability of the highest probability outcome meets or exceeds a threshold probability; and

at least partly in response to the determining, causing anticipatory information associated with the highest probability outcome to be output, the anticipatory information warning the entity of a road situation.

14. The method of claim 11, further comprising:

determining that a probability of the highest probability outcome meets or exceeds a threshold probability; and

at least partly in response to the determining, automatically adapting a vehicle to an expected operating condition without user intervention.