Whenever people move through their environments they do not move randomly. Instead, they usually follow specific trajectories or motion patterns corresponding to their intentions. Knowledge about such patterns enables a mobile robot to robustly keep track of persons in its environment and to improve its behavior. In this paper we propose a technique for learning collections of trajectories that characterize typical motion patterns of persons. Data recorded with laser-range finders are clustered using the expectation maximization algorithm. Based on the result of the clustering process, we derive a hidden Markov model that is applied to estimate the current and future positions of persons based on sensory input. We also describe how to incorporate the probabilistic belief about the potential trajectories of persons into the path planning process of a mobile robot. We present several experiments carried out in different environments with a mobile robot equipped with a laser-range scanner and a camera system. The results demonstrate that our approach can reliably learn motion patterns of persons, can robustly estimate and predict positions of persons, and can be used to improve the navigation behavior of a mobile robot.
Get full access to this article
View all access options for this article.
References
1.
Arras, K. O., and Vestli, S. J. 1998. Hybrid, high-precision localization for the mail distributing mobile robot system MOPS . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Leuven, Belgium.
2.
Asoh, H., Hayamizu, S., Hara, I., Motomura, Y., Akaho, S., and Matsui, T. 1997. Socially embedded learning of office-conversant robot Jijo-2 . Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI), Nagoya, Japan, August.
3.
Barraquand, J., Langois, B., and Latombe, J.-C. 1992. Numerical potential field techniques for robot path planning . IEEE Transactions on Robotics and Automation, Man and Cybernetics22(2): 224-241 .
4.
Burgard, W., Cremers, A. B., Fox, D., Hähnel, D., Lakemeyer, G., Schulz, D., Steiner, W., and Thrun, S. 1999. Experiences with an interactive museum tour-guide robot . Artificial Intelligence114(1-2): 3-55 .
5.
Cox, I. J. 1993. A review of statistical data association techniques for motion correspondence . International Journal of Computer Vision10(1): 53-66 .
6.
Duda, R., Hart, P., and Stork, D. 2001. Pattern Classification, Wiley-Interscience, New York .
7.
Ehrenmann, M., Lütticke, T., and Dillmann, R. 2001. Dynamic gestures as an input device for directing a mobile platform . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, May 21-26.
8.
Endres, H., Feiten, W., and Lawitzky, G. 1998. Field test of a navigation system: autonomous cleaning in supermarkets . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Leuven, Belgium.
9.
Engelberger, J. F. 1993. Health-care robotics goes commercial: the “helpmate” experience . Robotica11: 517-523 .
10.
Feyrer, S., and Zell, A. 2000. Robust real-time pursuit of persons with a mobile robot using multisensor fusion . Proceedings of the 6th International Conference on Intelligent Autonomous Systems (IAS-6), Venice, Italy, July.
11.
Fod, A., Howard, A., and Mataríc, M. J. 2002. A laser-based people tracker . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11-15.
12.
Foka, A. F., and Trahanias, P. E. 2002. Predictive autonomous robot navigation . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), EPFL, Lausanne, Switzerland, September 30-October 4, pp. 490-495 .
13.
Forgy, E. 1965. Cluster analysis of multivariate data: Efficiency versus interpretability of classifications . Biometrics21(3): 768 .
14.
Galata, N., Johnson, A., and Hogg, D. 2001. Learning variable length Markov models of behaviour . Computer Vision and Image Understanding Journal81(3): 398-413 .
15.
Goldberg, K., and Siegwart, R. 2001. Robots on the Web: Physical Interaction through the Internet, MIT Press, Cambridge, MA .
16.
Goldman, R. P., Geib, W., and Miller, C. A. 1999. A new model of plan recognition . Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), Stockholm, Sweden, July 30-August 1.
17.
González-Baños, H. H., Lee, C.-Y., and Latombe, J.-C. 2002. Real-time combinatorial tracking of a target moving unpredictably among obstacles . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11-15.
18.
Gross, H.-M., and Boehme, H.-J. 2000. Perses—a vision-based interactive mobile shopping assistant . Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Nashville, TN, October.
19.
Guralnik, V., and Haigh, K. Z. 2002. Learning models of human behaviour with sequential patterns . Proceedings of the AAAI-02 workshop “Automation as Caregiver”, Edmonton, Alberta, Canada, July.
20.
Hirzinger, G., Brunner, B., Dietrich, J., and Heindl, J. 1994. ROTEX: the first remotely controlled robot in space . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Diego, CA.
21.
Horswill, I. 1993. Polly: a vision-based artificial agent . Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-93), Washington, DC, July.
22.
Illmann, J., Kluge, B., and Prassler, E. 2002. Statistical recognition of motion patterns . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), EPFL, Lausanne, Switzerland, September 30-October 4.
23.
Jäger, M., and Nebel, B. 2002. Dynamic decentralized area partitioning for cooperating cleaning robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11-15.
24.
Johnson, N., and Hogg, D. 1995. Learning the distribution of object trajectories for event recognition . British Machine Vision Conference, Glasgow, UK.
25.
Jung, B., and Sukhatme, G. S. 2002.A region-based approach for cooperative multitarget tracking in a structural environment . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11-15.
26.
Kasper, M., Fricke, G., Stuernagel, K., and von Puttkamer, E. 2001. A behavior-based mobile robot architecture for learning from demonstration . Journal of Robotics and Automation34(2-3): 153-164 .
27.
Kautz, H., and Allen, J. F. 1986. Generalized plan recognition . Proceedings of the 5th National Conference on Artificial Intelligence (AAAI-86), Philadelphia, PA.
28.
King, S., and Weiman, C. 1990. Helpmate autonomous mobile robot navigation system . Proceedings of the SPIE Conference on Mobile Robots, Boston, MA, November, Vol. 2352, pp. 190-198 .
29.
Kluge, B., Köhler, C., and Prassler, E. 2001. Fast and robust tracking of multiple moving objects with a laser-range finder . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, May 21-26.
30.
Krumm, J., Harris, S., Meyers, B., Brumitt, B., Hale, M., and Shafer, S. 2000. Multicamera multiperson tracking for Easyliving . Proceedings of the 3rd IEEE International Workshop on Visual Surveillance, Dublin, Ireland.
31.
Kruse, F., and Wahl, E. 1998. Camera-based monitoring system for mobile robot guidance . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Victoria, BC, Canada, pp. 1248-1253 .
32.
Lacey, G., and Dawson-Howe, K. 1998. The application of robotics to a mobility aid for the elderly blind . Journal of Robotics and Autonomous Systems23: 245-252 .
33.
Lankenau, A., and Röfer, T. 2000. Smart wheelchairs—state of the art in an emerging market . Zeitschrift KI mit Schwerpunkt Autonome Mobile Systeme14(4): 37-39 .
34.
Lavalle, S. M., González-Banos, H. H., Becker, G., and Latombe, J.-C. 1997. Motion strategies for maintaining visibility of a moving target . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Albuquerque, NM.
35.
Li, C., Biswas, G., Dale, M., and Dale, P. 2001. Building models of ecological dynamics using HMM-based temporal data clustering . Proceedings of the 4th International Conference on Intelligent Data Analysis, Cascais, Portugal, September.
36.
Liao, L., Patterson, D., Fox, D., and Kautz, H. 2004. Learning and inferring transportation routines . Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-04), San Jose, CA, July.
37.
Lindström, M., and Eklundh, J.-O. 2001. Detecting and tracking moving objects from a mobile platform using a laser-range scanner . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Maui, HI, October.
38.
MacCormick, J., and Blake, A. 1999. A probabilistic exclusion principle for tracking multiple objects . Proceedings of the 7th International Conference on Computer Vision (ICCV), Kerkyra, Greece, September, pp. 572-587 .
39.
MacQueen, J. 1967. Some methods for classification and analysis of mulivariate observations . Proceedings of the 5th Berkeley Symposium on Mathematics, Statistics and Probability, Berkeley, CA, pp. 281-296 .
40.
McLachlan, G. J., and Krishnan, T. 1997. The EM Algorithm and Extensions, Series in Probability and Statistics, Wiley, New York .
41.
Mitchell, T. M. 1997. Machine Learning, McGraw-Hill, New York .
42.
Montemerlo, M., Thrun, S., and Whittaker, W. 2002. Conditional particle filters for simultaneous mobile robot localization and people-tracking . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11-15.
43.
Montemerlo, M., Pineau, J., Roy, N., Thrun, S., and Verma, V. 2002. Experiences with a mobile robotic guide for the elderly . Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-02), Edmonton, Alberta, Canada.
44.
Moravec, H. P., and Elfes, A. E. 1985. High-resolution maps from wide angle sonar . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), St Louis, MO, pp. 116-121 .
45.
Murrieta-Cid, R., González-Baños, H. H., and Tovar, B. 2002. A reactive motion planner to maintain visibility of unpredictable targets . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11-15.
46.
Nguyen, N. T., Bui, H. H., Venkatesh, S., and West, G. 2003. Recognizing and monitoring high-level behaviours in complex spatial environments . IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), Madison, WI, June.
47.
Nilsson, N. J. 1982. Principles of Artificial Intelligence, Springer-Verlag, Berlin .
48.
Nourbakhsh, I., Powers, R., and Birchfield, S. 1995. Dervish: an office-navigating robot . AI Magazine16(2): 53-60 .
49.
Oliver, N., Horvitz, E., and Garg, A. 2002. Layered representations for learning and inferring office activity from multiple sensory channels . Proceedings of the International Conference on Multimodal Interfaces (ICMI), Pittsburgh, PA, October.
50.
Parker, L. E. 1997. Cooperative motion control for multi-target observation . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Grenoble, France.
51.
Pirjanian, P., and Mataríc, M. 2000. Multirobot target acquisition using multiple objective behaviour coordination . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April 24-28.
52.
Rabiner, L. R., and Juang, B. H. 1986. An introduction to hidden Markov models . IEEE ASSP Magazine3(1): 4-16 .
53.
Riley, P., and Veloso, M. 2002. Recognizing probabilistic opponent movement models . RoboCup-2001: The 5th RoboCup Competitions and Conferences, Seattle, WA, A. Birk, S. Coradeschi, and S. Tadokoro, editors, Springer-Verlag, Berlin.
54.
Rosales, R., and Sclaroff, S. 1998. Improved tracking of multiple humans with trajectory prediction and occlusion modeling . Proceedings of the IEEEWorkshop on Interpretation of Visual Motion, Santa Barbara, CA, June.
55.
Rosales, R., and Sclaroff, S. 2003. A framework for heading-guided recognition of human activity . Computer Vision and Image Understanding Journal91(3): 335-367 .
56.
Rosencrantz, M., Gordon, G., and Thrun, S. 2003. Locating moving entities in dynamic indoor environments with teams of mobile robots . Proceedings of the 2nd Joint International Conference on Autonomous Agents and Multi-agent Systems (AAMAS), Melbourne, Australia, July.
57.
Schaeffer, C., and May, T. 1999. Care-o-bot—a system for assisting elderly or disabled persons in home environments. Assistive Technology on the Threshold of the New Millennium, IOS Press, Amsterdam .
58.
Schraft, R. D., and Schmierer, G. 1998. Service Robots, Springer-Verlag, Berlin .
59.
Schulz, D., Burgard, W., Fox, D., Thrun, S., and Cremers, A. B. 2000. Web interfaces for mobile robots in public places . IEEE Robotics and Automation Magazine7(1): 48-56 .
60.
Schulz, D., Burgard, W., Fox, D., and Cremers, A. B. 2003. People tracking with a mobile robot using sample-based joint probabilistic data association filters . International Journal of Robotics Research22(2): 99-116 .
61.
Schwarz, G. 1978. Estimating the dimension of a model . Annals of Statistics6(2): 461-464 .
62.
Siegwart, R., Arras, K. O., Jensen, B., Philippsen, R., and Tomatis, N. 2003. Design, implementation and exploitation of a new fully autonomous tour guide robot . Proceedings of the 1st International Workshop on Advances in Service Robotics (ASER), Bardolino, Italy, March.
63.
Simmons, R., Goodwin, R., Haigh, K., Koenig, S., and O’Sullivan, J. 1997.A layered architecture for office delivery robots . Proceedings of the 1st International Conference on Autonomous Agents, Marina del Rey, CA, February.
64.
Stachniss, C., and Burgard, W. 2002. An integrated approach to goal-directed obstacle avoidance under dynamic constraints for dynamic environments . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), EPFL, Lausanne, Switzerland, September 30-October 4.
65.
Stauffer, C., and Grimson, W. E. L. 2000. Learning patterns of activity using real-time tracking . IEEE Transactions on Pattern Analysis and Machine Intelligence22(8): 747-757 .
66.
Swain, M., and Ballard, D. 1991. Color indexing . International Journal of Computer Vision7(1): 11-32 .
67.
Tadokoro, S., Hayashi, M., Manabe, Y., Nakami, Y., and Takamori, T. 1995. On motion planning of mobile robots which coexist and cooperate with human . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Pittsburgh, PA, pp. 518-523 .
68.
Thrun, S., Beetz, M., Bennewitz, M., Burgard, W., Cremers, A. B., Dellaert, D., Fox, D., Hähnel, D., Rosenberg, C., Schulte, J., and Schulz, D. 2000. Probabilistic algorithms and the interactive museum tour-guide robot Minerva . International Journal of Robotics Research19(11): 972-999 .
69.
Weigel, T., Gutmann, J.-S., Dietl, M., Kleiner, A., and Nebel, B. 2002. CS Freiburg: coordinating robots for successful soccer playing . IEEE Transactions on Robotics and Automation18(5): 685-699 .
70.
Zhu, Q. 1991. Hidden Markov model for dynamic obstacle avoidance of mobile robot navigation . IEEE Transactions on Robotics and Automation7(3): 390-397 .
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
