Locating a mobile computing device in an indoor environment

• US 9,310,462 B2
• Filed: 09/07/2012
• Issued: 04/12/2016
• Est. Priority Date: 09/07/2012
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Chintalapudi, Krishna, Padmanabhan, Venkata N., Rai, Anshul, Sen, Rijurekha, Sidhu, Gursharan Singh
• Primary Examiner(s): PATEL, MAHENDRA R
• Application Number:
  US13/606,008
• Publication Number:
  US 20140073345A1
• Time in Patent Office: 1,313 Days
• Field of Search: 455/456.1, 455/456.2, 370/338, 709/236, 709/219, 340/539.3, 340/686.1
• US Class Current: 1/1
• CPC Class Codes: G01C 21/1656 with passive imaging devices, e.g. cameras
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 22/006 Pedometers
• CPC Class Codes: G01S 5/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: G01S 5/0264 at least one of the systems being a non-radio wave positioning system
• CPC Class Codes: H04W 4/026 using orientation information, e.g. compass
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information

Abstract

Inferring location of a mobile computing device in an indoor environment and crowdsourcing radio frequency data are described herein. A location of the mobile computing device in the indoor environment is inferred based upon known physical constraints of the indoor environment and data from an inertial sensor of the mobile computing device, wherein an initial location in the indoor environment of the mobile computing device is unknown, a heading offset of the mobile computing device is arbitrary, and wherein a placement of the mobile computing device on a user is arbitrary.

Claims

1. A method, comprising:

receiving data pertaining to a mobile computing device that comprises an inertial sensor, the data comprising;

an initial reading from the inertial sensor in the mobile computing device, the initial reading obtained when the mobile computing device is at an initial location in an indoor environment, wherein the initial location is unknown; and

a plurality of readings from the inertial sensor, the plurality of readings obtained subsequent in time from when the initial reading was obtained, the plurality of readings from the inertial sensor obtained over a range of time as the mobile computing device transits along a path in the indoor environment beginning at the initial location; and

inferring at least one location along the path of the mobile computing device in the indoor environment based at least in part upon the initial reading and the plurality of readings, wherein inferring of the at least one location of the mobile computing device in the indoor environment comprises inferring a length of a stride of a user of the mobile computing device based upon the initial reading and the plurality of readings.

2. The method of claim 1, wherein an orientation of the mobile computing device relative to a direction of motion of the mobile computing device when transiting along the path is arbitrary, and wherein inferring the at least one location along the path of the mobile computing device further comprises inferring a heading offset of the mobile computing device, the heading offset being a difference in the orientation of the mobile computing device relative to the direction of motion of the mobile computing device.

3. The method of claim 1, wherein a position of the mobile computing device relative to a body of a user of the mobile computing device is arbitrary.

4. The method of claim 1, wherein the at least one location that is inferred is the initial location of the wireless computing device.

5. The method of claim 1, wherein the at least one location is a current location of the wireless computing device in the indoor environment.

6. The method of claim 1, further comprising inferring the path of the mobile computing device in the indoor environment by way of backpropagation, wherein the initial location is inferred based at least in part upon the inferring of the at least one location.

7. The method of claim 1, wherein the inferring of the at least one location of the mobile computing device in the indoor environment further comprises:

computing a shape of the path of the mobile computing device in the indoor environment;

comparing the shape of the path of the mobile computing device in the indoor environment with path boundaries specified in a map of the indoor environment; and

inferring the at least one location of the mobile computing device in the indoor environment based at least in part upon the comparing of the shape of the path of the mobile computing device in the indoor environment with the path boundaries specified in the map of the indoor environment.

8. The method of claim 1, wherein the readings are obtained over the range of time, and wherein the inferring is undertaken as the data is received.

9. The method of claim 1, wherein the inertial sensor is one of an accelerometer, a compass, or a gyroscope.

10. The method of claim 1, further comprising receiving signal strength values of respective wireless signals received at the mobile computing device over the range of time, the respective wireless signals received at the mobile computing device from wireless signal transmitters that are external to the mobile computing device, and wherein the method further comprises assigning at least one signal strength value to the at least one location based at least in part upon the inferring of the at least one location of the mobile computing device in the indoor environment.

11. The method of claim 1 being executed by the mobile computing device.

12. The method of claim 1, wherein the inferring of the at least one location of the mobile computing device in the indoor environment further comprises computing probability distributions of respective locations of the mobile computing device in the indoor environment as the mobile computing device transits along the path.

13. The method of claim 12, wherein the computing of the probability distributions of the respective locations of the mobile computing device in the indoor environment as the mobile computing device transits along the path comprises utilizing multi-dimensional particle filtering comprising a plurality of dimensions, wherein the plurality of dimensions comprises dimensions corresponding to physical location, a dimension corresponding to a stride length of a user of the mobile computing device, and a dimension corresponding to a heading offset of the mobile computing device.

14. A system, comprising:

a processor; and

memory that comprises instructions that, when executed by the processor, cause the processor to perform acts comprising;

receiving data generated by at least one inertial sensor in a mobile computing device, the mobile computing device residing in an indoor environment, and wherein the data comprises;

first data generated by the at least one inertial sensor when the mobile computing device is at an initial unknown location in the indoor environment, the initial unknown location being an arbitrary location in the indoor environment, and wherein the initial unknown location is indeterminable based solely upon the first data; and

second data generated by the at least one inertial sensor subsequent to the mobile computing device being at the initial unknown location in the indoor environment, the second data generated by the at least one inertial sensor during transit of the mobile computing device from the initial unknown location along a path;

estimating a length of a stride of a user of the mobile computing device based upon the second data generated by the at least one inertial sensor; and

inferring a geographic location of the initial unknown location of the mobile computing device in the indoor environment based at least in part upon the first data and the estimated length of the stride of the user.

15. The system of claim 14, the acts further comprising:

receiving a signal strength value for a signal transmitted by a wireless access point and received at the mobile computing device at a time corresponding to the first data; and

assigning the signal strength value to the geographic location subsequent to the geographic location of the initial unknown geographic location being inferred.

16. The system of claim 14, wherein inferring a geographic location of the initial unknown location of the mobile computing device in the indoor environment comprises inferring the geographic location of the initial unknown location of the mobile computing device based upon a comparison between the path of the mobile computing device and known physical constraints of the indoor environment.

17. The system of claim 14, the acts further comprising:

inferring a current geographic location of the mobile computing device in the indoor environment based at least in part upon the first data and the second data; and

causing a location-based alert to be presented to a user of the mobile computing device based at least in part upon the inferred current geographic location of the mobile computing device.

19. The system of claim 14, the at least one inertial sensor is one of an accelerometer, a compass, or a gyroscope.

20. The system of claim 14, wherein inferring the geographic location of the initial unknown location of the mobile computing device comprises:

eliminating infeasible travel paths in the indoor environment based upon known physical constraints of the indoor environment; and

inferring the geographic location of the initial unknown location of the mobile computing device based upon the infeasible travel paths being eliminated.

18. A computer-readable data storage device comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

receiving a first reading from an inertial sensor in a mobile computing device when the mobile computing device is at an initial unknown location in an indoor environment, the initial unknown location being an arbitrary location in the indoor environment, and wherein the initial, unknown location is indeterminable based solely upon the first reading;

receiving a plurality of readings from the inertial sensor in the mobile computing device when the mobile computing device is transiting in the indoor environment, the plurality of readings obtained from inertial sensor subsequent to the first reading being obtained from the inertial sensor;

jointly inferring a length of a stride of a user of the mobile computing device, a heading offset of the mobile computing device, and a current location of the mobile computing device based at least in part upon the first reading, the plurality of readings, and known physical constraints of the indoor environment, wherein the heading offset is an orientation of the mobile computing device relative to a direction of travel of the mobile computing device;

inferring a path of the mobile computing device in the indoor environment from the initial unknown location to a destination location based at least in part upon the jointly inferring of the stride length, the heading offset, and the current location;

receiving signal strengths observed at the mobile computing device from signals received from at least one wireless access point, the signal strengths corresponding in time to when the mobile computing device is transiting in the indoor environment; and

assigning at least one signal strength to at least one location along the path of the mobile computing device based at least in part upon the inferring of the path of the mobile computing device in the indoor environment.