Location measurement process for radio-frequency badges employing path constraints

• US 20040095276A1
• Filed: 11/15/2002
• Published: 05/20/2004
• Est. Priority Date: 11/15/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Gregory, Krumm, John
• Granted Patent: US 6,839,027 B2
• Time in Patent Office: Days
• US Class Current: 342/465
• 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, the process comprising using a centralized computer of the network to perform the following process actions:

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 vectors 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 a process action of generating the calibration signal vectors prior to performing the action of comparing the locating vector to previously generated calibration signal strength vectors, said generating comprising the actions of:

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,

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, and

generating a calibration signal strength vector representing the signal strength measured by each RX in response to the same TX transmission and 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 process action of 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, for each representative location, the actions of:

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

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; and

inputting a message indicating that the TX is being removed from the currently indicated representative location and ceasing to associate any calibration data received with the currently indicated location.

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 process action of 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 the actions of:

upon the generation of the first locating signal strength vector,

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 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;

upon generation of each subsequent locating signal strength vector,

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,

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, wherein the process action of computing the locating quantity comprises an action of computing the probability of measuring the most current locating signal strength vector generated at a particular representative location based on the calibration signal strength vectors generated for that location, said computing of the probability comprising:

prescribing a value for the standard deviation of the signal strength readings within the space;

defining a covariance matrix Σ

as a 4×

4 identity matrix scaled by the prescribed standard deviation of the signal strength readings;

computing the nearest neighbor calibration signal strength vector s_n^* to the most current locating signal strength vector s as

$s_n^{*}=\underset{j=0<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>N_n-1}{\min }<br><br><br><br>s-s_n^{\left(j\right)}<br><br>$

where N_n is the number of calibration vectors at representative location n and s_n^(j) are the calibration vectors assigned to location n; and

defining the probability of measuring the most current locating signal strength vector generated at a particular representative location P(s|n) as

$P(s<br><br><br><br>n)=\frac{1}{{\left(\sqrt{2<br><br>\mathrm{\pi <br><br>}}\right)}^4<br><br>{<br><br>\underset{\text{\hspace{1em}<br><br>}}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>}^{0<br><br>\text{\hspace{1em}<br><br>}<br><br>5}<br><br>\text{\hspace{1em}<br><br>}}<br><br>{\mathrm{<br><br>}}^{-\frac{1}{2}<br><br>{\left(s-s_n^{*}\right)}^T<br><br>{\sum <br><br>}^{-1}<br><br>\left(s-s_n^{*}\right)}.$

7. The process of claim 5, further comprising the process action of 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.

8. The process of claim 2, wherein the process action of 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 the action of 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.

9. The process of claim 8, wherein the process action of 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 the action of determining similarity between the calibration signal strength vectors and the locating signal strength vector using a nearest neighbor technique.

10. A location measurement system for measuring the location of persons and objects within a space, comprising:

at least one radio frequency (RF) transmitters (TX), each of which is carried by the person, or attached to the object, whose location is to be measured and each of which transmits TX messages;

a plurality of RF receivers (RXs), each of which receives TX messages transmitted by TXs within signal range of the RX, said TX messages comprising a transmitter identifier which uniquely identifies the particular TX transmitting the TX message, and wherein each RX measures the strength of the signal carrying a TX message received from a TX;

at least one computing device, each of which is in communication with one or more RXs and which receive data messages from the RXs which are generated upon receipt of a TX message from a TX, wherein the data message comprises the transmitter identifier, a signal strength indicator associated with the TX message and a receiver identifier that uniquely identifies the particular RX sending the data message;

a centralized computing device which is in communication with each of the computing devices associated with a RX via said network and which receives badge hit messages each of which represents a version of the forwarded RX data messages with an identifier identifying the computing device forwarding the message appended thereto; and

a computer program comprising program modules executable by the centralized computing device, wherein the centralized computing device is directed by the program modules of the computer program to,

generate 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 within the space using the badge hit messages received via said network, and

for each locating signal strength vector generated, compare 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, and deeming the person or object of interest to be at a location assigned to that calibration vector, wherein each calibration signal strength vectors 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.

11. The system of claim 10, further comprising a program module for generating the calibration signal strength vectors which is executed prior to executing the program module for comparing the locating vector to previously generated calibration signal strength vectors, said calibration signal strength vector generating program module comprising sub-modules for:

storing a representation of a space comprising the coordinates and name of representative locations in the space where the person or object might be located at any point in time;

capturing calibration data comprising 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 as derived from received badge hit messages; and

generating a calibration signal strength vector representing the signal strength measured by each RX in response to the same TX transmission and assigning the calibration vector to the representative location where the TX was placed when the transmission was made.

12. The system of claim 11, further comprising a portable computing device which is in communication with the centralized computer via said network, and wherein the execution of the sub-module for storing the representation of the space is preceded by generating the spatial representation and transferring it to the centralized computer using said remote computer.

13. The system of claim 12, wherein the portable computing device comprises a graphical user interface including a display, user interface selection device and user interface data entry device, in addition to a computer program for generating said spatial representation comprising program modules executable by the portable computing device, wherein the portable computing device is directed by the program modules of the computer program to:

input a floor plan of the space;

display a calibration window on said display, said calibration window comprising a sector displaying the floor plan;

input a user-specified coordinate system used in defining locations in the space and their corresponding locations on the floor plan of the space;

input data and implement commands entered by the user using the calibration window via said selection and data entry devices to allow the user to specify the coordinates and name of said representative locations in the space;

respectively display a marker on the display of the floor plan at a location corresponding to the user-specified coordinates of each representative location entered by the user.

14. The system of claim 13, wherein the program module for inputting data and implementing commands entered by the user to specify the coordinates and name of said representative locations in the space, comprises a sub-module for inputting the coordinates and name of at least one representative location for each office or room in the space being calibrated, as well as the coordinates and name of a representative location in the hallways outside each office or room door.

15. The system of claim 13, wherein the program module for inputting data and implementing commands entered by the user to specify the coordinates and name of said representative locations in the space, comprises, for each location entered, executing sub-modules for:

inputting the coordinates of each representative location as the location in the space corresponding to a location on the displayed floor plan of the space that the user has identified by placing a screen cursor over the location and selecting it;

displaying the inputted coordinates in a position field appearing in the calibration window;

inputting a name entered by the user in a name field appearing in the calibration window and assigning the name to the representative location having the coordinates displayed in the position field at the time; and

displaying a representative location marker on the floor plan at the floor plan location corresponding to the inputted coordinates of the location.

16. The system of claim 13, wherein the program module for inputting data and implementing commands entered by the user to specify the coordinates and name of said representative locations in the space, comprises, for each location entered, executing sub-modules for:

inputting the coordinates of each representative location as the location in the space corresponding to a location on the displayed floor plan of the space that the user has identified by placing a screen cursor over the location and selecting it;

displaying the inputted coordinates in a position field appearing in the calibration window;

generating a unique name for the representative location;

assigning the name to the representative location;

displaying the assigned name in a name field appearing in the calibration window; and

displaying a representative location marker on the floor plan at the floor plan location corresponding to the inputted coordinates of the location.

17. The system of claim 13, further comprising a program module for inputting data and implementing commands entered by the user using the calibration window via said selection and data entry devices to allow the user to specify allowable paths between each representative location in the space and its adjacent representative locations, wherein an allowable path exists between a representative location and an adjacent representative location whenever a person or object carrying a TX could move from the representative location to the adjacent representative location in the time between transmissions of the TX.

18. The system of claim 17, wherein the program module for inputting data and implementing commands entered by the user to specify allowable paths between each representative location in the space and its adjacent representative locations, executing sub-modules for:

inputting, for each representative location, a list of transition probabilities representing said prescribed set of allowable transitions which specifies 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.;

for each non-zero transition probability specified between a pair of representative locations, displaying a line on the floor plan between the pair.

19. The system of claim 13, wherein the sub-module for capturing calibration data, comprises, for each representative location, the sub-modules for:

inputting a message generated by said portable computing device that indicates the TX is located at one of the representative locations and providing the name of the location;

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; and

inputting a message generated by said portable computing device that indicates the TX is being removed from the currently indicated representative location and ceasing to associate any calibration data received with the currently indicated location.

20. The system of claim 19, wherein the portable computing device further comprises a computer program for generating said messages indicating the TX is located at one of the representative locations and indicating the TX is being removed from the currently indicated representative location, said computer program comprising program modules executable by the portable computing device, wherein the portable computing device is directed by the program modules of the computer program to:

display a first button in the calibration window which when selected by the user causes the message indicating the TX is located at one of the representative locations to be provided to the centralized computer; and

display a second button in the calibration window which when selected by the user causes the message indicating the TX is being removed from the currently indicated representative location to be provided to the centralized computer.

21. 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:

in a calibration phase,

storing a representation of a space in which the location of a person or object carrying a TX is to be measured, wherein the 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,

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, and

generating a calibration signal strength vector representing the signal strength measured by each RX in response to the same TX transmission and assigning the calibration vector to the representative location where the TX was placed when the transmission was made; and

in a locating phase,

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, and

for each locating signal strength vector generated, comparing the locating vector to the 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, and deeming the person or object of interest to be at the location associated with that calibration vector.

22. 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, the process comprising using a centralized computer of the network to perform the following process actions:

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.

23. 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, the process comprising the following process actions:

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.