A Learning Algorithm for Localizing People Based on Wireless Signal Strength that Uses Labeled and Unlabeled Data

1 Introduction

This paper addresses the problem of localizing people using a wireless network. Various researchers have recently developed techniques using the signal strength of IEEE 802.11 b access points for people localization [ 1; 3; 6; 9; 11]. In doing so, these techniques require measurement data labeled by the position at which the data was acquired.

Our approach builds on this idea, but augments it by a learned probabilistic motion model of people. The data used for training the motion model is acquired as people walk through the environment. We employ the EM algorithm to train the resulting hidden Markov model.

2 Signal Strength Maps From Labeled Data

At the most basic level, our approach acquires a map of the wireless signal strength at different locations in the environ­ ment. For that, it requires the availability of signal strength measurements labeled by the true position. Our implementa­ tion represents this map by a piecewise linear Gaussian, that follows the (mostly) one-dimensional manifold of the center of each corridor in the building. Figure 1 illustrates the signal strength measurements for one of the access points in our test building. The measurement noise is modeled as a Gaussian, whose covariance is estimated from the data using the maxi­ mum likelihood estimator.

3 Probabilistic Localization

The signal strength map is sufficient to coarsely localize peo­ ple. Following [6], our approach implements a continuous­ state hidden Markov model (HMM), in which the person's po­ sition is the internal state, and the signal strengths are the mea­ surements. The signal strength map provides the measurement probabilities of the HMM. The next state transition, or motion model, may be as simple as a probabilistic model of Brownian motion; a more sensible choice will be discussed below.

Our approach uses this HMM to track the location of the person, by calculating an approximate posterior. This is achieved using the well-known Monte Carlo localization al­ gorithm [ 1 0], a variant of particle filters [5].

4 Motion Models From Unlabeled Data

The principal limitation of the approach thus far is its reliance on labeled data. Such data is difficult to collect, as it requires an independent means for generating correct position labels when carrying a wireless receiver through a building. Our ap­ proach specifically addresses the use of unlabeled data. Such data is acquired as people walk through the building.

This unlabeled data consists of signal measurements with­ out a pose estimate. We use this data to learn a motion model of a person. This motion model is realized by mixtures of Gaussians that characterize the relative change of position within a fixed time interval. Each linear sub-piece of the signal strength map possesses its own Gaussian mixture; in this way, the approach can learn location-specific predictions of peo­ ple's motion. The motivation to use a Gaussian mixture model arises from the fact that people often engage in one out of a small number of different motions (e.g., turning left or right at an intersection; see Figure 2). In our approach, the num­ ber of Gaussians is fixed, as is their variance. Our approach learns the means of the Gaussians and the mixture weights as a function of people's location.

Learning from unlabeled data is achieved using the EM al­ gorithm (see [2; 7; 8] for related work). Beginning with anini­ tial motion model, position probabilities are computed based on the signal strength, using the particle filter described above. These position probabilities are then used to calculate a dis­ tribution over the mixture components of the Gaussian, and subsequently to calculate the mean and new mixture weights. This methodology is a straightforward application of the EM algorithm, assuming that both a person's pose and the index of the Gaussian mixture are latent variables [ 4]. In our imple­ mentation, we bias the initial motion model (before learning) towards typical motions people might take, such as going for­ ward, turning left or right, and standing in place.

5 Experimental Results

Systematic experimental results were conducted in an office environment equipped with approximately 50 802.11 b wire­ less access points, distributed over an area of size 120 by 22.5

meters. On average, five access points are within communica­ tion range of each location in the environment.

All labeled data was acquired by using a laser range finder for localization, similar to work in mobile robotics [10] . A set of labeled data was collected by simply walking about the en­ vironment, traversing each corridor at least three times in each direction (along the center, left, and right of the hallway). We also collected a large set of unlabeled training data by travers­ ing paths characteristic of the movements of an individual (all paths originated or terminated at a specific office). Finally, we collected an independent test set with labels.

Figure 3 shows a key result, obtained for 200 particles. This figure shows the cumulative probability function over the av­ erage localization error from our labeled test set for different techniques. The top blue curve corresponds to the combined labeled-unlabeled data approach described above, utilizing the learned mixture models. The green dashed curve reflects the performance of the same system with no learning; all mixture weights are uniform. The red dot-dashed curve represents the performance of a pure Brownian motion model, rather than a mixture of Gaussians.

A localization error of 2.25 meters is achieved 70% of the time when only using the labeled data. This number appears to be well in tune with results reported in [6] while requiring a factor of 50 less labeled training data. This error is reduced by 20% as the motion model is trained with the unlabeled data. This illustrates the relative improvement that can be achieved by adding unlabeled measurements to the pool of training data.