• Start date: 01.01.2002

• End date: 31.12.2005
• Funded by: Universität Augsburg
• Local head of project: Prof. Dr. Theo Ungerer

Abstract

We investigate the feasibility of next context prediction using sequences of previously contexts and compare the efficiency of several prediction methods. There are four main contexts: the id, the location, the time, and the activity. We concentrate mostly on the location and evaluate the prediction methods in a scenario which concerns employees in an office building visiting offices in a regular fashion over some period of time. We model the scenario by different prediction techniques like dynamic Bayesian networks, neural networks, Markov predictors, and state predictors.

Description

The aim of the project is to investigate how far machine learning techniques can dynamically predict location sequences, time of location entry, and duration of stays independent of additional knowledge. Of course the information could be combined with contextual knowledge as e.g. the office time table or personal schedule of a person; however, we focus currently on dynamic techniques without contextual knowledge.

Further interesting questions concern the efficiency of training of a predictor, before the first useful predictions can be performed, and of retraining, i.e. how long it takes until the predictor adapts to a habitual change and provides again useful predictions. Predictions are called useful if a prediction is accurate with a certain confidence level. Moreover, memory and performance requirements of a predictor are of interest in particular for mobile appliances with limited performance ability and power supply.

The predictions could be used for a number of applications in a smart office environment:

• In the  Smart Doorplate Project a visitor is notified about the probable next location of an absent office owner within a smart office building. The prediction is needed to decide if the visitor should follow the searched person to his current location, go to the predicted next location, or just wait till the office owner comes back.
• Phone call forwarding to the current office location of a person is an often proposed smart office application, but where to forward a phone call in case that a person just left his office and did not yet reach his destination? The phone call could be forwarded to the predicted room and answered as soon as the person reaches his destination.

Our experiments as part of  Smart Doorplate Project yielded a collection of movement data of four persons over several months that are publicly available as  Augsburg Indoor Location Tracking Benchmarks. We use this benchmark data to evaluate several prediction techniques and compare the efficiency of these techniques with exactly the same evaluation set-up and data. Moreover, we can estimate how good next location prediction works - at least for the  Augsburg Indoor Location Tracking Benchmarks data.

We investigate neural networks, Bayesian networks, Markov predictors, and State predictors. First we chose from the multitude of neural networks the most well-known, the Multi-Layer Perceptron with one hidden layer and back-propagation learning algorithm. The multi-layer perceptron was chosen because of its general application domain and its popularity in the neural network research community. After analyzing more neural networks we decided that an Elman Net fits better for solving the next location problem. Elman nets hold a so-called context layer. With this layer the nets are suited to learn sequences. The results show that Elman nets are usually better suited than the multi-layer perceptron.

In the case of Bayesian networks we started with a static Bayesian network. Afterwards, in order to predict a future context of a person, the usage of a Dynamic Bayesian Network was chosen. This network consists of different time slices which all contain an identical Bayesian network. Bayesian networks are particularly well suited to model time.

The State Predictor method originates in branch prediction and data compression algorithms that are transformed and adapted to fit the scenario of context prediction. Generally speaking, the prediction principle is derived from Markov chains theory. Several one- and two-level predictors were proposed and evaluated first by synthetic benchmarks.

The table compares the prediction accuracies of the neural networks Elman net and multi-layer perceptron, Bayesian network, state predictor, and Markov Predictor showing always the best results yielded for each person of the Augsburg Benchmarks. The configurations may vary for different persons. Typically, there is no superb configuration of a predictor for all persons. The shown prediction accuracies are derived for the first scenario where a visitor will be informed about the potential return of an office owner. That means the accuracies include only predictions when the employee isn't in his own room. Furthermore the following set-up was used: All prediction algorithms were trained with summer data and the accuracies were measured with the fall data (see Augsburg Benchmarks). The results show that there isn't a universal predictor.

Because of the sometimes unreliable results of predictions it may be sometimes better to make no prediction instead of a wrong prediction. Humans may be frustrated by too many wrong predictions and won't believe in further predictions even when the prediction accuracy improves over time. Therefore Confidence Estimation of context prediction methods is necessary. We propose and evaluate three confidence estimation techniques for the state predictor method – the strong state method, the threshold method, and the confidence counter method. The proposed confidence estimation techniques can also be transferred to other prediction methods like Markov predictors, neural network, or Bayesian networks.

Moreover, also the length of stay is of interest. This can easily be predicted by dynamic Bayesian networks or attached to other predictors as arithmetic mean or median of previous length of stay in the respective location.

A user must set up a lot of parameters before he can use one of the proposed prediction methods and these parameters differ for each user. Therefore a complex configuration must be made before such a method can be used. A Hybrid Predictor can reduce the configuration overhead utilizing different prediction methods or configurations in parallel to yield different prediction results. A selector chooses the most appropriate prediction result from the result set of the base predictors. We propose and evaluate three principal hybrid predictor approaches – the warm-up predictor, the majority predictor, and the confidence predictor – with several variants. The hybrid predictors reach higher prediction accuracy than the average of the prediction accuracies of the separately used predictors.

The project Context Prediction in Ubiquitous Computing was finished with the PhD thesis of Jan Petzold.

Publications

2006

• Hybrid Predictors for Next Location Prediction
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  The 3rd International Conference on Ubiquitous Intelligence and Computing (UIC-06), Wuhan and Three Gorges, China, September 2006

• Comparison of Different Methods for Next Location Prediction
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  European Conference on Parallel Computing, Euro-Par 2006, Dresden, Germany, August/September 2006

• Improving Next Location Prediction by Using Hybrid Predictors
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  Poster at 2nd International Workshop on Location- and Context-Awareness (LoCA 2006), Dublin, Ireland, May 2006.

2005

• Zustandsprädiktoren zur Kontextvorhersage in ubiquitären Systemen
  Jan Petzold
  Dissertation, Universität Augsburg
  Erstgutachter: Prof. Dr. Theo Ungerer
  Zweitgutachter: Prof. Dr. Bernhard Bauer

• Prediction of Indoor Movements Using Bayesian Networks
  Jan Petzold, Andreas Pietzowski, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  First International Workshop on Location- and Context-Awareness, LoCA 2005, Oberpfaffenhofen, Germany, May 2005.

• Next Location Prediction Within a Smart Office Building
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  1st International Workshop on Exploiting Context Histories in Smart Environments (ECHISE'05) at the 3rd International Conference on Pervasive Computing, Munich, Germany, May 2005.

2004

• Confidence Estimation of the State Predictor Method
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  Second European Symposium on Ambient Intelligence, EUSAI 2004, Eindhoven, The Netherlands, November 2004.

• Person Movement Prediction Using Neural Networks
  Lucian Vintan, Arpad Gellert, Jan Petzold, Theo Ungerer
  Workshop on Modeling and Retrieval of Context 2004, MRC 2004, located at the 27th German Conference on Artificial Intelligence, Ulm, Germany, September 2004

• Person Movement Prediction Using Neural Network
  Lucian Vintan, Arpad Gellert, Jan Petzold, Theo Ungerer
  Technical Report, Institute of Computer Science, University of Augsburg, April 2004
  2004-10

• Augsburg Indoor Location Tracking Benchmarks
  Jan Petzold
  Technical Report, Institute of Computer Science, University of Augsburg, April 2004
  2004-09

• Global State Context Prediction Techniques Applied to a Smart Office Building
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer, Lucian Vintan
  The Communication Networks and Distributed Systems Modeling and Simulation Conference, San Diego, CA, USA, January 2004

2003

• Global and Local State Context Prediction
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  Artificial Intelligence in Mobile Systems 2003 (AIMS 2003) in Conjunction with the Fifth International Conference on Ubiquitous Computing 2003, Seattle, USA, October 2003.

• The State Predictor Method for Context Prediction
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  In Adjunct Proceedings Fifth International Conference on Ubiquitous Computing 2003. , Seattle, USA, October 2003

• Smart Doorplate - Toward an Autonomic Computing System
  Wolfgang Trumler, Faruk Bagci, Jan Petzold, Theo Ungerer
  The Fifth Annual International Workshop on Active Middleware Services (AMS2003), Seattle, USA, June 25, 2003

• Smart Doorplate
  Wolfgang Trumler, Faruk Bagci, Jan Petzold, Theo Ungerer
  The First International Conference on Appliance Design (1AD), Bristol, UK, May 6-8, 2003,
  Reprinted in: Journal of Personal and Ubiquitous Computing, volume 7, number 3-4, pages 221-226, July 2003

• Einsatz mobiler Agenten in verteilten ubiquitären Systemen
  Faruk Bagci, Jan Petzold, Wolfgang Trumler, Theo Ungerer
  19. PARS-Workshop, Basel, Switzerland, March 20-21, 2003, (in German)

• Einsatz von XML zur Kontextspeicherung in einem agentenbasierten ubiquitären System
  Faruk, Bagci, Jan Petzold, Wolfgang Trumler, Theo Ungerer
  XMIDX-Workshop, Berlin, Germany, February 17-18, 2003, (in German)

• Context Prediction Based on Branch Prediction Methods
  Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer
  Technical Report, Institute of Computer Science, University of Augsburg, July 2003
  2003-14

• Einsatz von Sprungvorhersagetechniken zur Kontextvorhersage in ubiquitären Systemen
  Jan Petzold
  Technical Report, Institute of Computer Science, University of Augsburg, March 2003
  2003-04