Context-Aware Navigation Algorithms
August 13, 2010 By: Jussi CollinAssume that your mobile phone knows your mode of transportation (stationary, walking, riding a car, etc.) automatically. How could navigation algorithms take advantage of this information? Here’s a possible way this information can be used. When you are not moving at all, it would turn off the GPS receiver to save power, or apply Doppler positioning techniques when the standard positioning fails. When you pick up your phone and start walking, the navigator switches to Pedestrian Dead Reckoning (PDR) mode. In the PDR mode a direct view to satellites is not needed for updating the positioning as the sensor-based step counting and heading estimation takes care of position updates during the GPS signal outages. Finally, when you start your car, the phone detects “driving”-mode and allows the map-matching algorithm to fix the positions on a road network. It is clear that automatic recognition of motion mode would help the navigator in the difficult process of obtaining accurate PVT estimate from noisy observations. How would it be possible to do such recognition? In this article we will show how the data obtained from accelerometers can be used to distinguish between the relevant motion modes.
Accelerometer Data
Modern smartphones, such as the Nokia N95, contain a 3-axis accelerometer. The accelerometer measures acceleration in inertial space minus the local gravity vector. The accelerometer output aB is thus
, (1)
where r is position vector in chosen reference coordinate frame L, 
denotes second time derivative (acceleration) of r, and g is local gravity vector. For simplicity, reference frame L is assumed to be a non-rotating, non-accelerating frame. A direction cosine matrix 
transforms vectors from local reference frame L to the body frame B (defined by sensor sensitivity axes). Orientation of the phone is not (very) relevant information for the motion mode classification, so we take the Euclidian norm of the accelerometer output
, (2)
where 
is the input to the recognition algorithm, and is the measured specific force vector.
The next step is to look at the time series 
with different motion modes. Figure 1 shows norm of N95 accelerometer data when the author is walking and driving a car. Also shown is the data when the phone is stationary on a table. Clearly, the variance of the data varies between the modes, and in the walking mode the waveform is cyclic due to step impacts. To see this more clearly, we plot the sample standard deviation and peak frequency of 5-second frames in Figure 2. In stationary mode, only the sensor noise is measured and the variability of the signal is very low. When driving, engine vibrations and vehicle accelerations cause the variability to increase, but the frequency peak is distributed quite randomly. When walking, the foot impacts increase the variability significantly. In addition, the peak frequency is now concentrated near 1.5 Hz, the step frequency of the person walking. Based on Figure 2, the task of recognizing the motion mode seems very simple – just draw decision boundary lines so that all the walking data points are separated from other points etc, as done in Figure 3. The problem is that our example data set is very small, and doesn’t include all the relevant motion modes. For example, a bicycling waveform is often very similar to a walking waveform due to pedalling motion. This is illustrated in Figure 4, where bicycling data point (red +) is shown. If the bicycling mode is misclassified to walking mode, the PDR algorithm would fail to provide accurate position. More features and a more efficient recognition algorithm is thus needed. Research done in the area of pattern recognition will help us.
Figure 1: Norm of accelerometer output with different motion modes
Figure 2: Distinctive features: standard deviation and peak frequency
Figure 3: Ad hoc decision boundaries
Figure 4: Data from bicycling causes a problem
Pattern Recognition
In of the simplest forms, pattern recognition is discrimination between p multivariate normal populations. The Bayes theorem is applied to obtain the probability of the originating population class (motion mode in our examples) given the observation vector. First, a training data set with known states is collected to obtain
, (3)
the distribution of observed q-vector z given that the observation comes from population class j. The mean vector 
and the covariance matrix 
are actually estimates and not perfectly known, but we will proceed with the assumption that there is no uncertainty in 
and 
. This assumption holds well if the training data set is large. Furthermore, we assume that the training data cannot be used to specify the prior probability P(Cj), the probability of event that the future observation comes from class j. 
is a safe choice.
By looking at the Figure 2 one can see that the assumption of normal distribution is somewhat dubious, but leads to a simple algorithm to start with. To proceed with recognition, we define a discrete type random variable
,
mapping events such that
. (4)
Using this definition, z can be thought of as an observation of true state corrupted by zero mean noise with covariance . Now we have the prior probability mass function
(5)
and z given 
has a multivariate normal distribution
(6)
The unconditional distribution of the observation is
(7)
Figure 5: Distribution of 
and the decision boundary. Integral of this distribution over the red area gives the probability of error given the true state is 2.
Defining 
if 
, we can apply Bayes’ theorem,
, (8)
resulting the desired probability mass function. The actual recognition is then made by selecting class j that has the highest probability. This selection rule forms a decision boundary to 
, which can be used to compute probabilities of misclassification (as described in Figure 5).
Now that we have a model and decision rule, the next step is to collect more data and find relevant features that will efficiently separate different motion modes. By selecting features such as max-min, zero crossing rate, mean, peak amplitude etc. and compressing the data a bit we obtain Figure 6. This figure shows that there is some hope in separating bicyclist and pedestrian, but one has to accept ~ 10 % error rate. Even though PDR algorithms possibly can’t tolerate this error rate, we believe that there are many applications that are not so sensitive to misclassification.
Figure 6: Training data projected onto best two linear discriminant directions. Contours enclose 99 % of the probability mass, computed using a Gaussian fit.
Conclusions
The classification results show that accelerometer data can be used to separate the motion modes of interest, but the decision error rate is quite high for navigation filter purposes. For example, bicyclist and pedestrian acceleration waveforms are very similar when the phone is carried in a pocket. If the PDR algorithm is applied to a bicyclist, the results will be very unfavorable. One way to decrease the error rate is to perform partial classification, where the option of not classifying a measurement is reserved. Tools developed in the area of speech recognition are probably very useful in this task, as the basic problem is very similar to motion mode recognition.
In addition to navigation algorithms, there are many applications where infrequent false detections can be tolerated; road condition analysis is one such example. As positioning-enabled mobile phones with accelerometer and internet access are becoming more and more common, it will be easy to distribute time and location-dependent information to others. Benefits of context awareness in personal navigation devices are thus twofold – location estimation will be more efficient, and useful location-tagged information can be given for other road users.
Acknowledgments
This work was funded by the National Technology Agency of Finland and was carried out in Sensor Data Fusion and Applications project as a part of the Cooperative Traffic research program of the Strategic Centre for Science, Technology and Innovation in the Field of ICT.
Jussi Collin
Tampere University of Technology
This article is based on ION ITM2010 paper "Context Awareness for GPS-Enabled Phones."
References
J. Syrjärinne and J. Käppi, “Method and apparatus for lowering power use by a ranging receiver, US Patent US7409188,” 2008.
A. Lehtinen, “Doppler positioning with GPS,” Master’s thesis, Tampere University of Technology, 2001.
R. Levi and T. Judd, “Dead reckoning navigation system using accelerometer to measure foot impacts, US patent US5583776,” 1999.
S. Dmitriev, B. Rivkin, and D. Koshaev, “Optimal map-matching for car navigation system,” in Proc. 6th Saint Petersburg International Conference on Integrated Navigation Systems, 1999.
A.Webb, Statistical Pattern Recognition. John Wiley & Sons, LTD, 2nd ed., 2002.
J. Kantola, M. Perttunen, T. Leppänen, J. Collin, and J. Riekki, “Context awareness for GPS-enabled phones,” in Proc. ION 2010 International Technical Meeting, pp. 117–124, Institute of Navigation, Alexandria, VA, USA, 2010.
J. Broffit, Handbook of Statistics 2, ch. Nonparametric Classification.
gsmarena.com search shows 195 phones with accelerometer and GPS, retrieved 10th May 2010.
Cooperative Traffic Research Programme.
RSS
Become a Fan
Join our Network
Follow Us
Please send any technical comments or questions to our webmaster.