System and methods for determining the location dynamics of a portable computing device

• US 7,532,113 B2
• Filed: 07/25/2005
• Issued: 05/12/2009
• Est. Priority Date: 06/30/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J., Krumm, John C.
• Primary Examiner(s): Appiah; Charles N
• Assistant Examiner(s): Vu; Michael T
• Application Number:
  US11/188,951
• Publication Number:
  US 20050258957A1
• Time in Patent Office: 1,387 Days
• Field of Search: 455/456, 455/561, 455/423, 455/67.6, 455/186, 455/404, 455/456.1, 455/456.3, 455/456.5, 345/833, 715/733, 709/203, 709/223
• US Class Current: 340/539.13
• 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: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A location system for locating and determining the motion and velocity of a wireless device. The methods include direct inferences about whether a device is in motion versus static based on a statistical analysis of the variation of radio signal strengths over time. The system is trained according to a sparse set of identified locations from which signal strengths are measured. The system uses the signal properties of the identified locations to interpolate for a new location of the wireless device. The system uses a probabilistic graph where the identified locations of the floor plan, expected walking speeds of pedestrians, and independent inference of whether or not the device is in motion are used to determine the new location of the device.

Claims

1. A graphical user interface that facilitates inferring motion and locating a mobile wireless device, the interface comprising:

an input component for receiving management information, the management information associated with at least the processes of measuring signal strength data of identified locations and generating probability data of the identified locations to further determine a new location of the wireless device, the probability data includes an inferred likelihood that the wireless device is in motion, an expected velocity of the wireless device, and at least one transition probability that the device is transitioning between two of the identified locations, wherein the determination of a new location is based upon the inferred likelihood that the wireless device is in motion, the expected velocity of the wireless device, the at least one transition probability that the device is transitioning between two of the identified locations, and feasible movement information of the mobile wireless device derived from building layout information of a building in which the mobile wireless device is currently located, wherein the feasible movement information is based on at least one travel path between the two identified locations along which a user carrying the device can physically traverse in the building; and

a presentation component for presenting a representation of the identified locations to facilitate user interaction therewith, wherein the presentation component further includes a plotting feature for providing a graphical representation of all of the identified locations to which the wireless device may travel, and possible paths that the wireless device may traverse to the identified locations.

2. The interface of claim 1, the management information including mapping information that maps a discrete low-density node with each of the identified locations.

3. The interface of claim 1, the management information including mapping information received from a mapping component that maps a discrete low-density node to each of the identified locations, and distributes high-density nodes among the low-density nodes according to predetermined spatial criteria, the mapping information presented by the presentation component.

4. The interface of claim 1, further comprising a mapping feature that maps a discrete low-density node with each of the identified locations, and determines corresponding distances between the low-density nodes.

5. The interface of claim 1, the presentation component providing a graphical representation of possible paths that the wireless device may traverse to the identified locations.

6. The interface of claim 1, the plotting feature further providing the capability of assigning edge weights to adjacent and non-adjacent nodes.

7. The interface of claim 1, the plotting feature further representing pathways to the identified locations and automatically converting the endpoint of each pathway to an end node, which is one type of location node.

8. The interface of claim 1, the plotting feature further automatically distributing intermediate nodes among the location nodes according to predetermined spatial criteria.

9. The interface of claim 1, further comprising a floor layout of individual location representations of the identified locations, wherein the location representations are selectable.

10. The interface of claim 1, the plotting feature further plotting signal properties associated with the a selected identified location and an unselected location.

11. The interface of claim 1, the user input component comprising at least one of:

means for selecting a building associated with the locations;

means for selecting a floor in the building;

means for selecting one of the locations; and

means for selecting a scan rate for sampling the signal properties.

12. The interface of claim 1, further comprising graphical means to display a color and/or a pattern corresponding to user preference information.

13. A computer readable medium comprising a graphical user interface that facilitates inferring motion and locating a mobile wireless device, comprising:

an input interface for receiving management information, the management information associated with at least the processes of measuring signal strength data of identified locations and generating probability data of the identified locations to further determine a new location of the wireless device, the probability data includes an inferred likelihood that the wireless device is in motion, an expected velocity of the wireless device, and at least one transition probability that the device is transitioning between two of the identified locations, wherein the determination of a new location is based upon the inferred likelihood that the wireless device is in motion, the expected velocity of the wireless device, the at least one transition probability that the device is transitioning between two of the identified locations, and feasible movement information of the mobile wireless device derived from building layout information of a building in which the mobile wireless device is currently located, wherein the feasible movement information is based on at least one travel path between the two identified locations along which a user carrying the device can physically traverse in the building; and

a presentation interface for presenting a representation of the identified locations to facilitate user interaction therewith, wherein the presentation interface further includes a plotting feature for providing a graphical representation of all of the identified locations to which the wireless device may travel, and possible paths that the wireless device may traverse to the identified locations.

14. The computer readable medium of claim 13, the management information including mapping information that maps a discrete low-density node with each of the identified locations.

15. The computer readable medium of claim 13, the management information including mapping information received from a mapping component that maps a discrete low-density node to each of the identified locations, and distributes high-density nodes among the low-density nodes according to predetermined spatial criteria, the mapping information presented by the presentation interface.

16. The computer readable medium of claim 13, further comprising a mapping feature that maps a discrete low-density node with each of the identified locations, and determines corresponding distances between the low-density nodes.

17. A graphical user interface system that facilitates inferring motion and locating a mobile wireless device, comprising:

means for receiving management information, the management information associated with at least the processes of measuring signal strength data of identified locations and generating probability data of the identified locations to further determine a new location of the wireless device, the probability data includes a probability that the mobile wireless device is in motion based upon the measured signal strength data of the identified locations, a probability of a speed of the mobile wireless device based upon the probability that the mobile wireless device is in motion, and at least one transition probability that the mobile wireless device is transitioning between two of the identified locations based upon the probability that the mobile wireless device is in motion and the probability of a speed of the mobile wireless device, wherein the determination of a new location is based upon the probability that the mobile wireless device is in motion, the probability of the speed of the mobile wireless device, the at least one transition probability that the mobile wireless device is transitioning between two of the identified locations and feasible movement information of the mobile wireless device between the two of the identified locations derived from building layout information of a building in which the mobile wireless device is currently located, wherein the feasible movement information is based on at least one travel path along which a user carrying the device can physically traverse in the building; and

means for presenting a representation of the identified locations to facilitate user interaction therewith, wherein the means for presenting further includes a plotting feature for providing a graphical representation of all of the identified locations to which the wireless device may travel, and possible paths that the wireless device may traverse to the identified locations.