Predicting Plan Failure by Monitoring Action Sequences and Duration

  • Giovani Parente Farias
  • Ramon Fraga Pereira
    PUCRS
  • Lucas Hilgert
  • Felipe Meneguzzi
    PUCRS
  • Renata Vieira
    PUCRS
  • Rafael Heitor Bordini
    PUCRS

Abstract

Anticipating failures in agent plan execution is important to enable an agent to develop strategies to avoid or circumvent such failures, allowing the agent to achieve its goal.  Plan recognition can be used to infer which plans are being executed from observations of sequences of activities being performed by an agent. In this work, we use this symbolic plan recognition algorithm to find out which plan the agent is performing and develop a failure prediction system, based on plan library information and in a simplified calendar that manages the goals the agent has to achieve. This failure predictor is able to monitor the sequence of agent actions and detects if an action is taking too long or does not match the plan that the agent was expected to perform. We showcase this approach successfully in a health-care prototype system.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas
Albrecht, D. W., Zukerman, I., and Nicholson, A. E., 1998. Bayesian Models for Keyhole Plan Recognition in
an Adventure Game. User Model. User-Adapt. Interact., 8(1-2): 5-47.

Armentano, M. G. and Amandi, A., 2007. Plan Recognition for Interface Agents. Artificial Intelligence,
28(2):131–162. ISSN 0269-2821. doi:10.1007/s10462-009-9095-8.

Augusto, J. C. and Nugent, C. D., editors, 2006. Designing Smart Homes, The Role of Artificial Intelligence,
volume 4008 of Lecture Notes in Computer Science. Springer. ISBN 3-540-35994-X.

Avrahami-Zilberbrand, D., 2009. Efficient Hybrid Algorithms for Plan Recognition and Detection of Suspicious
and Anomalous Behavior. Ph.D. thesis, Bar Ilan University.

Avrahami-Zilberbrand, D. and Kaminka, G. A., 2005. Fast and Complete Symbolic Plan Recognition. In Kaelbling,
L. P. and Saffiotti, A., editors, Proceedings of the International Joint Conference on Artificial Intelligence,
pages 653-658. Professional Book Center. ISBN 0938075934.

Azarewicz, J., Fala, G., and Heithecker, C., 1989. Template-based multi-agent plan recognition for tactical situation
assessment. In Fifth Conference on Artificial Intelligence Applications, pages 247-254.

Baker, C., Saxe, R., and Tenenbaum, J., 2009. Action Understanding as Inverse Planning. Cognition, 31: 329-
349. Breuker, J., 1990. Conceptual Model of Intelligent Help Systems. In Breuker, J., editor, EUROHELP:
developing Intelligent Help Systems, chapter 2, pages 41-66. EC, Copenhagen, DM.

Brown, S. M., 1998. A Decision Theoretic Approach for Interface Agent Development. Ph.D. thesis, Air Force
Institute of Technology, Wright Patterson AFB, OH, USA. AAI9905125.

Bui, H. H. and et al., 2004. Hierarchical Hidden Markov Models with General State Hierarchy. In Proceedings
of the 19th national conference on artificial intelligence, pages 324-329.

Bui, H. H., Venkatesh, S., and West, G., 2002. Policy Recognition in the Abstract Hidden Markov Model. J.
Artif. Int. Res., 17(1): 451-499. ISSN 1076-9757.

Carberry, S., 2001. Techniques for Plan Recognition. User Modeling and User-Adapted Interaction, 11(1-2):
31-48. ISSN 0924-1868.

Charniak, E. and Goldman, R. P., 1993. A Bayesian Model of Plan Recognition. Artif. Intell., 64(1): 53-79. Cirillo,
M., Karlsson, L., and Saffiotti, A., 2010. Human-aware Task Planning: An Application to Mobile Robots.

ACM Trans. Intell. Syst. Technol., 1(2):15: 1-15:26. ISSN 2157-6904. doi:10.1145/1869397.1869404.

Erol, K., Hendler, J., and Nau, D. S., 1994a. HTN Planning: Complexity and Expressivity. In Proceedings of
the Twelfth National Conference on Artificial Intelligence (Vol. 2), AAAI’94, pages 1123-1128. American

Association for Artificial Intelligence, Menlo Park, CA, USA. ISBN 0-262-61102-3.

Erol, K., Hendler, J. A., and Nau, D. S., 1994b. UMCP: A Sound and Complete Procedure for Hierarchical
Task-network Planning. In AIPS, pages 249-254.

Fagundes, M., Meneguzzi, F., Bordini, R. H., and Vieira, R., 2014. Dealing with Ambiguity in Plan Recognition
under Time Constraints. In Proceedings of the Thirteenth International Conference on Autonomous Agents
and Multiagent Systems, pages 389-396.

Fox, M. and Long, D., 2003. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.
Journal of Artificial Intelligence Research, 20(1): 61-124. ISSN 1076-9757.

Geib, C. W., 2002. Problems with intent recognition for elder care. In Proceedings of the AAAI-02 Workshop
Automation as Caregiver, pages 13-17.

Geib, C. W. and Goldman, R. P., 2001. Plan Recognition in Intrusion Detection Systems. In Proceedings of the
Second DARPA Information Survivability Conference and Exposition (DISCEX II), pages 329-342.

Geib, C. W. and Goldman, R. P., 2003. Recognizing Plan/Goal Abandonment. In Proceedings of the 18th International
Joint Conference on Artificial Intelligence, IJCAI’03, pages 1515-1517. Morgan Kaufmann Publishers
Inc., San Francisco, CA, USA.

Goldman, R. P., Geib, C. W., and Miller, C. A., 1999. A New Model of Plan Recognition. Artificial Intelligence,
64: 53-79.

Granada, R., Monteiro, J., Barros, R. C., and Meneguzzi, F., 2017a. A Deep Neural Architecture for Kitchen
Activity Recognition.

Granada, R., Pereira, R. F., Monteiro, J., Barros, R., Ruiz, D., and Meneguzzi, F., 2017b. Hybrid Activity and
Plan Recognition for Video Streams. In The 2017 AAAI Workshop on Plan, Activity, and Intent Recognition.

Greer, J. E. and Koehn, G. M., 1995. The Peculiarities of Plan Recognition for Intelligent Tutoring Systems.
In IJCAI-95 Workshop on the Next Generation of Plan Recognition Systems, pages 54-59. Montreal, Canada.

Grosz, B. J. and Sidner, C. L., 1990. Plans for discourse. In Cohen, P., Morgan, J., and Pollack, M., editors,
Intentions in communication, pages 417-444. MIT Press.

Hong, J., 2001. Goal recognition through goal graph analysis. Journal of Artificial Intelligence Research, 15:
1-30.

Hongeng, S. and Nevatia, R., 2003. Large-scale event detection using semi-hidden Markov models. In Computer
Vision, 2003. Proceedings. Ninth IEEE International Conference on, pages 1455-1462 vol. 2. doi:10.1109/
ICCV.2003.1238661.

Horvitz, E., Breese, J., Heckerman, D., Hovel, D., and Rommelse, K., 1998. The Lumiere project: Bayesian
user modeling for inferring the goals and needs of software users. In In Proceedings of the Fourteenth Conference
on Uncertainty in Artificial Intelligence, pages 256-265. Madison, WI.

Huber, M. and Durfee, E. H., 1993. Observational Uncertainty in Plan Recognition Among Interacting Robots.
In International joint conference on AI (IJCAI). Workshop on Dynamically Interacting Robots, pages 68-75.

Kaminka, G. A. and Tambe, M., 2000. Robust Agent Teams via Socially-attentive Monitoring. J. Artif. Int.
Res., 12(1): 105-147. ISSN 1076-9757.

Kautz, H. A. and Allen, J. F., 1986. Generalized Plan Recognition. In Kehler, T., editor, Proceedings of the Conference
of the American Association of Artificial Intelligence (AAAI-86), pages 32-37. Morgan Kaufmann.

Lesh, N., Rich, C., and Sidner, C. L., 1999. Using Plan Recognition in Human-computer Collaboration. In Proceedings
of the Seventh International Conference on User Modeling, UM ’99, pages 23-32. Springer- Verlag
New York, Inc., Secaucus, NJ, USA. ISBN 3-211-83151-7.

Masato, D., 2012. Incremental Activity and Plan Recognition for Human Teams. Ph.D. thesis, University of
Aberdeen.

Mausam and Weld, D. S., 2008. Planning with Durative Actions in Stochastic Domains. Journal of Artificial
Intelligence Research, 31(1): 33-82. ISSN 1076-9757.

McCarthy, J., 1986. Applications of Circumscription to Formalizing Common-Sense Knowledge. Artif. Intell.,
28(1): 89-116.

Oh, J., Meneguzzi, F., Sycara, K. P., and Norman, T. J., 2013. Prognostic Normative Reasoning. Eng. Appl. of
AI, 26(2): 863-872.

Panisson, A. R., Freitas, A., Schmidt, D., Hilgert, L., Meneguzzi, F., Vieira, R., and Bordini, R. H., 2015. Arguing
About Task Reallocation Using Ontological Information in Multi-Agent Systems. In 12th International
Workshop on Argumentation in Multiagent Systems.

Pearl, J., 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan
Kaufmann.

Pereira, R. F., Oren, N., and Meneguzzi, F., 2017. Landmark-Based Heuristics for Goal Recognition. In Proceedings
of the 32nd AAAI Conference on Artificial Intelligence.

Pynadath, D. V. and Wellman, M. P., 1995. Accounting for Context in Plan Recognition, with Application to
Traffic Monitoring. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence,
UAI’95, pages 472-481. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. ISBN 1-55860-385-9.

Ramírez, M. and Geffner, H., 2009. Plan Recognition as Planning. In Proc. IJCAI, pages 1778-1783.

Rich, C. and Sidner, C. L., 1997. COLLAGEN: when agents collaborate with people. In Proceedings of the first
international conference on Autonomous agents, AGENTS ’97, pages 284-291. ACM, New York, NY, USA.
ISBN 0-89791-877-0. doi:10.1145/267658.267730.

Sukthankar, G., Goldman, R. P., Geib, C., Pynadath, D. V., and Bui, H. H., editors, 2014. Plan, Activity, and
Intent Recognition: Theory and Practice. Elsevier. ISBN 978-0123985323.

Sukthankar, G. and Sycara, K., 2011. Activity Recognition for Dynamic Multi-Agent Teams. ACM TIST,
3(1):18. Ullmer, B. and Ishii, H., 2000. Emerging Frameworks for Tangible User Interfaces. IBM Syst. J.,
39(3-4): 915-931. ISSN 0018-8670. doi:10.1147/sj.393.0915.

Waern, A., 1996. Recognising Human Plans: Issues for Plan Recognition in Human-Computer Interaction.
Ph.D. thesis, The Royal Institute of Technology and Stockholm University
Farias, G. P., Pereira, R. F., Hilgert, L., Meneguzzi, F., Vieira, R., & Bordini, R. H. (2017). Predicting Plan Failure by Monitoring Action Sequences and Duration. ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 6(4), 55–69. https://doi.org/10.14201/ADCAIJ2017645569

Downloads

Download data is not yet available.
+