Predicting Plan Failure by Monitoring Action Sequences and Duration

Giovani Parente FARIAS, Ramon Fraga PEREIRA, Lucas HILGERT, Felipe MENEGUZZI, Renata VIEIRA, Rafael Heitor BORDINI

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.


Keywords


Failure Prediction; Plan Recognition; Multi-agent System

References


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,

(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-

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):

-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,

: 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:

-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.,

(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,

(1):18. Ullmer, B. and Ishii, H., 2000. Emerging Frameworks for Tangible User Interfaces. IBM Syst. J.,

(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




DOI: http://dx.doi.org/10.14201/ADCAIJ2017645569





Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.