Systems and methods for graph-based localization and mapping

• US 10,075,818 B2
• Filed: 09/13/2017
• Issued: 09/11/2018
• Est. Priority Date: 09/13/2016
• Status: Active Grant

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Le Grand, Etienne, Khider, Mohammed, Bruno, Luigi
• Primary Examiner(s): Taylor, Nathan
• Application Number:
  US15/703,779
• Publication Number:
  US 20180077534A1
• Time in Patent Office: 363 Days
• Field of Search: 4554561-4566
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/30 Services specially adapted for particular environments, situations or purposes
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

Traces are collected by multiple portable devices moving with an area that includes an indoor region, with each of the traces including measurements of wireless signals at different times, including measurements of wireless signals from signal sources disposed within the area. A motion map for the geographic area is constructed by determining, for each of the cells that make the motion map, respective probabilities of moving in various directions relative to each cell. Location estimates for the portable devices and the signal sources are generated using graph-based SLAM optimization of the location estimates. The graph-based SLAM optimization includes determining to which of the cells of the motion map the location estimate corresponds and applying the measurements of wireless signals sources and the set of probabilities of the cells as a first constraint and a second constraint, respectively, in the graph-based SLAM optimization.

Claims

1. A method of performing simultaneous localization and mapping (SLAM) optimization, the method comprising:

receiving, by one or more processors, traces collected by multiple portable devices moving within a geographic area that includes an indoor region, each of the traces including measurements of wireless signals sources at different times by a same device;

determining, for each of a plurality of cells in the geographic area, respective probabilities of moving in various directions relative to the cell, the plurality of cells defining a motion map for the geographic area; and

generating, by the one or more processors, location estimates for the portable devices and the signal sources using graph-based SLAM optimization of the location estimates, including, for at least some of the location estimates;

determining to which of the plurality of cells of the motion map the location estimate corresponds, and

applying the measurements of wireless signals sources and the set of probabilities of the cells as a first constraint and a second constraint, respectively, in the graph-based SLAM optimization.

2. The method of claim 1, wherein applying the second constraint includes, for each of the traces:

defining a plurality of directed segments in accordance with a size of each of the cells, and

applying the second constraint to each of the plurality of directed segments.

3. The method of claim 1, wherein determining the respective probabilities of moving in various directions relative to the cell includes determining, for each of the various directions D_i, a respective probability of moving in the direction D given that the cell was reached from direction D_j.

4. The method of claim 1, further comprising:

identifying several of the traces have a same direction, and

applying a third constraint to the identified traces to bias the traces toward each other.

5. The method of claim 1, further comprising:

receiving, by the one or more processors, floorplan data indicative of at least external wall geometry for the area;

determining signed distances between at least some of the location estimates and respective points in the external wall geometry; and

applying the signed distances as a third constraint in the graph-base SLAM optimization.

6. The method of claim 5, wherein generating the location estimates includes constraining the locations of the signal sources to the indoor region.

7. The method of claim 5, wherein generating the location estimates includes:

generating an attenuation factor for the signal sources disposed within the area using the external wall geometry, and

applying the attenuation factor as a measurement prior in the graph-based SLAM optimization, the measurement prior corresponding to a probability independent of the location estimates.

8. A computing system configured to perform simultaneous localization and mapping (SLAM) optimization, the computing system comprising:

processing hardware; and

a non-transitory computer-readable medium storing thereon instructions that, when executed by the processing hardware, cause the system to;

receive traces collected by multiple portable devices moving within a geographic area that includes an indoor region, each of the traces including measurements of wireless signals sources at different times by a same device,

determine, for each of a plurality of cells in the geographic area, respective probabilities of moving in various directions relative to the cell, the plurality of cells defining a motion map for the geographic area,

generate location estimates for the portable devices and the signal sources using graph-based SLAM optimization of the location estimates, including, for at least some of the location estimates;

determine to which of the plurality of cells of the motion map the location estimate corresponds, and

apply the measurements of wireless signals sources and the set of probabilities of the cells as a first constraint and a second constraint, respectively, in the graph-based SLAM optimization.

9. The computing system of claim 8, wherein to apply the second constraint, the instructions cause the system to:

for each of the traces, define a plurality of directed segments in accordance with a size of the cells, and

apply the second constraint to each of the plurality of directed segments.

10. The computing system of claim 8, wherein the instructions cause the system to:

identify several of the traces that follow a same direction, and

apply a third constraint to the identified traces to bias the traces toward each other.

11. The computing system of claim 8, wherein the instructions cause the system to:

receive floorplan data indicative of at least external wall geometry for the area,

determine signed distances between at least some of the location estimates and respective points in the external wall geometry, and

apply the signed distances as a third constraint in the graph-based SLAM optimization.

12. The computing system of claim 11, wherein generating the location estimates includes constraining the locations of the signal sources to the indoor region.

13. The computing system of claim 11, wherein generating the location estimates includes:

generating an attenuation factor for the signal sources disposed within the area using the external wall geometry, and

applying the attenuation factor as a measurement prior in the graph-based SLAM optimization, the measurement prior corresponding to a probability independent of the location estimates.

14. The computing system of claim 13, wherein generating the location estimates includes constraining the locations of the signal sources to the indoor region.

15. The computing system of claim 13, wherein generating the location estimates includes:

generating an attenuation factor for the signal sources disposed within the area using the external wall geometry, and

applying the attenuation factor as a measurement prior in the graph-based SLAM optimization, the measurement prior corresponding to a probability independent of the location estimates.