Modeling significant locations

• US 10,111,042 B2
• Filed: 02/22/2016
• Issued: 10/23/2018
• 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): Black, Thomas G
• Assistant Examiner(s): Huynh, Luat T
• Application Number:
  US15/050,279
• Publication Number:
  US 20160174048A1
• Time in Patent Office: 974 Days
• Field of Search: 701521, 4554563
• 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 modeling significant locations are described. A significant location can be a location that is significant to a user of a mobile device for a variety of reasons. The mobile device can determine that a place or region is a significant location upon determining that, with sufficient certainty, the mobile device has stayed at the place or region for a sufficient amount of time. The mobile device can construct a state model that is an abstraction of one or more significant locations. The state model can include states representing the significant locations, and transitions representing movement of the mobile device between the locations. The mobile device can use the state model to provide predictive user assistance.

Claims

1. A method comprising:

receiving, by a mobile device and from a storage device coupled to the mobile device, a state model, the state model comprising a plurality of states and transitions between the states, each state corresponding to a location, each transition from a first state to a second state indicating that the mobile device moved from a corresponding first location to a corresponding second location, each state and each transition being associated with a one or more timestamps;

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

determining, using a current time, the future time, and a current location of the mobile device as inputs, and based on a time period associated with the state model, and the states, transitions and associated timestamps in the state model, a probability for associating with each state, the time period corresponding to a length of time for which the state machine contains location data, and the probability indicating a likelihood that the mobile device will be located at the location corresponding to the state at the future time; and

based on the probabilities, providing a location associated with at least one state as a predicted future location in response to the request.

2. The method of claim 1, wherein determining the probability for associating with 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 2, wherein determining the probability for associating with each state comprises determining a transition probability density of the mobile device moving from the current location to a location corresponding to the 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 1, wherein determining the probability for each state comprises:

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

6. The method of claim 5, wherein determining the probability to be associated with each state comprises determining an entry probability density of the mobile device entering a location corresponding to the each state.

7. The method of claim 6, wherein determining the entry probability density is 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.

8. The method of claim 1, wherein determining the probability for associating with each state comprises:

determining whether the time period associated with the state model satisfies a longevity threshold;

determining a first activity pattern upon determining that the time period associated with 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 time period associated with 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.

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

10. 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.

11. The method of claim 10, 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.

12. The method of claim 1, 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.

13. A system comprising:

one or more processors;

a non-transitory storage device storing instructions operable to cause the one or more processors to perform operations comprising;

receiving, by a mobile device and from a storage device coupled to the mobile device, a state model, the state model comprising a plurality of states and transitions between the states, each state corresponding to a location, each transition from a first state to a second state indicating that the mobile device moved from a corresponding first location to a corresponding second location, each state and each transition being associated with a one or more timestamps;

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

determining, using a current time, the future time, and a current location of the mobile device as inputs, and based on a time period associated with the state model, and the states, transitions and associated timestamps in the state model, a probability for associating with each state, the time period corresponding to a length of time for which the state machine contains location data, and the probability indicating a likelihood that the mobile device will be located at the location corresponding to the state at the future time; and

based on the probabilities, providing a location associated with at least one state as a predicted future location in response to the request.

14. The system of claim 13, wherein determining the probability for associating with each state comprises:

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

15. The system of claim 14, wherein determining the probability for associating with each state comprises determining a transition probability density of the mobile device moving from the current location to a location corresponding to the each state in one or more transitions.

16. The system of claim 15, 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.

17. The system of claim 13, wherein determining the probability for each state comprises:

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

18. The system of claim 17, wherein determining the probability to be associated with each state comprises determining an entry probability density of the mobile device entering a location corresponding to the each state.

19. The system of claim 18, wherein determining the entry probability density is 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.

20. A non-transitory storage device storing instructions operable to cause one or more processors to perform operations comprising:

receiving, by a mobile device and from a storage device coupled to the mobile device, a state model, the state model comprising a plurality of states and transitions between the states, each state corresponding to a location, each transition from a first state to a second state indicating that the mobile device moved from a corresponding first location to a corresponding second location, each state and each transition being associated with a one or more timestamps;

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

determining, using a current time, the future time, and a current location of the mobile device as inputs, and based on a time period associated with the state model, and the states, transitions and associated timestamps in the state model, a probability for associating with each state, the time period corresponding to a length of time for which the state machine contains location data, and the probability indicating a likelihood that the mobile device will be located at the location corresponding to the state at the future time; and

based on the probabilities, providing a location associated with at least one state as a predicted future location in response to the request.