Method and System for Signal-based Localization

• US 20130244688A1
• Filed: 11/13/2012
• Published: 09/19/2013
• Est. Priority Date: 11/11/2011
• Status: Active Grant

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Thrun, Sebastian, Huang, Joseph, Millman, David, Stavens, David
• Granted Patent: US 9,201,133 B2
• Time in Patent Office: Days
• US Class Current: 455/456.1
• CPC Class Codes: G01S 17/42 Simultaneous measurement of distance and other co-ordinates indirect measurement G01S17/46
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 2205/02 Indoor
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

In an embodiment of the present invention, a GraphSLAM-like algorithm for signal strength SLAM is presented. This algorithm as an embodiment of the present invention shares many of the benefits of Gaussian processes yet is viable for a broader range of environments since it makes no signature uniqueness assumptions. It is also more tractable to larger map sizes, requiring O(N²) operations per iteration. In the present disclosure, an algorithm according to an embodiment of the present invention is compared to a laser-SLAM ground truth, showing that it produces excellent results in practice.

Claims

1. A computer-implemented method for localization using signal-strength measurements, comprising:

obtaining a set of signal-strength measurements;

performing simultaneous localization and mapping computations on the set of signal-strength measurements,

wherein the simultaneous and localization mapping computations make no assumptions on signature uniqueness; and

computing a location from the simultaneous localization and mapping computations.

2. The computer-implemented method of claim 1, wherein the signal-strength measurements are from signal sources.

3. The computer-implemented method of claim 1, wherein the signal sources are WiFi sources.

4. The computer-implemented method of claim 2, wherein a geographic distribution of signal sources is sparse.

5. The computer-implemented method of claim 2, wherein substantially similar signal strength measurements are from different signal sources.

6. The computer-implemented method of claim 1, further comprising receiving motion measurements.

7. The computer-implemented method of claim 1, wherein computing the location is performed using and O(N²) computer operations, where N is a dimensionality of a state space.

8. The computer-implemented method of claim 1, further comprising interpolating signal-strength measurements.

9. The computer-implemented method of claim 8, wherein signal sources for the interpolated signal-strength measurements are separated by free space.

10. The computer-implemented method of claim 1, further comprising computing a map from a plurality of computed locations.

11. A computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to implement a method for localization using signal-strength measurements, comprising:

obtaining a set of signal-strength measurements;

performing simultaneous localization and mapping computations on the set of signal-strength measurements,

wherein the simultaneous and localization mapping computations make no assumptions on signature uniqueness; and

computing a location from the simultaneous localization and mapping computations.

12. The computer-readable medium of claim 11, wherein the signal-strength measurements are from signal sources.

13. The computer-readable medium of claim 11, wherein the signal sources are WiFi sources.

14. The computer-readable medium of claim 12, wherein a geographic distribution of signal sources is sparse.

15. The computer-readable medium of claim 12, wherein substantially similar signal strength measurements are from different signal sources.

16. The computer-readable medium of claim 11, further comprising receiving motion measurements.

17. The computer-readable medium of claim 11, wherein computing the location is performed using and O(N²) computer operations, where N is a dimensionality of a state space.

18. The computer-readable medium of claim 11, further comprising interpolating signal-strength measurements.

19. The computer-readable medium of claim 18, wherein signal sources for the interpolated signal-strength measurements are separated by free space.

20. The computer-readable medium of claim 11, further comprising computing a map from a plurality of computed locations.

21. A computing device comprising:

a data bus;

a memory unit coupled to the data bus;

at least one processing unit coupled to the data bus and configured to obtain a set of signal-strength measurements;

perform simultaneous localization and mapping computations on the set of signal-strength measurements,

wherein the simultaneous and localization mapping computations make no assumptions on signature uniqueness; and

compute a location from the simultaneous localization and mapping computations.