Location measurement process for radio-frequency badges employing path constraints

• US 7,019,694 B2
• Filed: 11/05/2004
• Issued: 03/28/2006
• Est. Priority Date: 11/15/2002
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Gregory, Krumm, John
• Primary Examiner(s): Issing, Gregory C.
• Application Number:
  US10/982,742
• Publication Number:
  US 20050093745A1
• Time in Patent Office: 508 Days
• Field of Search: 342/463, 342/464, 342/465
• US Class Current: 342/463
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map

Abstract

A process for measuring the location of people and objects carrying radio frequency (RF) transmitters (TXs) that transmit messages to a plurality of RF receivers (RXs) located in a space. Each RX is in communication with a computer of a computer network and forwards data received from the TXs to the network via its associated computer, along with a value indicating the signal strength of the received TX transmission. The signal strengths attributable to the same transmission are used to form a locating signal strength vector which is then compared to exemplary vectors generated from signal strength readings gathered in a calibration procedure from a set of representative locations in the space. In comparing the locating vector to the exemplary vectors, constraints are enforced on movements between locations (e.g., cannot pass through walls) and to probabilistically enforce expectations on transitions between locations.

Claims

1. A computer-implemented process for measuring the location of people and objects carrying radio frequency (RF) transmitters (TXs) that transmit messages to a plurality of RF receivers (RXs) located in a space each of which is in communication with a computer of a computer network, wherein each RX forwards data received from the TXs to the network via its associated computer, along with a value indicating the signal strength of the received TX transmission, comprising:

capturing means for capturing data provided from the RXs which comprises the signal strength of each TX transmission measured by each RX associated with a TX carried by a person or object of interest within the space;

generating means for generating a locating signal strength vector representing the signal strength measured by each RX in response to the same TX transmission associated with the TX carried by the person or object of interest; and

for each locating signal strength vector generated, employing comparing means for comparing the locating vector to previously generated calibration signal strength vectors to determine what calibration vector is most likely to correspond to the locating vector based on any previous computed locations for the person or object being located and a prescribed set of allowable transitions between locations assigned to the calibration vectors, wherein each calibration signal strength vector represents what the signal strengths measured by each RX in response to a TX transmission would be if a TX is placed at said assigned locations in the space, and deeming the person or object being located to be at the location assigned to that calibration vector.

2. The process of claim 1, further comprising second generating means for generating the calibration signal vectors prior to comparing the locating vector to previously generated calibration signal strength vectors, said second generating means comprising:

storing means for storing a representation of a space in which the location of a person or object carrying a TX is to be measured, wherein the spatial representation comprises the coordinates and name of representative locations in the space where the person or object might be located at any point in time;

second capturing means for capturing calibration data provided from the RXs which comprises the signal strength of each TX transmission measured by each RX when a TX is respectively placed at each of the representative locations in the space;

third generating means for generating a calibration signal strength vector representing the signal strength measured by each RX in response to the same TX transmission; and

assigning means for assigning the calibration vector to the representative location where the TX was placed when the transmission was made.

3. The process of claim 2, wherein the capturing means for capturing calibration data provided from the RXs which comprises the signal strength of each TX transmission measured by each RX when a TX is respectively placed at each of the representative locations in the space, comprises employing for each representative location:

inputting means for inputting a message indicating that the TX is located at one of the representative locations and providing the name of the location;

third capturing means for capturing the calibration data provided from the RXs each time the TX transmits from the indicated representative location as the TX is reoriented at the location between TX transmissions and associating the calibration data with the indicated representative location;

second inputting means for inputting a message indicating that the TX is being removed from the currently indicated representative location; and

ceasing means for ceasing to associate any calibration data received with the currently indicated location whenever a message indicating that the TX is being removed from the currently indicated representative location is input.

4. The process of claim 2, wherein the spatial representation further comprises, for each of the representative locations, a set of transition probabilities representing said prescribed set of allowable transitions which specify the probability that a person or object of interest in the space would remain at the same location and the respective probabilities that the person or object would move to each of the other representative locations, between TX transmissions, wherein the probability of moving to another representative location that cannot be reached in the time between TX transmissions, owing to the distance between the locations or the presence of obstructions between the locations, is set to zero.

5. The process of claim 4, wherein the comparing means for comparing the locating vector to previously generated calibration signal strength vectors to determine what calibration vector is most likely to correspond to the locating vector for each locating signal strength vector generated and deeming the person or object of interest to be at the location assigned to that calibration vector, comprises:

upon the generation of the first locating signal strength vector, employing,

computing means for computing an initial locating quantity for each representative location which is defined as the product of the probability of starting at a representative location under consideration and the probability of measuring at that location the most current locating signal strength vector generated based on the calibration signal strength vectors generated for said location, and

designating means for designating the location of the representative location associated with the maximum locating quantity computed as the current location of the person or object carrying the TX responsible for the locating signal strength vector; and

upon generation of each subsequent locating signal strength vector, employing,

second computing means for computing a locating quantity for each representative location which is defined as the maximum value of the respective products of the locating quantity computed for the immediately preceding locating signal strength vector generated for each representative location multiplied by the transition probability of transitioning from that location to the representative location under consideration multiplied by the probability of measuring the current locating signal strength vector at that representative location,

second designating means for designating the representative location associated with the maximum locating quantity value computed as the current location of the person or object carrying the TX associated with the locating signal strength vector under consideration.

6. The process of claim 5, further comprising reporting means for reporting the locating quantity value computed for each representative location to a location-aware application, said location-aware application foregoing a prescribed action triggered by knowing the location of a person or object carrying a TX whenever the locating quantities when viewed as a whole indicated an uncertainty as to the location of the person or object of interest.

7. The process of claim 2, wherein the comparing means for comparing the locating vector to previously generated calibration signal strength vectors to determine what calibration vector is most likely to correspond to the locating vector for each locating signal strength vector generated and deeming the person or object of interest to be at the location assigned to that calibration vector, comprises a declaring means for declaring the person or object of interest to be at the representative location associated with the calibration signal strength vector that is most similar to the locating signal strength vector.

8. The process of claim 7, wherein the declaring means for declaring the person or object of interest to be at the representative location associated with the calibration signal strength vector that is most similar to the locating signal strength vector, comprises determining means for determining similarity between the calibration signal strength vectors and the locating signal strength vector using a nearest neighbor technique.

9. A computer-implemented process for measuring the location of people and objects carrying radio frequency (RF) receivers (RXs) that receive messages transmitted by a plurality of RF transmitters (TXs) located in a space, wherein each RX is in communication with a centralized computer of a computer network and forwards data received from the TX transmissions via the network to said centralized computer, along with a value indicating the signal strength of each received TX transmission, comprising:

data capturing means for capturing data provided from the RXs which comprises the signal strength of each TX transmission measured by each RX associated with a person or object of interest within the space;

generating means for generating a locating signal strength vector representing the signal strengths measured by a RX carried by the person or object of interest in response to TX transmissions received within a prescribed period of time; and

for each locating signal strength vector generated, employing comparing means for comparing the locating vector to previously generated calibration signal strength vectors to determine what calibration vector is most likely to correspond to the locating vector based on any previous computed locations for the person or object of interest and a prescribed set of allowable transitions between locations assigned to the calibration vectors, wherein each calibration signal strength vectors represents what the signal strengths measured by the RX carried by the person or object of interest in response to TX transmissions received within a prescribed period of time would be if the RX is placed at said assigned locations in the space, and for deeming the person or object being located to be at the location assigned to that calibration vector.

10. A computer-implemented process for measuring the location of people and objects carrying radio frequency (RF) receivers (RXs) that receive messages transmitted by a plurality of RF transmitters (TXs) located in a space, wherein each RX measures a value indicating the signal strength of each received TX transmission, comprising:

generating means for generating a locating signal strength vector representing the signal strengths measured by a RX carried by the person or object of interest in response to TX transmissions received within a prescribed period of time;

for each locating signal strength vector generated, employing comparing means for comparing the locating vector to previously generated calibration signal strength vectors to determine what calibration vector is most likely to correspond to the locating vector based on any previous computed locations for the person or object of interest and a prescribed set of allowable transitions between locations assigned to the calibration vectors and for deeming the person or object being located to be at a location assigned to that calibration vector, wherein each calibration signal strength vectors represents what the signal strengths measured by the RX carried by the person or object of interest in response to TX transmissions received within a prescribed period of time would be if the RX is placed at said assigned locations in the space.

11. A computer-readable medium having computer-executable instructions for measuring the location of people and objects carrying radio frequency (RF) transmitters (TXs) that transmit messages to a plurality of RF receivers (RXs) located in a space each of which is in communication with a computer of a computer network, wherein each RX forwards data received from the TXs to the network via its associated computer, along with a value indicating the signal strength of the received TX transmission, said computer-executable instructions comprising:

capturing data provided from the RXs which comprises the signal strength of each TX transmission measured by each RX associated with a TX carried by a person or object of interest within the space;

generating a locating signal strength vector representing the signal strength measured by each RX in response to the same TX transmission associated with the TX carried by the person or object of interest;

for each locating signal strength vector generated, comparing the locating vector to previously generated calibration signal strength vectors to determine what calibration vector is most likely to correspond to the locating vector based on any previous computed locations for the person or object being located and a prescribed set of allowable transitions between locations assigned to the calibration vectors, wherein each calibration signal strength vector represents what the signal strengths measured by each RX in response to a TX transmission would be if a TX is placed at said assigned locations in the space, and deeming the person or object being located to be at the location assigned to that calibration vector.

12. A computer-readable medium having computer-executable instructions for measuring the location of people and objects carrying radio frequency (RF) receivers (RXs) that receive messages transmitted by a plurality of RF transmitters (TXs) located in a space, wherein each RX is in communication with a centralized computer of a computer network and forwards data received from the TX transmissions via the network to said centralized computer, along with a value indicating the signal strength of each received TX transmission, said computer-executable instructions comprising:

capturing data provided from the RXs which comprises the signal strength of each TX transmission measured by each RX associated with a person or object of interest within the space;

generating a locating signal strength vector representing the signal strengths measured by a RX carried by the person or object of interest in response to TX transmissions received within a prescribed period of time;

for each locating signal strength vector generated, comparing the locating vector to previously generated calibration signal strength vectors to determine what calibration vector is most likely to correspond to the locating vector based on any previous computed locations for the person or object of interest and a prescribed set of allowable transitions between locations assigned to the calibration vectors, wherein each calibration signal strength vectors represents what the signal strengths measured by the RX carried by the person or object of interest in response to TX transmissions received within a prescribed period of time would be if the RX is placed at said assigned locations in the space, and deeming the person or object being located to be at the location assigned to that calibration vector.

13. A computer-readable medium having computer-executable instructions for measuring the location of people and objects carrying radio frequency (RF) receivers (RXs) that receive messages transmitted by a plurality of RF transmitters (TXs) located in a space, wherein each RX measures a value indicating the signal strength of each received TX transmission, said computer-executable instructions comprising:

generating a locating signal strength vector representing the signal strengths measured by a RX carried by the person or object of interest in response to TX transmissions received within a prescribed period of time;

for each locating signal strength vector generated, comparing the locating vector to previously generated calibration signal strength vectors to determine what calibration vector is most likely to correspond to the locating vector based on any previous computed locations for the person or object of interest and a prescribed set of allowable transitions between locations assigned to the calibration vectors and deeming the person or object being located to be at a location assigned to that calibration vector, wherein each calibration signal strength vectors represents what the signal strengths measured by the RX carried by the person or object of interest in response to TX transmissions received within a prescribed period of time would be if the RX is placed at said assigned locations in the space.