Determining and aligning a position of a device and a position of a wireless access point (AP)

Patent metadata

Field	Value
Publication number	US-9544871-B2
Application number	US-201414509189-A
Country	US
Kind code	B2
Filing date	Oct 8, 2014
Priority date	Feb 14, 2014
Publication date	Jan 10, 2017
Grant date	Jan 10, 2017

Abstract

Examples describe systems and methods for iteratively determining a signal strength map for a wireless access point (AP) aligned to position coordinates, positions of a device, and positions of the wireless APs. An example method includes selecting traces and a wireless AP among the traces for which data is indicative of a threshold amount of information to estimate a position of the device and a position of the wireless AP, selecting first characteristics from the traces to remain constant and second characteristics to be variable, and selecting a localization constraint that provides boundaries on the position of the device and the position of the wireless AP. The method also includes performing a simultaneous localization and mapping (SLAM) optimization of the position of the device and the position of the wireless AP based on the localization constraint with the first characteristics held constant and the second characteristics allowed to vary.

First claim

What is claimed is:

1. A method comprising:
receiving traces of data, wherein respective data is collected by sensors of a device over a plurality of locations and over time periods, and wherein a respective trace of data includes received signal strength indication (RSSI) data for a plurality of wireless access points (AP);
selecting, by one or more processors, a set of traces and a given wireless AP among the traces of data for which data is indicative of a threshold amount of information to estimate a position of the device over the time periods and a position of the given wireless AP;
selecting first characteristics from the set of traces to remain constant and second characteristics from the set of traces to be variable;
selecting a localization constraint that provides one or more boundaries on the position of the device over the time periods and the position of the given wireless AP;
performing, by the one or more processors, a simultaneous localization and mapping (SLAM) optimization of the position of the device and the position of the given wireless AP, over a plurality of iterations, based on the localization constraint with the first characteristics held constant and the second characteristics allowed to vary;
for the plurality of iterations, (i) selecting the set of traces based on the traces of data having an amount of GPS positioning data being less than a given amount of GPS positioning data in a previously selected set of traces, and (ii) performing the SLAM optimization based on the selected set of traces; and
based on the iterative optimizations, providing an estimate of the position of the device over the time periods and an estimate of the position of the given wireless AP.

2. The method of claim 1 , wherein selecting, by one or more processors, the set of traces and the given wireless AP among the traces of data for which data is indicative of the threshold amount of information to estimate the position of the device over the time periods and the position of the given wireless AP comprises:
selecting the set of traces based on a floor of a building on which the device traverses as indicated by data in the traces.

3. The method of claim 1 , wherein selecting, by one or more processors, the set of traces and the given wireless AP among the traces of data for which data is indicative of the threshold amount of information to estimate the position of the device over the time periods and the position of the given wireless AP comprises:
selecting the given wireless AP based on a given time period of accessibility of the given wireless AP exceeding a threshold.

4. The method of claim 1 , wherein selecting, by one or more processors, the set of traces and the given wireless AP among the traces of data for which data is indicative of the threshold amount of information to estimate the position of the device over the time periods and the position of the given wireless AP comprises:
selecting the set of traces based on accelerometer or gyroscope data in the traces indicating an average rotation of the device per step being less than a step threshold.

5. The method of claim 1 , wherein selecting, by one or more processors, the set of traces and the given wireless AP among the traces of data for which data is indicative of the threshold amount of information to estimate the position of the device over the time periods and the position of the given wireless AP comprises:
selecting the set of traces based on whether GPS data in the traces and relative position estimates of the device based on dead reckoning are matching.

6. The method of claim 1 , wherein selecting, by one or more processors, the set of traces and the given wireless AP among the traces of data for which data is indicative of the threshold amount of information to estimate the position of the device over the time periods and the position of the given wireless AP comprises:
selecting the set of traces based on a number of GPS readings in the traces.

7. The method of claim 1 , wherein selecting, by one or more processors, the set of traces and the given wireless AP among the traces of data for which data is indicative of the threshold amount of information to estimate the position of the device over the time periods and the position of the given wireless AP comprises:
selecting the set of traces based on a number of magnetometer data in the traces.

8. The method of claim 1 , wherein selecting, by one or more processors, the set of traces and the given wireless AP among the traces of data for which data is indicative of the threshold amount of information to estimate the position of the device over the time periods and the position of the given wireless AP comprises:
selecting the set of traces based on an amount of time between relative position estimates of the device per step.

9. The method of claim 1 , wherein selecting the first characteristics from the set of traces to remain constant comprises selecting relative position estimates of the device based on dead reckoning to remain constant.

10. The method of claim 1 , wherein selecting the first characteristics from the set of traces to remain constant comprises selecting positions of the plurality of wireless access points (AP) as seen in the traces to remain constant.

11. The method of claim 1 , wherein selecting the localization constraint that provides one or more boundaries on the position of the device over the time periods and the position of the given wireless AP comprises selecting GPS data in the traces as the localization constraint.

12. The method of claim 1 , wherein selecting the localization constraint that provides one or more boundaries on the position of the device over the time periods and the position of the given wireless AP comprises selecting GPS data and relative position estimates of the device based on dead reckoning as the localization constraint.

13. The method of claim 1 , wherein performing the SLAM optimization of the position of the device and the position of the given wireless AP comprises:
performing a non-linear least squares optimization of possible locations of the device and of the given wireless AP by reducing a square error between the possible locations of the device and of the given wireless AP due to observed GPS positioning data and RSSI.

14. The method of claim 1 , wherein performing the SLAM optimization comprises performing the SLAM optimization over the plurality of iterations on growing subsets of localization constraints for determination of an optimal estimate of the position of the device over the time periods and an optimal estimate of the position of the given wireless AP based on the received traces of data from the devices.

15. The method of claim 14 , further comprising:
for a first iteration, selecting a first set of traces based on an amount of GPS positioning data in the traces exceeding a count threshold; and
for the first set of traces,
aligning a path of the device based on relative position estimates of the device due to dead reckoning to GPS positioning data of the first set of trace so as to provide a relative path of the device;
aligning given RSSI for the given wireless AP to the relative path of the device, for a given trace in the first set, based on data collection times so as to provide initial signal strength maps for the given wireless AP;
performing a first optimization of possible locations of the given wireless AP based on the initial signal strength map for the given wireless AP with the relative path of the device held constant; and
based on the first optimization, providing a first signal strengt

Assignees

• Google Inc

Inventors

• Le Grand Etienne
• Williams Brian Patrick

Classifications

• G01S5/02522

  The radio-map containing measured values of non-radio values · CPC title

• H04W88/08

  Access point devices · CPC title

• H04W64/006

  with additional information processing, e.g. for direction or speed determination · CPC title

• H04W64/003 Primary

  locating network equipment · CPC title

• H04W4/33

  for indoor environments, e.g. buildings · CPC title