Reduction of the impact of hard limit constraints in state space models

• US 8,996,302 B2
• Filed: 11/30/2012
• Issued: 03/31/2015
• Est. Priority Date: 11/30/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., Ma, Shannon M.
• Primary Examiner(s): To, Tuan C.
• Assistant Examiner(s): SMITH, ISAAC G
• Application Number:
  US13/691,185
• Publication Number:
  US 20140156180A1
• Time in Patent Office: 851 Days
• Field of Search: 701/433, 701/434, 701/423, 382/103, 382/107, 455/456.1, 455/456.2, 455/456.3, 455/513
• US Class Current: 701/423
• CPC Class Codes: G01C 21/3896 Transmission of map data from central databases
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting
• CPC Class Codes: G01S 5/02521 using a radio-map
• 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

Abstract

A location of a mobile device in a venue can be estimated by using a state space estimator to determine candidate locations of the mobile device at a first time point based on previous candidate positions conditioned upon an observation of one or more environmental variables. A second observation is received at a second time point, and the state space estimator performs a propagation step to determine the candidate locations at the second time point based on the candidate locations at the first time point and the second observation. The propagation step includes a plurality of sub-propagation steps in which a time length between the sub-propagation steps is a fraction of the time length between the first and second time points, and at each sub-propagation step each candidate location is propagated according to a stochastic process. The location of the mobile device at the second time point is determined based on the candidate locations at the second time point.

Claims

1. A computer-implemented method, comprising:

determining a location of a mobile device in a venue comprising a space accessible by a movable body carrying the mobile device and one or more constraints of movement of the movable body, including

determining, using a state space estimator, candidate locations of the mobile device at a first time point based on candidate positions determined at a previous time point conditioned upon an observation of one or more environmental variables provided at the first time point,

receiving a second observation of the one or more environment variables at a second time point,

using the state space estimator to perform a propagation step to determine the candidate locations of the mobile device at the second time point,

wherein the propagation step comprises a plurality of sub-propagation steps in which a time length between the sub-propagation steps is a fraction of the time length between the first and second time points, the first of the sub-propagation steps causing propagation of the candidate locations at the first time point,

wherein the propagation of each candidate location at each sub-propagation step is guided by a general direction of movement of the mobile device, and

wherein at each sub-propagation step each candidate location is propagated according to a stochastic process without causing a conflict between the candidate locations of successive sub-propagation steps and the one or more constraints of movement, and

determining the location of the mobile device at the second time point based on the candidate locations at the second time point and the second observation of the one or more environmental variables.

2. The method of claim 1, in which when performing each sub-propagation step, upon detecting a conflict between the candidate locations and the one or more constraints of movement,

performing the previous sub-propagation steps again and increasing a randomness in at least one of a heading or a velocity of the propagation of each candidate location at each sub-propagation step to explore alternative movements of the mobile device, and

identifying candidate locations that do not conflict with the one or more constraints of movement.

3. The method of claim 2 in which a conflict between the candidate locations and the one or more constraints of movement occurs when the state space estimator attempts to propagate a candidate location associated with a sub-propagation step to another candidate location associated with a successive sub-propagation step and a constraint of movement is between the candidate location and the other candidate location.

4. The method of claim 1 in which when performing the propagation step, upon detecting a conflict between the candidate locations and the one or more constraints of movement, performing the sub-propagation steps again and further reducing the time length between the sub-propagation steps and increasing the number of sub-propagation steps between the first and second time points.

5. The method of claim 1 in which the constraints of movement of the mobile device comprise walls or obstacles in the venue that may constrain movements of a pedestrian carrying the mobile device.

6. The method of claim 1 in which the time length between sub-propagation steps is equal to or less than one-tenth the time duration between updated observations.

7. A computer-implemented method, comprising:

receiving observations of one or more environment variables, in which the observations are updated at a first time interval;

propagating, using a state space estimator, candidate locations of a mobile device at a second time interval that is smaller than the first time interval such that the first interval includes a plurality of the second time intervals,

wherein the state space estimator takes into account map data when propagating the candidate locations,

wherein the map data represents a venue comprising a space accessible by a movable body carrying the mobile device and one or more constraints of movement of the movable body, and

wherein the propagating is performed according to a stochastic process and further is constrained by the one or more constraints of movement such that each pair of successive candidate locations is compatible with the one or more constraints of movement, and

when an updated observation is available, updating the candidate locations based on the updated observation; and

determining a location of the mobile device based on the candidate locations.

8. The method of claim 7 wherein a pair of successive candidate locations is incompatible with the one or more constraints of movement when the state space estimator attempts to propagate, over the second time interval, a candidate location to another candidate location and a constraint of movement is between the candidate location and the other candidate location.

9. The method of claim 7, comprising increasing a noise level of the stochastic process upon detecting that propagating the candidate positions is incompatible with the constraints of movement, in which increasing the noise level increases a randomness in at least one of a heading or a velocity of the propagation of each candidate location.

10. The method of claim 9 in which propagating the candidate positions is incompatible with the constraints of movement when the state space estimator attempts to propagate a candidate location from a first position to a second position according to the stochastic process and a constraint of movement is between the first and second positions.

11. The method of claim 7, comprising reducing the second time interval of the propagation steps upon detecting that propagating the candidate positions is incompatible with the constraints of movement, and increasing the number of propagation steps between available observation updates.

12. The method of claim 7 in which the constraints of movement comprise walls or obstacles in the venue that may constrain movements of a pedestrian carrying the mobile device.

13. The method of claim 7 in which the propagation of each candidate location at each propagation step is guided by a general direction of movement of the mobile device based on a stochastic propagation model.

14. The method of claim 7 in which the second time interval is equal to or less than one-tenth the first time interval.

15. A mobile device comprising:

a storage configured to store map data associated with a venue comprising a space accessible by a movable body and one or more constraints of movement of the movable body; and

a processor configured to

implement a state space estimator to determine candidate locations of the mobile device at a first time point based on candidate positions determined at a previous time point conditioned upon an observation of one or more environmental variables provided at the first time point,

receive a second observation of the one or more environment variables at a second time point,

use the state space estimator to perform a propagation step, taking into account of the map data, to determine the candidate locations of the mobile device at the second time point,

wherein the propagation step comprises a plurality of sub-propagation steps in which a time length between the sub-propagation steps is less than half the time length between the first and second time points, the first of the sub-propagation steps causing propagation of the candidate locations at the first time point,

wherein the propagation of each candidate location at each sub-propagation step is guided by a general direction of movement of the mobile device, and

wherein at each sub-propagation step each candidate location is propagated according to a stochastic process without causing a conflict between the candidate locations of successive sub-propagation steps and the one or more constraints of movement, and

determine the location of the mobile device at the second time point based on the candidate locations at the second time point and the second observation of the one or more environmental variables.

16. The mobile device of claim 15 in which when performing each sub-propagation step, upon detecting a conflict between the candidate locations and the one or more constraints of movement, the processor is configured to

perform the previous sub-propagation steps again and increase a randomness in at least one of a heading or a velocity of the propagation of each candidate location at each sub-propagation step to explore alternative movements of the mobile device, and

identify candidate locations that do not conflict with the one or more constraints of movement.

17. The mobile device of claim 16 in which a conflict between the candidate locations and the one or more constraints of movement occurs when the state space estimator attempts to propagate a candidate location associated with a sub-propagation step to another candidate location associated with a successive sub-propagation step and a constraint of movement is between the candidate location and the other candidate location.

18. The mobile device of claim 15 in which when performing the propagation step, upon detecting a conflict between the candidate locations and the one or more constraints of movement, the processor is configured to perform the sub-propagation steps again and further reduce the time length between the sub-propagation steps and increase the number of sub-propagation steps between the first and second time points.

19. The mobile device of claim 15 in which the constraints of movement of the mobile device comprise walls or obstacles in the venue that may constrain movements of a pedestrian carrying the mobile device.

20. The mobile device of claim 15 in which the time length between sub-propagation steps is equal to or less than one-fifth the time duration between updated observations.

21. A mobile device comprising:

one or more sensors to generate observations of one or more environment variables;

a storage configured to store map data associated with a venue comprising a space accessible by a movable body and one or more constraints of movement of the movable body; and

a processor configured to

receive observations of the one or more environment variables from the one or more sensors, in which the observations are updated at a first time interval;

propagate, using a state space estimator, candidate locations of a mobile device at a second time interval that is smaller than the first time interval such that the first interval includes a plurality of the second time intervals, wherein the propagation is performed according to a stochastic process and further is constrained by the one or more constraints of movement such that each pair of successive candidate locations is compatible with the one or more constraints of movement, and

when an updated observation is available, update the candidate locations based on the updated observation; and

determine a location of the mobile device based on the candidate locations.

22. The mobile device of claim 21 wherein the processor is configured to increase a noise level of the stochastic process upon detecting that propagating the candidate positions is incompatible with the constraints of movement, in which increasing the noise level increases a randomness in at least one of a heading or a velocity of the propagation of each candidate location.

26. The mobile device of claim 21, wherein the processor is further configured to

reduce the second time interval upon detecting that propagating the candidate positions is incompatible with the constraints of movement, and

increase a number of propagations of candidate positions between available observation updates.

27. The mobile device of claim 21, wherein a pair of successive candidate locations is incompatible with the one or more constraints of movement when the state space estimator attempts to propagate, over the second time interval, a candidate location to another candidate location and a constraint of movement is between the candidate location and the other candidate location.

23. An apparatus comprising:

a computer storage medium storing instructions that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising;

receiving observations of one or more environment variables, in which the observations are updated at a first time interval;

propagating, using a state space estimator, candidate locations of a mobile device at a second time interval that is smaller than the first time interval such that the first interval includes a plurality of the second time intervals,

wherein the state space estimator takes into account map data when propagating the candidate locations,

wherein the map data represents a venue comprising a space accessible by a movable body carrying the mobile device and one or more constraints of movement of the movable body, and

wherein the propagation is performed according to a stochastic process and further is constrained by the one or more constraints of movement such that each pair of successive candidate locations is compatible with the one or more constraints of movement, and

when an updated observation is available, updating the candidate locations based on the updated observation; and

determining a location of the mobile device based on the candidate locations.

24. The apparatus of claim 23, wherein the operations further comprise increasing a noise level of the stochastic process upon detecting that propagating the candidate positions is incompatible with the constraints of movement, in which increasing the noise level increases a randomness in at least one of a heading or a velocity of the propagation of each candidate location.

25. The apparatus of claim 23, wherein the operations further comprise

reducing the second time interval upon detecting that propagating the candidate positions is incompatible with the constraints of movement, and

increasing a number of propagations of candidate positions between available observation updates.

28. The apparatus of claim 23, wherein a pair of successive candidate locations is incompatible with the one or more constraints of movement when the state space estimator attempts to propagate, over the second time interval, a candidate location to another candidate location and a constraint of movement is between the candidate location and the other candidate location.