MULTI-STAGE DEAD RECKONING FOR CROWD SOURCING

• US 20130110454A1
• Filed: 10/28/2011
• Published: 05/02/2013
• Est. Priority Date: 10/28/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sidhu, Gursharan S., Agarwal, Sharad
• Granted Patent: US 10,184,798 B2
• Time in Patent Office: Days
• US Class Current: 702/150
• CPC Class Codes: G01C 21/188 for accumulated errors, e.g. by coupling inertial systems with absolute positioning systems

Abstract

A device identifies signals it receives at a particular point in time, such as Wi-Fi signals and cell tower signals. The device records data indicating these identified signals, as well as data used to determine the position of the device at that particular point in time. The position of the device is determined using dead reckoning, which is separated into two stages. In the first stage, a distance and direction of movement is determined at the device based on data from various inertial sensors of the device. In the second stage, various filters, maps, and/or other techniques are used at another device (e.g., a crowd sourcing data service) thus alleviating the device of the burden of performing the second stage.

Claims

1. A method comprising:

collecting, at a first device, data from one or more inertial sensors to determine a position of the first device using dead reckoning;

performing, at the first device, a first stage of the dead reckoning based on the data from the one or more inertial sensors; and

providing a result of the first stage to a second device to perform a second stage of the dead reckoning based on the result of the first stage.

2. A method as recited in claim 1, the result of the first stage comprising a direction and a length of each of multiple steps taken by a user of the first device.

3. A method as recited in claim 1, the result of the first stage comprising a distance moved and a direction of movement.

4. A method as recited in claim 3, the second stage comprising using a particle filter or Kalman filter to estimate a position of the first device after each of the multiple steps.

5. A method as recited in claim 3, the second stage comprising using a map to estimate a position of the first device after each of the multiple steps.

6. A method as recited in claim 1, further comprising compressing, prior to providing the result of the first stage to the second device, the result of the first stage, and providing the result of the first stage to the second device by providing the compressed result of the first stage to the second device.

7. A method as recited in claim 1, further comprising waiting to send the result of the first stage until the first device can communicate with a network having a cost or fee below a threshold amount.

8. A method as recited in claim 1, further comprising:

determining, based on an amount of power that would be consumed by one or more components of the first device in performing the second stage of the dead reckoning, whether to perform the second stage of the dead reckoning at the first device or at the second device; and

providing the result of the first stage to the second device if determined that the second stage of the dead reckoning is to be performed at the second device, otherwise performing the second stage of the dead reckoning at the first device.

9. A method as recited in claim 8, the determining comprising determining to perform the second stage of dead reckoning at the first device if an amount of power consumed by a processor of the first device in performing the second stage of the dead reckoning is less than an amount of power consumed by a network component in transferring the result of the first stage to the second device.

10. A method as recited in claim 1, further comprising:

determining, based on an amount of data included in the result of the first stage of the dead reckoning, whether to perform the second stage of the dead reckoning at the first device or at the second device; and

providing the result of the first stage to the second device if determined that the second stage of the dead reckoning is to be performed at the second device, otherwise performing the second stage of the dead reckoning at the first device.

11. A method as recited in claim 1, further comprising:

determining, based on an amount of time taken to transfer the result of the first stage of the dead reckoning to the second device and receive an indication of a position of the first device from the second device, whether to perform the second stage of the dead reckoning at the first device or at the second device; and

providing the result of the first stage to the second device if determined that the second stage of the dead reckoning is to be performed at the second device, otherwise performing the second stage of the dead reckoning at the first device.

12. A method comprising:

receiving, from a first device, a result from a first stage of dead reckoning based on data from one or more inertial sensors of the first device; and

performing, at a second device that receives the result from the first stage, a second stage of the dead reckoning based on the result from the first stage.

13. A method as recited in claim 12, the result comprising movement data at a particular point in time, the receiving further comprising receiving observation data including an indication of identifiers of wireless access points or cell transceivers from which signals are received by the first device at the particular point in time.

14. A method as recited in claim 12, the second device being included as part of a crowd sourcing data service.

15. A method as recited in claim 12, the result from the first stage comprising a direction and a length of each of multiple steps taken by a user of the first device.

16. A method as recited in claim 12, the result from the first stage comprising a distance moved and a direction of movement of the first device.

17. A method as recited in claim 12, further comprising receiving the result from the first stage of dead reckoning only if the first device determined, based on an amount of power that would be consumed by one or more components of the first device in performing the second stage of the dead reckoning, to perform the second stage of the dead reckoning at the second device.

18. A method as recited in claim 12, further comprising receiving the result from the first stage of dead reckoning only if the first device determined, based on an amount of data included in the result from the first stage of the dead reckoning, to perform the second stage of the dead reckoning at the second device.

19. A method as recited in claim 12, further comprising receiving the result from the first stage of dead reckoning only if the first device determined, based on an amount of time taken to transfer the result of the first stage from the dead reckoning to the second device and receive an indication of a position of the first device from the second device, to perform the second stage of the dead reckoning at the second device.

20. One or more computer storage media having stored thereon multiple instructions that, when executed by one or more processors of a device, cause the one or more processors to:

collect, at the device, data from one or more inertial sensors to determine a position of the device at a particular point in time using dead reckoning;

perform, at the device, a first stage of the dead reckoning based on the data from the one or more inertial sensors to generate a result including a distance moved by the device and a direction of movement of the device; and

provide, after waiting until the device can communicate with a network having a cost or fee below a threshold amount, both observation data and the result of the first stage to a crowd sourcing data service to perform a second stage of the dead reckoning based on the result of the first stage, the observation data including an indication of identifiers of wireless access points or cell transceivers from which signals are received by the device at the particular point in time.