Activity recognition via user-trace segmentation

ABSTRACT

A major issue of activity recognition in sensor networks is automatically recognizing a user's high-level goals accurately from low-level sensor data. Traditionally, solutions to this problem involve the use of a location-based sensor model that predicts the physical locations of a user from the sensor data. This sensor model is often trained offline, incurring a large amount of calibration effort. In this article, we address the problem using a goal-based segmentation approach, in which we automatically segment the low-level user traces that are obtained cheaply by collecting the signal sequences as a user moves in wireless environments. From the traces we discover primitive signal segments that can be used for building a probabilistic activity model to recognize goals directly. A major advantage of our algorithm is that it can reduce a significant amount of human effort in calibrating the sensor data while still achieving comparable recognition accuracy. We present our theoretical framework for activity recognition, and demonstrate the effectiveness of our new approach using the data collected in an indoor wireless environment.

REFERENCES

• 1: David W. Albrecht , Ingrid Zukerman , An E. Nicholson, Bayesian Models for Keyhole Plan Recognition in an Adventure Game, User Modeling and User-Adapted Interaction, v.8 n.1-2, p.5-47, 1998 [doi>10.1023/A:1008238218679]
• 2: Anderson, B. D. O. and Moore, J. B. 1979. Optimal Filtering. Prentice-Hall, Englewood Cliffs, New Jersey.
• 3: Bahl, P., Balachandran, A., and Padmanabhan, V. 2000. Enhancements to the RADAR user location and tracking system. Tech. rep. MSR-TR-2000-12, Microsoft Research.
• 4: Bahl, P. and Padmanabhan, V. N. 2000. RADAR: An in-building RF-based user location and tracking system. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). Tel-Aviv, Israel, 775--784.
• 5: Blaylock, N. and Allen, J. 2003. Corpus-based statistical goal recognition. In Proceedings of the 8th International Joint Conference on Artificial Intelligence (IJCAI). Acapulco, Mexico, 1303--1308.
• 6: Christoph Bregler, Learning and Recognizing Human Dynamics in Video Sequences, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.568, June 17-19, 1997
• 7: Bui, H., Phung, D., and Venkatesh, S. 2004. Hierarchical hidden Markov models with general state hierarchy. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI). San Jose, CA, 324--329.
• 8: Bui, H., Venkatesh, S., and West, G. 2002. Policy recognition in the abstract hidden Markov model. J. Art. Intel. Res. 17, 451--499.
• 9: Xiaoyong Chai , Qiang Yang, Reducing the Calibration Effort for Location Estimation Using Unlabeled Samples, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.95-104, March 08-12, 2005 [doi>10.1109/PERCOM.2005.34]
• 10: Eugene Charniak , Robert P. Goldman, A Bayesian model of plan recognition, Artificial Intelligence, v.64 n.1, p.53-79, Nov. 1993 [doi>10.1016/0004-3702(93)90060-O]
• 11: Bill Chiu , Eamonn Keogh , Stefano Lonardi, Probabilistic discovery of time series motifs, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956808]
• 12: Czielniak, G., Bennewitz, M., and Burgard, W. 2003. Where is …? learning and utilizing motion patterns of persons with mobile robots. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Acapulco, Mexico, 909--914.
• 13: Dempster, A. P., Laird, N. M., and Rubin, D. B. 1977. Maximum likelihood from incomplete data via EM algorithm. J. Royal Statis. Soc. Series B 39, 1--38.
• 14: Enge, P. and Misra, P. 1999. Special issue on GPS: The global positioning system. Proc. IEEE, 3--172.
• 15: Shai Fine , Yoram Singer , Naftali Tishby, The Hierarchical Hidden Markov Model: Analysis and Applications, Machine Learning, v.32 n.1, p.41-62, July 1998 [doi>10.1023/A:1007469218079]
• 16: Dieter Fox , Jeffrey Hightower , Lin Liao , Dirk Schulz , Gaetano Borriello, Bayesian Filtering for Location Estimation, IEEE Pervasive Computing, v.2 n.3, p.24-33, July 2003 [doi>10.1109/MPRV.2003.1228524]
• 17: Zoubin Ghahramani, Learning Dynamic Bayesian Networks, Adaptive Processing of Sequences and Data Structures, International Summer School on Neural Networks, "E.R. Caianiello"-Tutorial Lectures, p.168-197, September 06-13, 1997
• 18: Ghahramani, Z. and Hinton, G. E. 1998. Switching state-space models. Tech. Rep., 6 King's College Road, Toronto M5S 3H5, Canada.
• 19: Goldman, R., Geib, C., and Miller, C. 1999. A new model of plan recognition. In Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence (UAI). Stockholm, Sweden, 245--254.
• 20: Andreas Haeberlen , Eliot Flannery , Andrew M. Ladd , Algis Rudys , Dan S. Wallach , Lydia E. Kavraki, Practical robust localization over large-scale 802.11 wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023728]
• 21: Han, K. and Veloso, M. 2000. Automated robot behavior recognition applied to robotic soccer. In Robotics Research: the 9th International Symposium. Springer-Verlag, London, 199--204.
• 22: Johan Himberg , Kalle Korpiaho , Heikki Mannila , Johanna Tikanmäki , Hannu Toivonen, Time Series Segmentation for Context Recognition in Mobile Devices, Proceedings of the 2001 IEEE International Conference on Data Mining, p.203-210, November 29-December 02, 2001
• 23: Kautz, H. and Allen, J. F. 1986. Generalized plan recognition. In Proceedings of the 5th National Conference on Artificial Intelligence (AAAI). Philadelphia, PA, 32--37.
• 24: Eamonn J. Keogh , Selina Chu , David Hart , Michael J. Pazzani, An Online Algorithm for Segmenting Time Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.289-296, November 29-December 02, 2001
• 25: Andrew M. Ladd , Kostas E. Bekris , Algis Rudys , Guillaume Marceau , Lydia E. Kavraki , Dan S. Wallach, Robotics-based location sensing using wireless ethernet, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570674]
• 26: Lari, K. and Young, S. J. 1990. The estimation of stochastic context-free grammars using the inside-outside algorithm. Comput. Speech Lang. 4, 35--56.
• 27: Lesh, N. and Etzioni, O. 1995. A sound and fast goal recognizer. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Montreal, Canada, 1704--1710.
• 28: Yan Li , Tianshu Wang , Heung-Yeung Shum, Motion texture: a two-level statistical model for character motion synthesis, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 29: Liao, L., Fox, D., and Kautz, H. 2004. Learning and inferring transportation routines. In Proceedings of the 19th National Conference in Artificial Intelligence (AAAI). San Jose, CA, 348--353.
• 30: Seng W. Loke, Representing and reasoning with situations for context-aware pervasive computing: a logic programming perspective, The Knowledge Engineering Review, v.19 n.3, p.213-233, September 2004 [doi>10.1017/S0269888905000263]
• 31: Dimitrios Lymberopoulos , Abhijit S. Ogale , Andreas Savvides , Yiannis Aloimonos, A sensory grammar for inferring behaviors in sensor networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127817]
• 32: Minka, T. 1998. Expectation-maximization as lower bound maximization. Tutorial. http://research.microsoft.com/~minka/papers/em.html.
• 33: Martin Mühlenbrock , Oliver Brdiczka , Dave Snowdon , Jean-Luc Meunier, Learning to Detect User Activity and Availability from a Variety of Sensor Data, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom'04), p.13, March 14-17, 2004
• 34: Murphy, K. 1998. Learning switching Kalman filter models. Tech. rep. TR 98--10, Compaq Cambridge Research Lab.
• 35: Kevin Patrick Murphy , Stuart Russell, Dynamic bayesian networks: representation, inference and learning, University of California, Berkeley, 2002
• 36: Nguyen, N., Bui, H., Venkatesh, S., and West, G. 2003. Recognising and monitoring high-level behaviours in complex spatial environments. In Proceedings of International Conference on Computer Vision and Pattern Recognition (CVPR). Madison, WI, 620--625.
• 37: Tim Oates, PERUSE: An Unsupervised Algorithm for Finding Recurrig Patterns in Time Series, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.330, December 09-12, 2002
• 38: Oh, S. M., Regh, J. M., Balch, T., and Dellaert, F. 2005. Data-driven MCMC for learning and inference in switching linear dynamic systems. In Proceedings of the 20th National Conference in Artificial Intelligence (AAAI). Pittsburgh, PA, 944--949.
• 39: Patterson, D., Liao, L., Fox, L., and Kautz, H. 2003. Inferring high-level behavior from low-level sensors. In Proceedings of the 5th International Conference on Ubiquitous Computing (UbiComp). Seattle, WA, 73--89.
• 40: Pavlović, V. and Rehg, J. M. 2000. Impact of dynamic model learning on classification of human motion. In Proceedings of the International Conference on Computer Vision and Pattern Recognition (CVPR). Hilton Head Island, SC, 788--795.
• 41: Pavlović, V., Rehg, J. M., Cham, T.-J., and Murphy, K. 1999. A dynamic Bayesian network approach to figure tracking using learned dynamic models. In Proceedings of the 6th IEEE International Conference on Computer Vision (ICCV). Kerkyra, Corfu, Greece, 94--101.
• 42: Pavlović, V., Rehg, J. M., and MacCormick, J. 2000. Learning switching linear models of human motion. In Advances in Neural Information Processing Systems (NIPS). Vol. 13. MIT Press, Cambridge, MA, 981--987.
• 43: Patrick Peursum , Hung H. Bui , Svetha Venkatesh , Geoff West, Human Action Segmentation via Controlled Use of Missing Data in HMMs, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 4, p.440-445, August 23-26, 2004 [doi>10.1109/ICPR.2004.443]
• 44: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 45: David V. Pynadath , Michael P. Wellman, Probabilistic State-Dependent Grammars for Plan Recognition, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.507-514, June 30-July 03, 2000
• 46: Roos, T., Myllymaki, P., Tirri, H., Misikangas, P., and Sievanen, J. 2002. A probabilistic approach to WLAN user location estimation. Int. J. Wireless Inform. Netw. 9, 3 (July), 155--164.
• 47: Smailagic, A. and Kogan, D. 2002. Location sensing and privacy in a context aware computing environment. IEEE Wirel. Comm. 9, 5, 10--17.
• 48: Tapia, E. M., Intille, S., and Larson, K. 2004. Activity recognition in the home using simple and ubiquitous sensors. In Proceedings of the 2nd International Conference on Pervasive Computing (Pervasive). Vienna, Austria, 158--175.
• 49: Tekinay, S. 1998. Special issue on wireless geolocation systems and services. IEEE Comm. Mag. 87, 1 (April).
• 50: Roy Want , Andy Hopper , Veronica Falcão , Jonathan Gibbons, The active badge location system, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.91-102, Jan. 1992 [doi>10.1145/128756.128759]
• 51: Wren, C. R. and Tapia, E. M. 2006. Toward scalable activity recognition for sensor networks. In Proceedings of the 2nd International workshop in Location and Context-Awareness (LoCA). Vol. 3987. Dublin, Ireland, 168--185.
• 52: Yin, J., Chai, X., and Yang, Q. 2004. High-level goal recognition in a wireless LAN. In Proceedings of the 19th National Conference in Artificial Intelligence (AAAI). San Jose, CA, 578--584.
• 53: Yin, J., Shen, D., Yang, Q., and Li, Z.-N. 2005a. Activity recognition through goal-based segmentation. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI). Pittsburgh, PA, 28--33.
• 54: Jie Yin , Qiang Yang , Lionel Ni, Adaptive Temporal Radio Maps for Indoor Location Estimation, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.85-94, March 08-12, 2005 [doi>10.1109/PERCOM.2005.7]
• 55: Youssef, M. and Agrawala, A. 2004. Handling samples correlation in the horus system. In Proceedings of the 23rd IEEE Conference on Computer Communications and Networking (INFOCOM). Hong Kong, China, 1023--1031.
• 56: Moustafa A. Youssef , Ashok Agrawala , A. Udaya Shankar, WLAN Location Determination via Clustering and Probability Distributions, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.143, March 23-26, 2003
• 57: Mohammed J. Zaki, SPADE: an efficient algorithm for mining frequent sequences, Machine Learning, v.42 n.1/2, p.31-60, Jan. 2001 [doi>10.1023/A:1007652502315]
• 58: Zhu, X. 2005. Semi-supervised learning literature survey. Tech. rep. 1530, Computer Sciences, University of Wisconsin-Madison.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES

General Terms:
Algorithms, Performance

Keywords:
Activity recognition, motion patterns, segmentation