Crowd sourcing based on dead reckoning

• US 9,464,903 B2
• Filed: 07/14/2011
• Issued: 10/11/2016
• Est. Priority Date: 07/14/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Sidhu, Gursharan S., Agarwal, Sharad
• Primary Examiner(s): Charioui, Mohamed
• Assistant Examiner(s): KUAN, JOHN CHUNYANG
• Application Number:
  US13/183,124
• Publication Number:
  US 20130018629A1
• Time in Patent Office: 1,916 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/12 executed aboard the object being navigated; Dead reckoning
• CPC Class Codes: G01C 21/14 by recording the course traversed by the object G01C21/16 takes precedence
• CPC Class Codes: G01C 21/165 combined with non-inertial navigation instruments
• CPC Class Codes: G01C 21/188 for accumulated errors, e.g. by coupling inertial systems with absolute positioning systems
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/28 with correlation of data from several navigational instruments
• CPC Class Codes: G01S 19/49 whereby the further system is an inertial position system, e.g. loosely-coupled
• CPC Class Codes: G01S 5/0027 of actual mobile position, i.e. position determined on mobile
• CPC Class Codes: G01S 5/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information

Abstract

An identification is made as to when a device is at an anchor location, which can be a proximity zone along an edge of a dead zone or a location where a signal from a beacon is detected. In response to the device being at an anchor location, recording of crowd sourcing data based on dead reckoning starts. Recording crowd sourcing data based on dead reckoning includes identifying one or more signals received by a device while the device is at each of multiple positions. For each of the multiple positions, both an indication of the position determined based at least in part on dead reckoning and an indication of the one or more signals received while the device is at that position are recorded.

Claims

1. A method implemented by one or more processing units on a device, the method comprising:

identifying that the device is at an anchor location;

in response to the device being at the anchor location, starting recording in a data store of the device;

intermediate device positions determined by dead reckoning,

observation data received at the intermediate device positions, and

indications of accuracy of the intermediate device positions;

sending a first portion of the observation data and first corresponding intermediate device positions to a crowd sourcing data service, wherein the first corresponding intermediate device positions have an acceptable level of accuracy;

not sending a second portion of the observation data and second corresponding intermediate device positions to the crowd sourcing data service, wherein the second corresponding intermediate device positions do not have the acceptable level of accuracy;

identifying an updated device position that has the acceptable level of accuracy;

in response to the identifying the updated device position, using backtracking to modify at least one of the second corresponding intermediate device positions, producing a modified position; and

sending the modified position and corresponding observation data to the crowd sourcing data service.

2. The method of claim 1, the crowd sourcing data including an identification of one or more signals received while the device is at an individual intermediate device position.

3. The method of claim 1, the anchor location comprising a proximity zone along an edge of a dead zone.

4. The method of claim 1, the anchor location comprising a location where a signal from a beacon is detected.

5. The method of claim 1, further comprising:

for a subsequent device position following the anchor location, determining whether a first position of the device based on dead reckoning or a second position of the device based on a global navigation satellite system is more accurate.

6. The method of claim 5, further comprising determining and recording an accuracy estimate for the subsequent device position.

7. The method of claim 1, the updated device position being identified based on a signal received from a beacon or a global navigation satellite system.

8. The method of claim 1, the backtracking comprising using data from the dead reckoning to backtrack the at least one of the second corresponding intermediate device positions from the updated device position.

9. The method of claim 8, further comprising recording accuracy estimates that correspond to the intermediate device positions, wherein the backtracking further comprises modifying certain intermediate device positions, determined by the dead reckoning, for which the accuracy estimates do not meet an acceptable estimated accuracy.

10. The method of claim 9, wherein the accuracy estimates are made by the device.

11. The method of claim 1, further comprising using a global navigation satellite system to determine the intermediate device positions at larger intervals while the device is within a dead zone than while the device is not within the dead zone.

12. A device comprising:

a processing unit; and

a storage device storing computer readable instructions which, when executed by the processing unit, cause the processing unit to;

use inertial sensor data to determine different positions of the device in a dead zone by dead reckoning;

record the different positions and associated signals received by the device at the different positions;

continue to collect additional inertial sensor data and additional signals received by the device beyond a dead reckoning fidelity interval;

mark the additional signals as having associated positions that do not have acceptable estimated accuracy;

determine an updated position with acceptable estimated accuracy;

responsive to determining the updated position, backtrack to modify the associated positions to produce modified positions of the device that have acceptable estimated accuracy, wherein the device was at the modified positions prior to arriving at the updated position;

subsequent to modifying the associated positions, re-mark the additional signals as being associated with the modified positions; and

send crowd sourcing data to a crowd sourcing data service, the crowd sourcing data indicating that the additional signals correspond to the modified positions.

13. The device of claim 12, the backtracking being based on the additional inertial sensor data.

14. The device of claim 12, wherein the computer readable instructions further cause the processing unit to:

subsequent to determining the updated position;

determine a first estimated position of the device based on dead reckoning;

determine a second estimated position of the device using a global navigation satellite system; and

select the first estimated position or the second estimated position based on which is a more accurate position of the device.

15. The device of claim 12, the dead reckoning using a known starting position obtained before the device entered the dead zone.

16. The device of claim 12, wherein the computer readable instructions further cause the processing unit to:

determine the updated position using beacon signals from a beacon in or near the dead zone.

17. The device of claim 12, wherein the computer readable instructions further cause the processing unit to:

record the associated positions and associate the associated positions with the additional signals.

18. The device of claim 12, wherein the computer readable instructions further cause the processing unit to:

record strengths of the associated signals received by the device; and

send the strengths as part of the crowd sourcing data to the crowd sourcing data service.

19. The device of claim 12, wherein the computer readable instructions further cause the processing unit to:

extend the dead reckoning fidelity interval using a beacon signal.

20. A method implemented by one or more processing units of a device, the method comprising:

identifying that the device is at an anchor location, the anchor location comprising a proximity zone along an edge of a dead zone;

in response to the device being at the anchor location, starting recording crowd sourcing data comprising one or more signals received while the device is at multiple positions, the multiple positions being determined based at least in part on dead reckoning;

determining a subsequent position of the device based on the dead reckoning that does not have acceptable estimated accuracy;

continuing to record the one or more signals at the subsequent position and further positions determined by the dead reckoning;

when an updated position of the device that does have acceptable estimated accuracy is determined, backtracking from the updated position, the backtracking including modifying one or more of the subsequent position and the further positions of the device to have acceptable estimated accuracy; and

sending, to a data service, a portion of the crowd sourcing data that is associated with the one or more of the subsequent position and the further positions of the device that have been modified to have acceptable estimated accuracy.

21. A device comprising:

a processor and storage; and

a position determination module configured to determine multiple positions of the device based on dead reckoning and determine estimated accuracy of the multiple positions of the device, the multiple positions comprising an anchor location, an intermediate position that does not have acceptable estimated accuracy, and a later position that does have acceptable estimated accuracy;

a backtracking module configured to modify the intermediate position to have acceptable estimated accuracy based on backtracking from the later position, producing an updated position;

a data collection module configured to record crowd sourcing data comprising one or more signals received while the device is at the multiple positions; and

a communication module configured to send a portion of the crowd sourcing data to a data service, the portion being associated with the updated position of the device that has acceptable estimated accuracy,

wherein the position determination module, the backtracking module, the data collection module, and the communication module are stored on the storage and executable by the processor.

22. The device of claim 21, wherein the position determination module is further configured to determine that the device is at the anchor location, the anchor location comprising a proximity zone along an edge of a dead zone.

23. The device of claim 21, wherein the data collection module is further configured to start recording the crowd sourcing data based on the device being at the anchor location.

24. The device of claim 21, wherein the communication module is further configured to defer sending the portion of the crowd sourcing data until the intermediate position is modified to produce the updated position that does have acceptable estimated accuracy.