Location determination using dual statistical filters

• US 9,491,585 B2
• Filed: 05/31/2014
• Issued: 11/08/2016
• Est. Priority Date: 05/31/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Huang, Joseph Ding-Jiu, Patel, Abhinav R., Tay, Darin, Millman, David Benjamin, Tsoong, Jessica Noel, Mayor, Robert, Lovich, Vitali
• Primary Examiner(s): CAI, WAYNE HUU
• Application Number:
  US14/292,859
• Publication Number:
  US 20150350849A1
• Time in Patent Office: 892 Days
• Field of Search: 4554561-4566, 455/404.2, 701/213, 701/469, 701/472, 701/473, 701/525
• US Class Current: 1/1
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/04 using association of physical positions and logical data in a dedicated environment, e.g. buildings or vehicles
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

Methods, systems, and computer program product for location determination using dual statistical filters are described. A mobile device can determine a location of the mobile device using a particle filter and a Kalman filter. The particle filter can filter candidate locations of the mobile device using measurements of environment variables in the venue. The Kalman filter can filter inputs from a sensor of the mobile device for measuring angular movement of the mobile device. The particle filter and the Kalman filter can be linked by heading of the mobile device. Output of the Kalman filter can be used to determine where to place particles, or candidate locations, in a next iteration of the particle filter. Output from the particle filter can be used to determine a center mode of the Kalman filter and to determine a bias of the sensor for measuring angular movement.

Claims

1. A method of iteratively estimating a location of a mobile device at a venue, comprising:

from an initial estimated location of the mobile device at the venue at an initial time in a first iteration, obtaining a set of first candidate locations of the mobile device at a first time that is after the initial time using a statistical model of a first Bayesian filter, each first candidate location being represented using location coordinates and being associated with a respective heading, the heading being inferred from a direction from the initial estimated location to a respective candidate position;

from readings of a first sensor of the mobile device that measures an angular value, determining a statistical distribution of the angular value as a function of the heading of the mobile device using a statistical model of a second Bayesian filter;

determining a set of second candidate locations of the mobile device at a second time that is after the first time, wherein each second candidate location is determined using a first candidate location and a respective heading that has been adjusted according to the statistical distribution of the angular value;

weighting each second candidate location by matching readings of a second sensor of the mobile device against location fingerprint data that specifies expected readings of the second sensor at various locations of the venue, including giving higher weight to a second candidate location that has a higher degree of match; and

determining a most likely location of the mobile device at the venue using the weighted second candidate locations and designating the most likely location as an estimated location of the mobile device at the second time.

2. The method of claim 1, wherein the angular value includes an angle, angular velocity, or angular acceleration.

3. The method of claim 1, wherein the initial estimated location is determined using a Gaussian random noise.

4. The method of claim 1, wherein obtaining a set of first candidate locations of the mobile device including determining the first candidate locations by applying a statistical random noise to the initial estimated location, the statistical random noise having a specified variance per unit time.

5. The method of claim 4, wherein the specified variance per unit time includes a uniform variance per unit time, a constantly growing variance per unit time, or linearly growing variance per unit time.

6. The method of claim 1, wherein the first sensor of the mobile device includes a gyroscope, a magnetometer, or a derived sensor that includes a statistical signal processing unit that applies the statistical processing to a motion sensor.

7. The method of claim 1, wherein:

the second sensor includes a wireless receiver;

the expected readings of the second sensor includes at least one of expected received signal strength indicators (RSSIs) of radio frequency (RF) signals or round-trip time (RTT) of the RF signals; and

the expected readings of the second sensor are associated with a plurality of grids, each grid corresponding to a different signal source, having a plurality of cells, and covering at least a portion of the venue.

8. The method of claim 1, wherein:

the first Bayesian filter is a type of particle filter where each particle is a candidate location, and

the second Bayesian filter is a type of Kalman filter using reading of the first sensor as input.

9. The method of claim 1, comprising adjusting a parameter of a model that defines the first Bayesian filter, the parameter including a stride length using results of weighting each second candidate location.

10. The method of claim 1, comprising:

adjusting a bias of the first sensor of the mobile device using results of weighting each second candidate location, wherein adjusting the bias includes adjusting parameters of the statistical distribution of the angular value over heading of the mobile device for a next iteration of location estimation.

11. The method of claim 10, wherein adjusting parameters of the statistical distribution of the angular value over heading comprises inducing weight on central moments of measurements of the first sensor from the weighted second candidate locations.

12. The method of claim 11, comprising:

designating the most likely location of the mobile device as the initial estimated location of the mobile device in a next iteration, wherein in the next iteration, each respective heading is adjusted according to the statistical distribution of the angular value having the adjusted bias.

13. A mobile device comprising:

one or more processors; and

a storage device storing computer instructions operable to cause the one or more processors to perform operations of iteratively estimating a location of a mobile device at a venue, the operations comprising;

from an initial estimated location of the mobile device at the venue at an initial time in a first iteration, obtaining a set of first candidate locations of the mobile device at a first time that is after the initial time using a statistical model of a first Bayesian filter, each first candidate location being represented using location coordinates and being associated with a respective heading, the heading being inferred from a direction from the initial estimated location to a respective candidate position;

from readings of a first sensor of the mobile device that measures an angular value, determining a statistical distribution of the angular value as a function of heading of the mobile device using a statistical model of a second Bayesian filter;

determining a set of second candidate locations of the mobile device at a second time that is after the first time, wherein each second candidate location is determined using a first candidate location and a respective heading that has been adjusted according to the statistical distribution of the angular value;

weighting each second candidate location by matching readings of a second sensor of the mobile device against location fingerprint data that specifies expected readings of the second sensor at various locations of the venue, including giving higher weight to a second candidate location that has a higher degree of match; and

determining a most likely location of the mobile device at the venue using the weighted second candidate locations and designating the most likely location as an estimated location of the mobile device at the second time.

14. The mobile device of claim 13, wherein the angular value includes an angle, angular velocity, or angular acceleration.

15. The mobile device of claim 13, wherein the initial estimated location is determined using a Gaussian random noise.

16. The mobile device of claim 13, wherein obtaining a set of first candidate locations of the mobile device including determining the first candidate locations by applying a statistical random noise to the initial estimated location, the statistical random noise having a specified variance per unit time.

17. The mobile device of claim 16, wherein the specified variance per unit time includes a uniform variance per unit time, a constantly growing variance per unit time, or linearly growing variance per unit time.

18. The mobile device of claim 17, wherein each weight is applied to a measurement of a signal of a respective signal source as determined by a mobile device configured to determine a location, at the venue, of the mobile device.

19. A non-transitory computer-readable medium storing computer instructions operable to cause one or more processors of a mobile device to perform operations of iteratively estimating a location of a mobile device at a venue, the operations comprising:

from an initial estimated location of the mobile device at the venue at an initial time in a first iteration, obtaining a set of first candidate locations of the mobile device at a first time that is after the initial time using a statistical model of a first Bayesian filter, each first candidate location being represented using location coordinates and being associated with a respective heading, the heading being inferred from a direction from the initial estimated location to a respective candidate position;

from readings of a first sensor of the mobile device that measures an angular value, determining a statistical distribution of the angular value as a function of heading of the mobile device using a statistical model of a second Bayesian filter;

determining a set of second candidate locations of the mobile device at a second time that is after the first time, wherein each second candidate location is determined using a first candidate location and a respective heading that has been adjusted according to the statistical distribution of the angular value;

weighting each second candidate location by matching readings of a second sensor of the mobile device against location fingerprint data that specifies expected readings of the second sensor at various locations of the venue, including giving higher weight to a second candidate location that has a higher degree of match; and

determining a most likely location of the mobile device at the venue using the weighted second candidate locations and designating the most likely location as an estimated location of the mobile device at the second time.

20. The non-transitory computer-readable medium of claim 19, wherein the angular value includes an angle, angular velocity, or angular acceleration.

21. The non-transitory computer-readable medium of claim 19, wherein the initial estimated location is determined using a Gaussian random noise.

22. The non-transitory computer-readable medium of claim 19, wherein obtaining a set of first candidate locations of the mobile device including determining the first candidate locations by applying a statistical random noise to the initial estimated location, the statistical random noise having a specified variance per unit time.

23. The non-transitory computer-readable medium of claim 22, wherein the specified variance per unit time includes a uniform variance per unit time, a constantly growing variance per unit time, or linearly growing variance per unit time.