Predictive user assistance

• US 9,807,565 B2
• Filed: 09/09/2013
• Issued: 10/31/2017
• Est. Priority Date: 06/07/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., Dal Santo, Michael P., Huang, Ronald Keryuan
• Primary Examiner(s): Appiah, Charles
• Assistant Examiner(s): Mastrodonato, Margaret G
• Application Number:
  US14/022,099
• Publication Number:
  US 20140364150A1
• Time in Patent Office: 1,513 Days
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 88/005 Data network PoA devices

Abstract

Techniques for predictive user assistance are described. A mobile device can learn movement patterns of the mobile device. The mobile device can construct a state model that is an abstraction of locations where the mobile device stayed for sufficient amount of time. The state model can include states representing the locations, and transitions representing movement of the mobile device between the locations. The mobile device can use the state model, a current location of the mobile device, and a current time to determine a predicted future location of the mobile device at a given future time. Based on the predicted location and the given future time, the mobile device can predict what assistance a user of the mobile device may request. The mobile device can then provide the assistance to the user before the given future time.

Claims

1. A method comprising:

receiving, by a mobile device, an ordered plurality of locations of the mobile device;

determining, by the mobile device, a plurality of significant locations, wherein each significant location corresponds to a respective cluster of two or more consecutive locations in the ordered plurality of locations;

determining, by the mobile device, a state model, including designating each significant location as a respective state in the state model, and representing each movement of the mobile device between significant locations as a respective transition between corresponding states of the state model;

receiving, by the mobile device, a request for predicting a future location of the mobile device, the request specifying a future time;

determining a current location of the mobile device and a current time;

determining, using the current time and the current location of the mobile device as inputs, a respective probability of transitioning from the current location to each state of the state model;

selecting, from the state model and based on the future time, a first transition from a first state of the states to a second state of the states or a second transition from the first state to the second state, each of the first transition and the second transition being associated with a respective transition time and a respective transition probability, wherein the selecting is based on comparing the respective transition time and the future time;

based on the transition probability associated with the selected transition and the probabilities, determining a likely future state of the mobile device; and

providing at least one location associated with the likely state as a predicted future location in response to the request.

2. The method of claim 1, wherein determining the respective probability of transitioning from the current location to each state comprises:

determining that the current location is in state, where the current location is represented as a state in the state model.

3. The method of claim 1, wherein determining the respective probability of transitioning from the current location to each state comprises determining a transition probability density of the mobile device moving from the current location to a respective location corresponding to each state in one or more transitions.

4. The method of claim 3, wherein:

the transition probability density satisfies properties of a Markov process, and

determining the transition probability density is based on the transitions between states and a transition begin timestamp and a transition end timestamp associated with each of the transitions.

5. The method of claim 3, wherein determining the respective probability of transitioning from the current location to each state comprises:

determining that the current location is out of state; and

determining an entry probability density of entering into each of the states based on a dwell time the mobile device is in each state, the dwell time being determined based on one or more entry timestamps and one or more exit timestamps associated with the respective state.

6. The method of claim 1, wherein determining the respective probability of transitioning to each state comprises:

determining whether the state model satisfies a longevity threshold;

determining a first activity pattern upon determining that the state model satisfies the longevity threshold, wherein the first activity pattern corresponds to a first time span, or determining a second activity pattern upon determining that the state model does not satisfy the longevity threshold, wherein the second activity pattern corresponds to a second time span, the first time span being longer than the second time span; and

determining the probability based on the current time, the future time, and the first activity pattern or second activity pattern.

7. The method of claim 1, comprising filtering the states in the state model based on a respective distance between the current location and each location represented in the state model and a difference between the current time and the future time.

8. The method of claim 1, wherein providing the location as the predicted future location comprises:

identifying a state associated with a highest probability, and designating the location associated with the state associated with the highest probability as the predicted future location;

or

ranking the states based on the probabilities and one or more forecast attributes, and designating the location associated with a highest rank as the predicted future location.

9. The method of claim 8, wherein forecast attributes include at least one of:

a time of last visit to each corresponding location;

a derived likelihood for a forecast window based on the current location, the current time, and a forecast window length;

a temporal length of the state model;

an aggregated dwell time at each state;

or

a number of visits at each state.

10. The method of claim 9, comprising:

determining that a data density of the state model satisfies a sparse model threshold; and

in response, determining the probability for associating with each state in a sparse operating mode.

11. A mobile device comprising:

one or more processors; and

a non-transitory computer-readable medium coupled to the one or more processors and storing instructions operable to cause the one or more processors to perform operations comprising;

receiving an ordered plurality of locations of the mobile device;

determining a plurality of significant locations, wherein each significant location corresponds to a respective cluster of two or more consecutive locations in the ordered plurality of locations;

determining a state model, including designating each significant location as a respective state in the state model, and representing each movement of the mobile device between significant locations as a respective transition between corresponding states of the state model;

receiving a request for predicting a future location of the mobile device, the request specifying a future time;

determining a current location of the mobile device and a current time;

determining, using the current time and the current location of the mobile device as inputs, a respective probability of transitioning from the current location to each state of the state model;

selecting, from the state model and based on the future time, a first transition from a first state of the states to a second state of the states or a second transition from the first state to the second state, each of the first transition and the second transition being associated with a respective transition time and a respective transition probability, wherein the selecting is based on comparing the respective transition time and the future time;

based on the transition probability associated with the selected transition and the probabilities, determining a most likely future state of the mobile device; and

providing at least one location associated with the likely state as a predicted future location in response to the request.

12. The mobile device of claim 11, wherein determining the respective probability of transitioning from the current location to each state comprises:

determining that the current location is in state, where the current location is represented as a state in the state model.

13. The mobile device of claim 11, wherein determining the respective probability of transitioning from the current location to each state comprises determining a transition probability density of the mobile device moving from the current location to a respective location corresponding to each state in one or more transitions.

14. The mobile device of claim 13, wherein:

the transition probability density satisfies properties of a Markov process, and

determining the transition probability density is based on the transitions between states and a transition begin timestamp and a transition end timestamp associated with each of the transitions.

15. The mobile device of claim 13, wherein determining the respective probability of transitioning from the current location to each state comprises:

determining that the current location is out of state; and

determining an entry probability density of entering into each of the states based on a dwell time the mobile device is in each state, the dwell time being determined based on one or more entry timestamps and one or more exit timestamps associated with the respective state.

16. The mobile device of claim 11, wherein determining the respective probability of transitioning to each state comprises:

determining whether the state model satisfies a longevity threshold;

determining a first activity pattern upon determining that the state model satisfies the longevity threshold, wherein the first activity pattern corresponds to a first time span, or determining a second activity pattern upon determining that the state model does not satisfy the longevity threshold, wherein the second activity pattern corresponds to a second time span, the first time span being longer than the second time span; and

determining the probability based on the current time, the future time, and the first activity pattern or second activity pattern.

17. The mobile device of claim 11, the operations comprising filtering the states in the state model based on a respective distance between the current location and each location represented in the state model and a difference between the current time and the future time.

18. The mobile device of claim 11, wherein providing the location as the predicted future location comprises:

identifying a state associated with a highest probability, and designating the location associated with the state associated with the highest probability as the predicted future location;

or

ranking the states based on the probabilities and one or more forecast attributes, and designating the location associated with a highest rank as the predicted future location.

19. The mobile device of claim 18, wherein forecast attributes include at least one of:

a time of last visit to each corresponding location;

a derived likelihood for a forecast window based on the current location, the current time, and a forecast window length;

a temporal length of the state model;

an aggregated dwell time at each state;

or

a number of visits at each state.

20. The mobile device of claim 19, the operations comprising:

determining that a data density of the state model satisfies a sparse model threshold; and

in response, determining the probability for associating with each state in a sparse operating mode.

21. A non-transitory computer-readable medium coupled to one or more processors of a mobile device and storing instructions operable to cause the one or more processors to perform operations comprising:

receiving an ordered plurality of locations of the mobile device;

Determining a plurality of significant locations, wherein each significant location corresponds to a respective cluster of two or more consecutive locations in the ordered plurality of locations;

determining a state model, including designating each significant location as a respective state in the state model, and representing each movement of the mobile device between significant locations as a respective transition between corresponding states of the state model;

receiving a request for predicting a future location of the mobile device, the request specifying a future time;

determining a current location of the mobile device and a current time;

determining, using the current time and the current location of the mobile device as inputs, a respective probability of transitioning from the current location to each state of the state model;

selecting, from the state model and based on the future time, a first transition from a first state of the states to a second state of the states or a second transition from the first state to the second state, each of the first transition and the second transition being associated with a respective transition time and a respective transition probability, wherein the selecting is based on comparing the respective transition time and the future time;

based on the transition probability associated with the selected transition and the probabilities, determining a likely future state of the mobile device; and

providing at least one location associated with the likely state as a predicted future location in response to the request.

22. The non-transitory computer-readable medium of claim 21, wherein determining the respective probability of transitioning from the current location to each state comprises:

determining that the current location is in state, where the current location is represented as a state in the state model.

23. The non-transitory computer-readable medium of claim 21, wherein determining the respective probability of transitioning from the current location to each state comprises determining a transition probability density of the mobile device moving from the current location to a respective location corresponding to each state in one or more transitions.

24. The non-transitory computer-readable medium of claim 23, wherein:

the transition probability density satisfies properties of a Markov process, and

determining the transition probability density is based on the transitions between states and a transition begin timestamp and a transition end timestamp associated with each of the transitions.

25. The non-transitory computer-readable medium of claim 23, wherein determining the respective probability of transitioning from the current location to each state comprises:

determining that the current location is out of state; and

determining an entry probability density of entering into each of the states based on a dwell time the mobile device is in each state, the dwell time being determined based on one or more entry timestamps and one or more exit timestamps associated with the respective state.

26. The non-transitory computer-readable medium of claim 21, wherein determining the respective probability of transitioning to each state comprises:

determining whether the state model satisfies a longevity threshold;

determining a first activity pattern upon determining that the state model satisfies the longevity threshold, wherein the first activity pattern corresponds to a first time span, or determining a second activity pattern upon determining that the state model does not satisfy the longevity threshold, wherein the second activity pattern corresponds to a second time span, the first time span being longer than the second time span; and

determining the respective probability based on the current time, the future time, and the first activity pattern or second activity pattern.

27. The non-transitory computer-readable medium of claim 21, the operations comprising filtering the states in the state model based on a respective distance between the current location and each location represented in the state model and a difference between the current time and the future time.

28. The non-transitory computer-readable medium of claim 21, wherein providing the location as the predicted future location comprises:

identifying a state associated with a highest probability, and designating the location associated with the state associated with the highest probability as the predicted future location;

or

ranking the states based on the probabilities and one or more forecast attributes, and designating the location associated with a highest rank as the predicted future location.

29. The non-transitory computer-readable medium of claim 28, wherein forecast attributes include at least one of:

a time of last visit to each corresponding location;

a derived likelihood for a forecast window based on the current location, the current time, and a forecast window length;

a temporal length of the state model;

an aggregated dwell time at each state;

or

a number of visits at each state.

30. The non-transitory computer-readable medium of claim 29, the operations comprising:

determining that a data density of the state model satisfies a sparse model threshold; and

in response, determining the respective probability for associating with each state in a sparse operating mode.