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

• US 7,250,907 B2
• Filed: 06/30/2003
• Issued: 07/31/2007
• Est. Priority Date: 06/30/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krumm, John C., Horvitz, Erc J.
• Primary Examiner(s): Issing; Gregory C.
• Application Number:
  US10/610,190
• Publication Number:
  US 20040263388A1
• Time in Patent Office: 1,492 Days
• Field of Search: 342/451
• 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 effectuated on a machine that determines location dynamics of a mobile device, comprising:

a measuring component that employs a graph outlining probable ambulatory routes to process signal properties related to identified locations; and

a probability processing component that 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.

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 considers at least one of structure of the variance(s), different signal distributions 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 bafflers 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 associated with an observation probability.

15. The system of claim 1, a graph of identified locations, associated transition probabilities, and observation probabilities are combined using a Viterbi algorithm that 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 uses an interpolation function that extends probability distributions of the identified locations to new locations.

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

36. 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.

37. A machine implemented 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 utilizes a model of ambulatory pathways and path constraints imposed by a building'"'"'s interior structure to directly infer 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.

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

a tangible machine 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 employment of a model of available humanly accessible routes and an analysis of statistics of variation of one or more of the radio signals over time and ascertains a speed of the mobile device, the probability processing component further employs an interpolation function that extends probability distributions of the identified locations to new locations.

39. A wireless device location system, comprising:

means for measuring signal properties related to identified locations, the signal properties measured from at least one wireless signal associated with one or more wireless network interface;

means for determining an inference of motion of the mobile device based at least in part in the measured signal properties;

means for approximating a location of the mobile device based at least in part on the inference of motion and a graph that maps possible humanly accessible routes; and

means for determining a speed of the mobile device.

40. A method implemented on a machine for determining the location dynamics of a mobile device, comprising:

utilizing a tangible machine component to measure signal properties related to identified locations;

generating a location constraint model by employing a constraint-sensitive path-planning algorithm that considers physical barriers between two of the identified locations;

based at least in part on the location constraint model and signal properties, 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.

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

42. The method of claim 40, the location of the mobile device approximated using regression function.

43. The method of claim 40, 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.

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

45. The method of claim 40, 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.

46. The method of claim 40, 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.

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