POSITIONING AND MAPPING BASED ON VIRTUAL LANDMARKS

• US 20140195149A1
• Filed: 01/10/2013
• Published: 07/10/2014
• Est. Priority Date: 01/10/2013
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Lei Yang, Yang Xue
• Inventors: YANG, Xue, YANG, Lei
• Granted Patent: US 9,677,890 B2
• Time in Patent Office: Days
• US Class Current: 701/445
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

This disclosure is directed to positioning and mapping based on virtual landmarks. A space may include a plurality of signal sources (e.g., wireless access points (APs), cellular base stations, etc.). The space may be virtually divided into a plurality of regions, wherein each region in the space may be associated with a virtual landmark. Virtual landmarks may be identified by a signature comprised of measurements of wireless signals received from the plurality of access points when at the associated region. A device position may be approximated based on signal power magnitude and variance measurements for wireless signals received at the virtual landmark. Devices may employ an algorithm such as, for example, Simultaneous Localization and Mapping (SLAM) for positioning and map creation in the space without the need for GPS signals, specialized signaling equipment, pre-navigation device training, etc. Navigation/mapping may also account for space changes, signal source position changes, etc.

Claims

1. A device, comprising:

a communication module to at least receive wireless signals; and

a processing module to determine at least one virtual landmark in a space based on the received wireless signals, to generate a map for use in navigating the space based on the at least one virtual landmark, and to navigate within the space based on the generated map.

2. The device of claim 1, wherein the communication module is to receive short-range wireless communication signals from a plurality of radio signal sources within the space.

3. The device of claim 2, wherein the space is virtually divided into a plurality of regions, each of the plurality of the regions being associated with a virtual landmark.

4. The device of claim 3, wherein each virtual landmark associated with a region in the space is identified by a signature comprising measurements of signal power magnitude and variance in the wireless signals received from each of the plurality of signal sources within the space.

5. The device of claim 4, wherein the measured power magnitude and variance of the wireless signals is based on Received Signal Strength Indication (RSSI).

6. The device of claim 1, wherein the processing module is to generate the map and navigate using a Simultaneous Localization and Mapping (SLAM) algorithm.

7. The device of claim 6, wherein the SLAM algorithm uses detection of virtual landmarks to correct device pose estimations.

8. The device of claim 7, wherein generating the map comprises the processing module being to generate a provisional map based on the virtual landmarks, to determine whether the virtual landmarks were previously visited, and to update a permanent map to update the signature for at least one existing virtual landmark or to add at least one new virtual landmark based on the determination.

9. The device of claim 8, wherein navigating within the space based on the map comprises the processing module being further to update particle weights for the virtual landmarks based on the measured signatures for the virtual landmarks compared to the signatures recorded in the permanent or provisional maps.

10. The device of claim 9, wherein the processing module is further to determine whether any radio signal sources at a new pose have changed position based on the updated particle weights being substantially similar.

11. The device of claim 10, wherein determining whether any radio signal sources at the new pose have changed position comprises the processing module being further to observe if signal power magnitude changes accumulated over all particles for any radio signal source is substantially higher than signal power magnitude changes accumulated over all particles for other radio signal sources.

12. The device of claim 10, wherein the processing module is further to remove from signatures of the virtual landmarks the signal measurements corresponding to any source of wireless signals whose position was determined to have changed.

13. A method, comprising:

determining that a device has changed position;

estimating the position of the device within a space by determining virtual landmarks associated with regions within a plurality of regions into which the space is virtually divided;

updating a map of the space in the device based on the determined virtual landmarks; and

navigating within the space based on the map.

14. The method of claim 13, wherein determining the device has changed position comprises sensing a position change in the device based on inertial sensors within the device.

15. The method of claim 13, wherein estimating the position of the device comprises determining a new pose for particles corresponding to possible positions of the device within the space in accordance with a Simultaneous Localization and Mapping (SLAM) algorithm.

16. The method of claim 15, further comprising updating virtual landmark estimates based on signal power magnitude and variance measurements of wireless signals received at the new pose, the wireless signal measurements forming a signature by which virtual landmarks are identified.

17. The method of claim 16, wherein updating the map comprises generating a provisional map based on the virtual landmarks, determining whether the virtual landmarks were previously visited, and updating a permanent map to update the signature for at least one existing virtual landmark or to add at least one new virtual landmark based on the determination.

18. The method of claim 17, wherein navigating within the space based on the map comprises updating particle weights for the virtual landmarks based on the measured signatures for the virtual landmarks compared to the signatures recorded in the permanent or provisional maps.

19. The method of claim 18, further comprising determining whether any radio signal sources at the new pose have changed position based on the updated particle weights being substantially similar.

20. The method of claim 19, wherein determining whether any radio signal sources at the new pose have changed position comprises observing if signal power magnitude changes accumulated over all particles for any radio signal source is substantially higher than signal power magnitude changes accumulated over all particles for other radio signal sources.

21. The method of claim 19, further comprising removing from the signatures of the virtual landmarks the signal measurements corresponding to any source of wireless signals whose position was determined to have changed.

22. At least one machine-readable storage medium having stored thereon, individually or in combination, instructions that when executed by one or more processors result in the following operations comprising:

determining that a device has changed position;

estimating the position of the device within a space by determining virtual landmarks associated with regions within a plurality of regions into which the space is virtually divided;

updating a map of the space in the device based on the determined virtual landmarks; and

navigating within the space based on the map.

23. The medium of claim 22, wherein determining the device has changed position comprises sensing a position change in the device based on inertial sensors within the device.

24. The medium of claim 22, wherein estimating the position of the device comprises determining a new pose for particles corresponding to possible positions of the device within the space in accordance with a Simultaneous Localization and Mapping (SLAM) algorithm.

25. The medium of claim 24, further comprising instructions that when executed by one or more processors result in the following operations comprising:

updating virtual landmark estimates based on signal power magnitude and variance measurements of wireless signals received at the new pose, the wireless signal measurements forming a signature by which virtual landmarks are identified.

26. The medium of claim 25, wherein updating the map comprises generating a provisional map based on the virtual landmarks, determining whether the virtual landmarks were previously visited, and updating a permanent map to update the signature for at least one existing virtual landmark or to add at least one new virtual landmark based on the determination.

27. The medium of claim 26, wherein navigating within the space based on the map comprises updating particle weights for the virtual landmarks based on the measured signatures for the virtual landmarks compared to the signatures recorded in the permanent or provisional maps.

28. The medium of claim 27, further comprising instructions that when executed by one or more processors result in the following operations comprising:

determining whether any sources of the wireless signals received at the new pose have changed position based on the updated particle weights being substantially equal.

29. The medium of claim 28, wherein determining whether any radio signal sources at the new pose have changed position comprises observing if signal power magnitude changes accumulated over all particles for any radio signal source is substantially higher than signal power magnitude changes accumulated over all particles for other radio signal sources.

30. The medium of claim 28, further comprising instructions that when executed by one or more processors result in the following operations comprising:

removing from the signatures of the virtual landmarks the signal measurements corresponding to any source of wireless signals whose position was determined to have changed.