Systems and methods for graph-based localization and mapping

• US 10,356,562 B2
• Filed: 09/10/2018
• Issued: 07/16/2019
• Est. Priority Date: 09/13/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Le Grand, Etienne, Khider, Mohammed, Bruno, Luigi
• Primary Examiner(s): Taylor, Nathan S
• Application Number:
  US16/126,905
• Publication Number:
  US 20190007800A1
• Time in Patent Office: 309 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 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, and at least some of the traces including pseudorange measurements related to distances to respective satellites. Location estimates for the portable devices and the signal sources are generated using graph-based SLAM optimization of the location estimates. More particularly, constraints for the pseudorange measurements are generated and applied for the pseudorange measurements in 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, and at least some of the traces including pseudorange measurements related to distances to respective satellites; 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;

generating constraints for the pseudorange measurements, and

applying the generated constraints for the pseudorange measurements in graph-based SLAM optimization.

2. The method of claim 1, wherein generating constraints for the pseudorange measurements includes separately estimating a time parameter and at least one coordinate parameter.

3. The method of claim 2, wherein generating the constraints for the pseudorange measurements includes separately estimating the time parameter and each of x, y, and z coordinates.

4. The method of claim 1, wherein at least some of the pseudorange measurements include measurements from less than a minimum number of satellites necessary to generate a position fix.

5. The method of claim 1, further comprising generating smoothness constrains between time estimates of consecutive pseudorange measurements, to model clock drift.

6. The method of claim 1, wherein at least some of the traces include measurements of wireless signals from access points of wireless local area networks, and wherein generating the location estimates includes generating constraints for the measurements of the wireless signals from the access points.

7. 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.

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, and at least some of the traces including pseudorange measurements related to distances to respective satellites,

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;

generate constraints for the pseudorange measurements, and

apply the generated constraints for the pseudorange measurements in graph-based SLAM optimization.

9. The computing system of claim 8, wherein to generate the constraints for the pseudorange measurements, the instructions further cause the system to separately estimate a time parameter and at least one coordinate parameter.

10. The computing system of claim 9, wherein to generate the constraints for the pseudorange measurements, the instructions further cause the system to separately estimate the time parameter and each of x, y, and z coordinates.

11. The computing system of claim 8, wherein at least some of the pseudorange measurements include measurements from less than a minimum number of satellites necessary to generate a position fix.

12. The computing system of claim 8, wherein the instructions further cause the system to generate smoothness constrains between time estimates of consecutive pseudorange measurements, to model clock drift.

13. The computing system of claim 8, wherein at least some of the traces include measurements of wireless signals from access points of wireless local area networks, and wherein to generate the location estimates, the instructions cause the system to generate constraints for the measurements of the wireless signals from the access points.

14. The computing system of claim 8, wherein the instructions further 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-base SLAM optimization.

15. A non-transitory computer-readable medium storing thereon instructions that, when executed by one or more processors, cause the one or more processors 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, and at least some of the traces including pseudorange measurements related to distances to respective satellites; and

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

generate constraints for the pseudorange measurements, and

apply the generated constraints for the pseudorange measurements in graph-based SLAM optimization.

16. The non-transitory computer-readable medium of claim 15, wherein to generate the constraints for the pseudorange measurements, the instructions further cause the one or more processors to separately estimate a time parameter and at least one coordinate parameter.

17. The non-transitory computer-readable medium of claim 16, wherein to generate the constraints for the pseudorange measurements, the instructions further cause the one or more processors to separately estimate the time parameter and each of x, y, and z coordinates.

18. The non-transitory computer-readable medium of claim 15, wherein at least some of the pseudorange measurements include measurements from less than a minimum number of satellites necessary to generate a position fix.

19. The non-transitory computer-readable medium of claim 15, wherein the instructions further cause the one or more processors to generate smoothness constrains between time estimates of consecutive pseudorange measurements, to model clock drift.

20. The non-transitory computer-readable medium of claim 15, wherein at least some of the traces include measurements of wireless signals from access points of wireless local area networks, and wherein to generate the location estimates, the instructions cause the one or more processors to generate constraints for the measurements of the wireless signals from the access points.