Predicting Plan Failure by Monitoring Action Sequences and Duration

  • Giovani Parente Farias
    Pontifical Catholic University of Rio Grande do Sul – PUCRS giovanifarias[at]gmail.com
  • Ramon Fraga Pereira
    Pontifical Catholic University of Rio Grande do Sul – PUCRS
  • Lucas W. Hilgert
    Pontifical Catholic University of Rio Grande do Sul – PUCRS
  • Felipe Meneguzzi
    Pontifical Catholic University of Rio Grande do Sul – PUCRS
  • Renata Vieira
    Pontifical Catholic University of Rio Grande do Sul – PUCRS
  • Rafael H. Bordini

Abstract

An agent can attempt to achieve multiple goals and each goal can be achieved by applying various different plans. 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. Symbolic Plan Recognition is an algorithm that represents knowledge about the agents under observation in the form of a plan library. In this work, we use this symbolic algorithm to find out which plan the agent is performing and we develop a failure prediction system, based on information available in the plan library and in a simplified calendar which 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 be performing. We have successfully employed this approach 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. https://doi.org/10.1023/A:1008238218679

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. https://doi.org/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. https://doi.org/10.1109/CAIA.1989.49160

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
https://doi.org/10.1016/j.cognition.2009.07.005

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. https://doi.org/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.

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. https://doi.org/10.1109/discex.2001.932191

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. https://doi.org/10.1023/A:1006673610113

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. https://doi.org/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. https://doi.org/10.1007/978-3-7091-2490-1_3

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. https://doi.org/10.1016/0004-3702(86)90032-9

Oh, J., Meneguzzi, F., Sycara, K. P., and Norman, T. J., 2013. Prognostic Normative Reasoning. Eng. Appl. of AI, 26(2):863–872. https://doi.org/10.1016/j.engappai.2012.12.006

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. https://doi.org/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. https://doi.org/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. W., 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(2), 71–84. https://doi.org/10.14201/ADCAIJ2017627184

Most read articles by the same author(s)

Downloads

Download data is not yet available.
+