COMPUTING-DEVICE LOCALIZATION BASED ON INERTIAL SENSORS

• US 20130131972A1
• Filed: 11/18/2011
• Published: 05/23/2013
• Est. Priority Date: 11/18/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: KUMAR, SUMIT, PATNEY, SACHIN, ZHAO, CHUNSHUI, JOSHI, ABHIJIT PURSHOTTAM
• Application Number:
  US13/300,053
• Publication Number:
  US 20130131972A1
• Time in Patent Office: Days
• US Class Current: 701/409
• CPC Class Codes: G01C 21/1654 with electromagnetic compass
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

Technology is described for determining a location at which a computing device is positioned. For example, a computing device is positioned in an area (e.g., building), and a map (e.g., floor plan) is retrieved that depicts the area. An initial location of the computing device is determined with respect to the map. Inertial sensors record motion inputs (e.g., acceleration, orientations, etc.), which are analyzed to determine a path along which the computing device moves. The path is applied to the initial location to determine an updated location at which the computing device may be located.

Claims

1. Computer-storage media having computer-executable instructions embodied thereon that, when executed, perform a method of determining a location at which a computing device is positioned with respect to a mapped area, the method comprising:

retrieving a map depicting the mapped area and including respective positions of Wireless access points located in the mapped area;

detecting respective strengths of signals received from one or more of the wireless access points, wherein the respective strengths are used to determine an initial computing-device location comprising a position of the computing device on the map depicting the mapped area;

recording by an inertial sensor a set of acceleration values and directional inputs that describe a movement of the computing device;

calculating a change in acceleration values between an acceleration-peak value and an acceleration-valley value, wherein an amount of time lapses between a first time instant at which the acceleration-peak value is detected and a second time instant at which the acceleration-valley value is detected;

applying the change in acceleration values and the amount of time in a stride-length-estimation algorithm to calculate an estimated stride length;

combining the estimated stride length with the directional inputs to calculate an estimated movement parameter, which indicates a direction and distance in which the computing device is detected to have moved; and

applying the estimated movement parameter to the initial computing-device location to calculate an updated computing-device location comprising an updated position of the computing device on the map.

2. The media of claim 1, wherein the initial computing-device location is determined by executing a triangulation protocol.

3. The media of claim 1, wherein recording by the inertial sensor comprises recording respective measurements detected by an accelerometer, a gyroscope, and a magnetometer.

4. The media of claim 1 further comprising, applying a Bayesian filter to the estimated movement parameter to generate a plurality of particles having a distribution that represents the estimated movement parameter, wherein a particle of the plurality of particles is removed from the distribution when the particle conflicts with a non-navigatable area depicted on the map.

5. The media of claim 1, wherein the stride-length-estimation algorithm comprises a summation of:

a first test-group derived parameter,

a first quotient of the change in acceleration values and a second test-group derived parameter,

a second quotient of the amount of time and a third test-group derived parameter,

a third quotient of a fourth test-group derived parameter and a square of the change in acceleration values, and

a fourth quotient of a fifth test-group derived parameter and a square of the amount of time.

6. The media of claim 5, wherein test-group derived parameters are calculated by analyzing test-group data, which includes a plurality of known stride lengths, each of which is matched with a respective known change in acceleration and a respective known amount of time.

7. The media of claim 6, wherein analyzing the test-group data comprises applying a linear least-squares analysis to data points generated by the plurality of known stride lengths, the respective known changes in acceleration and the respective known amounts of time.

8. A method of determining a location at which a computing device is positioned with respect to a mapped area, the method comprising:

detecting by a signal receiver respective strengths of signals received from one or more wireless access points, wherein the respective strengths are used to determining an initial computing-device location comprising a position of the computing device on a map depicting the mapped area;

recording by an inertial sensor a set of acceleration values and directional inputs that describe a movement of the computing device;

calculating a change in acceleration values between an acceleration-peak value and an acceleration-valley value, wherein an amount of time lapses between a first time instant at which the acceleration-peak value is detected and a second time instant at which the acceleration-valley value is detected;

applying the change in acceleration values and the amount of time in a stride-length-estimation algorithm to calculate an estimated stride length;

combining the estimated stride length with the directional inputs to calculate an estimated movement parameter, which indicates a direction and distance in which the computing device is detected to have moved; and

applying the estimated movement parameter to the initial computing-device location to calculate an updated computing-device location comprising an updated position of the computing device on the map.

9. The method of claim 8, wherein the initial computing-device location is determined by executing a triangulation protocol.

10. The method of claim 8, wherein recording by the inertial sensor comprises recording respective measurements detected by an accelerometer, a gyroscope, and a magnetometer.

11. The method of claim 8 further comprising, applying a particle-filter method to the estimated movement parameter to generate a plurality of particles having a distribution that represents the estimated movement parameter, wherein a particle of the plurality of particles is removed from the distribution when the particle conflicts with a non-navigatable area depicted on the map.

12. The method of claim 8,

wherein the stride-length-estimation algorithm comprises a formula represented by S=α

₀+α

₂Δ

A+α

₂Δ

t+α

₃Δ

A²+α

₄Δ

t²,

wherein (S) represents an estimated stride length,

wherein Δ

A represents the change in acceleration values,

wherein Δ

t represents the amount of time, and

wherein α

₀, α

₁, α

₂, α

₃, α

₄ represent test-group derived parameters.

13. The method of claim 12, wherein test-group derived parameters are calculated by analyzing test-group data, which includes a plurality of known stride lengths, each of which is matched with a respective known change in acceleration and a respective known amount of time.

14. The method of claim 13, wherein analyzing the test-group data comprises applying a linear least-squares analysis to data points generated by the plurality of known stride lengths, the respective known changes in acceleration and the respective known amounts of time.

15. A computing device comprising a processor coupled with computer-storage media, which store computer-executable instructions thereon that, when executed by the computing device, perform a method of determining a location at which a computing device is positioned with respect to a mapped area, the computing device comprising:

a map receiver that receives a map depicting the mapped area and that depicts respective positions of wireless access points located in the mapped area;

a wireless-signal receiver that receives signals from the wireless access points and that measures respective signal strengths of the signals, which are used to determine an initial computing-device location comprising a position of the computing device on the map depicting the mapped area;

an inertial sensor that records a set of acceleration values and directional inputs that describe a movement of the computing device,

wherein a change in acceleration values exists between an acceleration-peak value and an acceleration-valley value, and

wherein an amount of time lapses between a first time instant at which the acceleration-peak value is detected and a second time instant at which the acceleration-valley value is detected;

a stride-length estimator that leverages the processor to apply the change in acceleration values and the amount of time in a stride-length-estimation algorithm to calculate an estimated stride length;

a movement-parameter calculator that leverages the processor to combine the estimated stride length with the directional inputs to calculate an estimated movement parameter, which indicates a direction and distance in which the computing device is detected to have moved; and

a computing-device-location updater that applies the estimated movement parameter to the initial computing-device location to calculate an updated computing-device location comprising an updated position of the computing device on the map.

16. The computing device of claim 15, wherein the inertial sensor comprises an accelerometer, a gyroscope, a magnetometer, or a combination thereof.

17. The computing device of claim 15,

wherein the movement-parameter calculator applies a particle-filter method to the estimated movement parameter to generate a plurality of particles having a distribution that represents the estimated movement parameter,

wherein a particle of the plurality of particles is removed from the distribution when the particle conflicts with a non-navigatable area depicted on the map, and

wherein the movement-parameter calculator recalculates the distribution to account for removal of the particle.

18. The computing device of claim 15, wherein the stride-length-estimation algorithm comprises a summation of:

a first test-group derived parameter,

a first quotient of the change in acceleration values and a second test-group derived parameter,

a second quotient of the amount of time and a third test-group derived parameter,

a third quotient of a fourth test-group derived parameter and a square of the change in acceleration values, and

a fourth quotient of a fifth test-group derived parameter and a square of the amount of time.

19. The computing device of claim 15, wherein the directional inputs comprise an angular rate and an azimuth-measurement value.

20. The computing device of claim 15 further comprising, a computing-device-location transmitter that sends the updated computing-device location to a server to facilitate location-based services that are received by the computing device.