Systems and methods for performing a multi-step process for map generation or device localizing

Patent metadata

Field	Value
Publication number	US-9459104-B2
Application number	US-201414444072-A
Country	US
Kind code	B2
Filing date	Jul 28, 2014
Priority date	Jul 28, 2014
Publication date	Oct 4, 2016
Grant date	Oct 4, 2016

Abstract

Examples describe systems and methods for performing a multi-step approach for map generation and device localizing using data collected by the device and observations of interdependencies between the data. An example method includes receiving logs of data collected by the device, determining a constraint for locations of the device according to a comparison of data in the logs of data with available known signal strength maps of corresponding data, and performing a first simultaneous localization and mapping (SLAM) optimization of location estimates of the device using the logs of data and the constraint as a first initialization. A second SLAM optimization is performed using outputs of the first SLAM optimization and relative estimates of the device based on dead reckoning as a second initialization. An output location estimate of the device is provided based on the second SLAM optimization.

First claim

What is claimed is:

1. A method comprising:
receiving logs of data, wherein respective data is collected by a device over a plurality of locations and over a time period;
determining first location estimates of the device according to a comparison of data available in the logs of data with available known signal strength maps of corresponding data, wherein the first location estimates indicate a trajectory of the device over the time period;
determining, by one or more processors, second location estimates of the device using the first location estimates and relative position estimates of the device based on dead reckoning, wherein the relative position estimates of the device based on dead reckoning link together data points within the first location estimates considered to be consecutive location estimates of the device, wherein the second location estimates indicate a refined trajectory of the device over the time period;
determining output location estimates of the device using the second location estimates, the relative position estimates based on dead reckoning, and the respective data, wherein the output location estimates indicate a further refined trajectory of the device over the time period; and
generating maps of the plurality of locations based on the output location estimates of the device and the logs of data, wherein the maps include one or more of a map of WiFi received signal strength indications (RSSI), a map of magnetic fields, a geographical map of pathways, and a map of GPS visibility.

2. The method of claim 1 , wherein the logs of data include one or more of information indicative of received signal strength for a wireless network at a given location and at a given time period, GPS positioning data, magnetic field data, accelerometer data, and gyroscope data.

3. The method of claim 1 , wherein determining the first location estimates comprises:
based on the logs of data, determining possible locations of the device for instances when a wireless network signal has been observed from a wireless network;
comparing the wireless network signal to a map of wireless signal strength for the wireless network;
determining a measurement probability map in which a given wireless signal strength corresponds to a signal strength of the wireless network signal; and
using the measurement probability map to determine the first location estimates of the device.

4. The method of claim 3 , wherein determining the measurement probability map in which the given wireless signal strength corresponds to the signal strength of the wireless network signal comprises:
determining a first radius indicating a first distance away from an access point in the wireless network for which the signal strength is associated;
determining a second radius indicating a second distance away from the access point in the wireless network for which the signal strength is associated; and
determining the measurement probability map to have a first perimeter defined by the first radius and a second perimeter defined by the second radius.

5. The method of claim 1 , wherein determining the first location estimates for locations of the device comprises:
based on the logs of data, determining by the one or more processors possible locations of the device for instances when a Bluetooth wireless signal has been observed;
comparing the Bluetooth wireless signal to a map of Bluetooth devices;
determining a measurement probability map in which a given Bluetooth wireless signal is estimated to be received; and
using the measurement probability map to determine the first location estimates of the device.

6. The method of claim 1 , wherein determining the first location estimates for locations of the device comprises:
based on the logs of data, determining by the one or more processors possible locations of the device for instances when a magnetic field signal has been collected;
comparing the magnetic field signal to a map of magnetic field signal strength for a given location of the plurality of locations;
determining a measurement probability map in which a given magnetic field signal strength corresponds to a signal strength of the magnetic field signal; and
using the measurement probability map to determine the first location estimates of the device.

7. The method of claim 1 , wherein determining one or more of the first location estimates, the second location estimates, and the output location estimates comprises performing a simultaneous localization and mapping (SLAM) optimization.

8. The method of claim 7 , wherein performing the SLAM optimization comprises performing a GraphSLAM optimization.

9. The method of claim 1 , wherein determining the first location estimates comprises performing a simultaneous localization and mapping (SLAM) optimization of location estimates of the device using the logs of data without using given relative position estimates of the device based on dead reckoning.

10. The method of claim 9 , wherein performing the SLAM optimization of location estimates of the device comprises using an artificial area in the map where the respective data is estimated to be collected, and the method further comprises:
performing one or more additional SLAM optimizations using the output location estimates, the relative position estimates of the device based on dead reckoning, and replacing the artificial area with the respective data.

11. A non-transitory computer readable memory having stored therein instructions, that when executed by one or more processors, cause the one or more processors to perform functions comprising:
receiving logs of data, wherein respective data is collected by a device over a plurality of locations and over a time period;
determining a constraint for locations of the device according to a comparison of data available in the logs of data with available known signal strength maps of corresponding data;
performing a first simultaneous localization and mapping (SLAM) optimization of location estimates of the device using the logs of data and the constraint as a first initialization;
based on the first SLAM optimization, providing a first location estimate of the device over the time period, wherein the first location estimate indicates a trajectory of the device over the time period;
performing a second SLAM optimization of the location estimates of the device using the first location estimate and relative position estimates of the device based on dead reckoning as a second initialization;
based on the second SLAM optimization, providing an output location estimate of the device over the time period; and
generating maps of the plurality of locations based on the output location estimate of the device and the logs of data, wherein the maps include one or more of a map of WiFi received signal strength indications (RSSI), a map of magnetic fields, a geographical map of pathways, and a map of GPS visibility.

12. The non-transitory computer readable memory of claim 11 , wherein determining the constraint for locations of the device comprises:
based on the logs of data, determining by the one or more processors possible locations of the device for instances when a wireless network signal has been observed from a wireless network;
comparing the wireless network signal to a map of wireless signal strength for the wireless network;
determining a measurement probability map in which a given wireless signal strength corresponds to a signal strength of the wireless network signal; and
using the measurement probability map as the constraint for locations of the device.

13. The non-transitory computer readable memory of claim 11

Assignees

• Google Inc

Inventors

• Le Grand Etienne

Classifications

• G01C21/12 Primary

  executed aboard the object being navigated; Dead reckoning · CPC title

• G01C21/14 Primary

  by recording the course traversed by the object (G01C21/16 takes precedence) · CPC title