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

• US 20040263388A1
• Filed: 06/30/2003
• Published: 12/30/2004
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krumm, John C., Horvitz, Erc J.
• Granted Patent: US 7,250,907 B2
• Time in Patent Office: Days
• US Class Current: 342/451
• 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 system that determines location dynamics of a mobile device, comprising:

a measuring component that measures signal properties related to identified locations; and

a probability processing component that makes a determination and/or inference about motion of the mobile device, and approximates a location of the mobile device based at least in part on the determination and/or inference of motion.

2. The system of claim 1, the probability processing component outputting a probability that the mobile device is currently in motion.

3. The system of claim 1, the probability processing component employs a statistical analysis that factors variance of signal strengths when the mobile device is in motion versus when the mobile device is still.

4. The system of claim 3, the signal strength variance is temporally analyzed.

5. The system of claim 3, the analysis further considering at least one of structure of the variance(s), different modes of distributions over signals over time, and relative signal strengths.

6. The system of claim 1, the signal properties obtained from an IEEE 802.11 device.

7. The system of claim 1, the signal properties obtained from radio broadcasts of AM or FM radio as used by traditional commercial broadcasters.

8. The system of claim 1, the probability processing component utilizes a hidden Markov model to determine state transition probabilities.

9. The system of claim 1, any two of the identified locations having associated therewith a transition probability that indicates a probability that the mobile device will move from a first identified location to a second identified location.

10. The system of claim 9, the transition probability is a function of elapsed time since a last signal strength measurement, the distance between the any two identified locations, and a probability that the mobile device is currently in motion.

11. The system of claim 1, a shortest path between two of the identified locations is based upon a constraint-sensitive path-planning algorithm that considers physical barriers between the two identified locations.

12. The system of claim 1, a probable speed of the mobile device is explicitly considered by inferring a likelihood that the mobile device is in motion.

13. The system of claim 1, the speed of the mobile device is computed from at least one of an expected velocity based upon consideration of a probability distribution of human pedestrian speeds and the inference of motion.

14. The system of claim 1, each of the identified locations has associated therewith an observation probability.

15. The system of claim 1, a graph of the identified locations, associated transition probabilities, and observation probabilities are combined using a Viterbi algorithm, which algorithm computes a probability distribution over the identified locations from every set of measured signal properties.

16. The system of claim 15, an output of the Viterbi algorithm is a probability value associated with each identified location giving a probability that the mobile device is at that respective identified location.

17. The system of claim 1, the probability processing component generates an observation probability for each of the identified locations based on the signal properties received at that identified location.

18. The system of claim 1, the probability processing component automatically causing to be stored a probability distribution of signal strengths of a wireless transmitter when the transmitter is sensed from one of the identified locations.

19. The system of claim 18, the probability distribution of signal strengths is associated with the one identified location.

20. The system of claim 1, the probability processing component outputs an expected value representing a location of the mobile device.

21. The system of claim 1, each of the identified locations calibrated using signal properties measured at that location.

22. The system of claim 1, the inference of motion determined according to a variance of the signal strengths over time.

23. The system of claim 1, further comprising a mapping component that maps a discrete low-density node with each of the identified locations.

24. The system of claim 1, further comprising a mapping component that maps a discrete low-density node with each of the identified locations, and distributes high-density nodes among the low-density nodes according to predetermined spatial criteria.

25. The system of claim 1, further comprising a mapping component that maps a discrete low-density node with each of the identified locations, and determines distances between the low-density nodes.

26. The system of claim 25, the mapping component interspersing high-density nodes among the low-density nodes, and the probability processing component utilizing distances between pairs of the high-density nodes to calculate transition probabilities the corresponding pair of high-density nodes.

27. The system of claim 1, the probability processing component determining a location of the mobile device by calculating a continuous position estimate of the location of the mobile device based upon an expected value of a discrete probability distribution over all of the identified locations.

28. The system of claim 1, the probability processing component using a maximum-likelihood decoding algorithm to optimize over all possible paths between the identified locations with respect to a history of the measured signal properties.

29. The system of claim 1, the inference of motion representative of the likelihood that the mobile device is at least one of in motion and at rest.

30. The system of claim 1, the probability processing component using at least one of a Bayesian rule and a support vector machine to determine a posterior probability that the mobile device is moving.

31. The system of claim 1, the probability processing component capturing quantitatively a variation in signal strength of a wireless transmitter by sensing the wireless transmitter with the strongest signal, and calculating a variance of that strongest signal over time.

32. The system of claim 1, the probability processing component performing a smoothing operation on posterior probability data of the mobile device.

33. The system of claim 32, the smoothing operation accomplished by imposing explicit transition probabilities on the posterior probability data, which explicit transition probabilities govern still and moving states of the mobile device.

34. The system of claim 1, the probability processing component derives at least one of a still state and moving state of the mobile device, a transition probability between two of the identified locations, an initial state probability of the mobile device, a velocity value between the two identified locations, and an observation probability based on the signal properties at each of the two identified locations.

35. The system of claim 1, the probability processing component uses an interpolation function that extends probability distributions of the identified locations to new locations.

36. A computer according to the system of claim 1.

37. The system of claim 1, the probability processing component using calibration data to approximate the location of the mobile device relative to the identified locations.

38. A system that facilitates tracking a mobile device, comprising:

a component that receives radio signals associated with the mobile device; and

a probability processing component that directly infers a likelihood that the mobile device is in motion versus static based on an analysis of statistics of variation of one or more of the radio signals over time.

39. A system that facilitates tracking a mobile device, comprising:

a component that receives radio signals associated with the mobile device; and

a probability processing component that directly infers a probability distribution over velocity of the mobile device based on an analysis of statistics of variation of one or more of the radio signals over time.

40. A location system that facilitates locating a wireless device, comprising:

a computer-based mapping component that maps identified locations to location nodes;

a measuring component that measures signal strength data related to the location nodes; and

a probability processing component that determines at least one of motion and the location of the wireless device using a regression function that is based at least in part upon the signal strength data, the regression function estimating new locations based upon the signal strength data.

41. The system of claim 40, the mapping component provides a representation of possible paths that the wireless device may traverse to the identified locations.

42. The system of claim 40, the mapping component provides 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.

43. The system of claim 40, the mapping component provides the capability of assigning edge weights to adjacent and non-adjacent location nodes.

44. The system of claim 40, the mapping component represents pathways to the identified locations and automatically converts the endpoint of each pathway to an end node, which is one type of location node.

45. The system of claim 44, the mapping component automatically distributes intermediate nodes among the location nodes according to predetermined spatial criteria.

46. The system of claim 40, the velocity of the wireless device is computed from at least one of an expected velocity based upon consideration of a probability distribution of human pedestrian speeds and on an inference of whether or not the wireless device is moving.

47. The system of claim 40, the mapping component derives a shortest path between two of the location nodes based upon a constraint-sensitive path-planning algorithm that considers physical barriers between the two corresponding identified locations.

48. The system of claim 40, the measuring component measures the signal strengths of networked transmitting devices displaced throughout an area that includes the identified locations.

49. The system of claim 40, the probability processing component generating an observation probability for each of the location nodes based on signal strengths received at that respective location node.

50. The system of claim 40, the probability processing component automatically generates and associates transition probability data with the location nodes using path constraints, moving probability data, and speed distribution data.

51. The system of claim 40, the probability processing component using a Viterbi algorithm to generate a probability distribution over all location nodes for every set of observed signal strengths.

52. The system of claim 40, the regression function is an interpolation function that extends probability distributions of the location nodes to the new locations.

53. The system of claim 40, the probability processing component using a maximum-likelihood decoding algorithm to optimize over all possible paths between the identified locations with respect to a history of the measured signal properties.

54. The system of claim 40, the probability processing component capturing quantitatively a variation in signal strength of a wireless transmitter by sensing the wireless transmitter with the strongest signal, and calculating a variance of that strongest signal over time.

55. A wireless device location system, comprising:

means for measuring signal properties related to identified locations;

means for determining an inference of motion of the mobile device; and

means for approximating a location of the mobile device based at least in part on the inference of motion.

56. A method of determining the location dynamics of a mobile device, comprising:

measuring signal properties related to identified locations;

calculating with probability data an inference of motion of the mobile device; and

approximating a location of the mobile device based at least in part on the inference of motion.

57. The method of claim 56, further comprising calibrating the identified locations by measuring the signal properties from each of the identified locations.

58. The method of claim 56, the location of the mobile device approximated using regression function.

59. The method of claim 56, the location dynamics including velocity, which velocity of the mobile device is computed from at least one of an expected velocity based upon consideration of a probability distribution of human pedestrian speeds and on an inference of whether or not the mobile device is moving.

60. The method of claim 56, the probability data including path data generated from a constraint-sensitive path-planning algorithm that considers physical barriers between two of the identified locations.

61. The method of claim 56, the probability data including observation probability data generated for each of the identified locations, which observation probability data is based on received signal strengths at the respective identified locations.

62. The method of claim 56, further comprising automatically generating and associating transition probability data with each of the identified locations using path constraints, moving probability data, and speed distribution data.

63. The method of claim 56, the location of the mobile device approximated with respect to a floor of a building.

64. A method of determining the location of a wireless measurement device, comprising:

developing a computer-based map of locations in which the wireless device will be used;

sparsely populating the map with low-density nodes each of which is associated with a respective location on the map;

training the locations by measuring signal properties received at calibration nodes associated with each of the low-density nodes;

generating signal strength distributions for each of the calibration nodes based upon the received signal properties;

populating the map with high-density nodes that are interspersed among the low-density nodes;

generating a transition probability for each pair of high-density nodes based upon path constraints between the nodes;

generating observation probabilities for each of the low-density location nodes;

processing the signal strength distributions, transition probabilities, and observation probabilities to generate a probability value for each high-density node; and

interpolating the probability that the wireless device is at one or near one of the high-density nodes based upon the probability values of the low-density nodes.

65. The method of claim 64, further comprising generating a transition probability between a high-density node and a low-density node.

66. A graphical user interface that facilitates inferring motion and locating a 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; and

a presentation component for presenting a representation of the identified locations to facilitate user interaction therewith.

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

68. The interface of claim 66, 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.

69. The interface of claim 66, 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.

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

71. The interface of claim 66, further comprising 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.

72. The interface of claim 66, further comprising a plotting feature for providing the capability of assigning edge weights to adjacent and non-adjacent nodes.

73. The interface of claim 66, further comprising a plotting feature for 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.

74. The interface of claim 66, further comprising a plotting feature for automatically distributing intermediate nodes among the location nodes according to predetermined spatial criteria.

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

76. The interface of claim 66, further comprising a plotting feature for plotting the signal properties associated with the selected identified location and an unselected location.

77. The interface of claim 66, 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.

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