CORRECTING DEVICE ERROR RADIUS ESTIMATES IN POSITIONING SYSTEMS

• US 20130342401A1
• Filed: 06/22/2012
• Published: 12/26/2013
• Est. Priority Date: 06/22/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lin, Jyh-Han, DiAcetis, Stephen P., Song, Yong, Letchner, Julia Maureen
• Granted Patent: US 9,651,654 B2
• Time in Patent Office: Days
• US Class Current: 342/451
• CPC Class Codes: G01S 1/00 Beacons or beacon systems transmitting signals having a characteristic or characteristics capable of being detected by non-directional receivers and defining directions, positions, or position lines fixed relatively to the beacon transmitters; Receivers co-operating therewith position fixing by co-ordinating a plurality of determinations of direction or position lines G01S5/00
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/0242 Determining the position of transmitters to be subsequently used in positioning G01S5/0289 takes precedence
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence

Abstract

Embodiments adjust device error radiuses associated with inferred device positions produced by positioning systems. Inferred beacon positions and associated beacon radiuses are accessed for beacons in a beacon fingerprint from an observing computing device. The beacon radiuses are associated with a pre-defined confidence level (e.g., an in-circle percentage). A Kalman filter is applied to at least one of the beacons using the inferred beacon positions and the beacon radiuses associated therewith to infer a device position for the computing device and to compute a device error radius for the inferred device position. The computed device error radius is adjusted as a function of the quantity of beacons input to the Kalman filter to achieve the pre-defined confidence level.

Claims

1. A system for adjusting computed device error radiuses associated with inferred device positions, said system comprising:

a memory area storing a plurality of positioned observations each including at least a set of beacons observed by one of a plurality of computing devices, the plurality of positioned observations including training positioned observations and test positioned observations, the memory area further storing a plurality of beacon positions inferred from the training positioned observations and storing a plurality of minimum beacon radiuses achieving a pre-defined confidence level, the plurality of minimum beacon radiuses being estimated by comparing the inferred beacon positions with the test positioned observations; and

a processor programmed to;

receive data representing a set of beacons from a mobile computing device, said beacons being observed by the mobile computing device;

obtain, from the plurality of inferred beacon positions stored in the memory area, a beacon position for each of the beacons in the set of beacons in the received data;

for each of the obtained, inferred beacon positions, obtain a minimum beacon radius from the plurality of minimum beacon radiuses stored in the memory area to achieve the pre-defined confidence level;

apply a Kalman filter to one or more of the beacons observed by the mobile computing device using the inferred beacon positions and the obtained minimum beacon radiuses for said one or more of the beacons, wherein applying the Kalman filter infers a device position for the mobile computing device and computes a device error radius for the inferred device position; and

adjust the computed device error radius as a function of a quantity of said one or more of the beacons input to the Kalman filter to achieve the pre-defined confidence level.

2. The system of claim 1, wherein the processor is further programmed to compare the inferred beacon positions with the test positioned observations by calculating a distance therebetween.

3. The system of claim 1, wherein the processor is further programmed to estimate the minimum beacon radius for one of the beacons in the received data by generating an error distance histogram based on the comparison between the inferred beacon position and the test positioned observations stored in the memory area.

4. The system of claim 3, wherein the processor is further programmed to select the minimum beacon radius from the generated error distance histogram as a function of observation counts for the one of the beacons and the pre-defined confidence level, the observation counts being stored in the training positioned observations in the memory area.

5. The system of claim 3, wherein the processor is further programmed to filter the beacons from the set of beacons in the received data by removing correlated beacons, the correlated beacons having substantially the same inferred beacon positions.

6. The system of claim 1, wherein the pre-defined confidence level represents a percentage within a circle having the adjusted, computed device error radius.

7. The system of claim 1, further comprising means for pre-processing data input to the Kalman filter and post-processing data output from the Kalman filter to adjust the computed device error radius to achieve the pre-defined confidence level.

8. A method comprising:

receiving data representing a set of beacons from a computing device, said beacons being observed by the computing device;

accessing beacon reference data to access an inferred beacon position for each of the beacons in the set of beacons and to access a minimum beacon radius for each of the inferred beacon positions to achieve a pre-defined confidence level;

applying a Kalman filter to one or more of the beacons using the inferred beacon positions and the minimum beacon radiuses for said one or more of the beacons, wherein applying the Kalman filter infers a device position for the computing device and computes a device error radius for the inferred device position; and

adjusting the computed device error radius as a function of a quantity of said one or more of the beacons input to the Kalman filter to achieve the pre-defined confidence level.

9. The method of claim 8, wherein adjusting the computed device error radius comprises accessing an error radius adjustment coefficient table.

10. The method of claim 8, wherein adjusting the computed device error radius comprises selecting an adjustment coefficient value as a function of a quantity of said one or more of the beacons input to the Kalman filter.

11. The method of claim 10, further comprising applying the selected adjustment coefficient value to the computed device error radius.

12. The method of claim 10, further comprising computing a plurality of the adjustment coefficient values from the beacon reference data by:

partitioning the beacon reference data into a training dataset and a test dataset;

constructing a beacon model for each of the beacons in the set of beacons using the training dataset; and

comparing the test dataset against the constructed beacon models.

13. The method of claim 12, wherein constructing the beacon models comprises inferring the beacon position for each of the beacons in the set of beacons.

14. The method of claim 8, further comprising filtering the set of beacons to remove correlated beacons.

15. The method of claim 8, wherein receiving the data comprises receiving, by a positioning service, the data from an observing computing device.

16. The method of claim 8, wherein the receiving, the accessing, the applying, and the adjusting are performed by one or more of the following:

a mobile computing device and a cloud service.

17. One or more computer storage media embodying computer-executable components, said components comprising:

an interface component that when executed causes at least one processor to receive data representing a set of beacons from a computing device, said beacons being observed by the computing device;

a beacon store component that when executed causes at least one processor to access beacon reference data to infer a beacon position for each of the beacons in the set of beacons;

a beacon radius component that when executed causes at least one processor to determine a minimum beacon radius for each of the inferred beacon positions to achieve a pre-defined confidence level;

a refiner component that when executed causes at least one processor to apply a Kalman filter to one or more of the beacons using the inferred beacon positions and the determined minimum beacon radiuses for said one or more of the beacons, wherein applying the Kalman filter infers a device position for the computing device and computes a device error radius for the inferred device position; and

a coefficient component that when executed causes at least one processor to adjust the computed device error radius as a function of a quantity of said one or more of the beacons input to the Kalman filter to achieve the pre-defined confidence level,

wherein the interface component further executes to provide the inferred device position and the adjusted, computed device error radius to the computing device.

18. The computer storage media of claim 17, wherein the pre-defined confidence level corresponds to an in-circle percentage.

19. The computer storage media of claim 17, wherein the refiner component further filters the set of beacons to remove correlated beacons having substantially the same inferred beacon positions.

20. The computer storage media of claim 17, wherein the coefficient component adjusts the computed device error radius by multiplying the computed device error radius by a coefficient value selected as a function of the quantity of said one or more of the beacons input to the Kalman filter