# US 2014/0156180 A1 · Reduction Of The Impact Of Hard Limit Constraints In State Space Models > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0156180 A1 - Document ID: US20140156180A1 - Status: Published application - Kind: A1 - Application number: 13/691,185 - Filed: 2012-11-30 - Published: 2014-06-05 - Earliest claimed: 2012-11-30 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Lukas M. Marti; Shannon M. Ma - Web page: https://patentgrep.com/patent/US20140156180A1 ## CPC - G01S 5/0252: {Radio frequency fingerprinting} - G01C 21/3896: {Transmission of map data from central databases} - G01S 5/02521: {using a radio-map} - G01S 5/0278: {involving statistical or probabilistic considerations (G01S5/0252, G01S5/0294 take precedence)} - G01S 5/0294: {Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering} - G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) ## 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 ### Claim 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 based on the candidate locations at the first time point and the second observation of the one or more environmental variables, 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, and at each sub-propagation step each candidate location is propagated according to a stochastic process, and determining the location of the mobile device at the second time point based on the candidate locations at the second time point. ### Claim 2 (depends on 1) 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 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. ### Claim 3 (depends on 2) 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 from a first position at the first time point to a second position at the second time point and a constraint of movement is between the first and second positions. ### Claim 4 (depends on 1) 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 propagation steps between the first and second time points. ### Claim 5 (depends on 1) The method of claim 1 in which the propagation of each candidate location at each sub-propagation step is guided by a general direction of movement of the mobile device. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 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, the propagation being performed according to a stochastic process, 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. ### Claim 9 (depends on 8) The method of claim 8 wherein the state space estimator takes into account map data when propagating the candidate locations, in which 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, the propagation being constrained by the one or more constraints of movement. ### Claim 10 (depends on 9) The method of claim 9, 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. ### Claim 11 (depends on 10) The method of claim 10 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. ### Claim 12 (depends on 9) The method of claim 9, 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. ### Claim 13 (depends on 9) The method of claim 9 in which the constraints of movement comprise walls or obstacles in the venue that may constrain movements of a pedestrian carrying the mobile device. ### Claim 14 (depends on 8) The method of claim 8 in which the propagation of each candidate location at each propagation step is guided by a stochastic propagation model. ### Claim 15 (depends on 8) The method of claim 8 in which the second time interval is equal to or less than one-tenth the first time interval. ### Claim 16 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 based on the candidate locations at the first time point and the second observation of the one or more environmental variables, 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, and at each sub-propagation step each candidate location is propagated according to a stochastic process, and determine the location of the mobile device at the second time point based on the candidate locations at the second time point. ### Claim 17 (depends on 16) The mobile device of claim 16 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 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. ### Claim 18 (depends on 17) The mobile device of claim 17 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 from a first position at the first time point to a second position at the second time point and a constraint of movement is between the first and second positions. ### Claim 19 (depends on 16) The mobile device of claim 16 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 propagation steps between the first and second time points. ### Claim 20 (depends on 16) The mobile device of claim 16 in which the propagation of each candidate location at each sub-propagation step is guided by a general direction of movement of the mobile device. ### Claim 21 (depends on 16) The mobile device of claim 16 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. ### Claim 22 (depends on 16) The mobile device of claim 16 in which the time length between sub-propagation steps is equal to or less than one-fifth the time duration between updated observations. ### Claim 23 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, the propagation being performed according to a stochastic process, taking into account of the map data, 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. ### Claim 24 (depends on 23) The mobile device of claim 23 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. ### Claim 25 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, the propagation being performed according to a stochastic process, 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. ### Claim 26 (depends on 25) The apparatus of claim 25, wherein the state space estimator takes into account map data when propagating the candidate locations, in which 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, the propagation being constrained by the one or more constraints of movement, and 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. ### Claim 27 (depends on 25) The apparatus of claim 25, wherein the state space estimator takes into account map data when propagating the candidate locations, in which 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, the propagation being constrained by the one or more constraints of movement, and the operations further comprise 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. ### Claim 28 (depends on 23) The mobile device of claim 23, wherein the processor is further configured to reduce 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.