article

A probabilistic plan recognition algorithm based on plan tree grammars

Authors:

Christopher W. Geib,

Robert P. GoldmanAuthors Info & Claims

Artificial Intelligence, Volume 173, Issue 11

Pages 1101 - 1132

https://doi.org/10.1016/j.artint.2009.01.003

Published: 01 July 2009 Publication History

Abstract

We present the PHATT algorithm for plan recognition. Unlike previous approaches to plan recognition, PHATT is based on a model of plan execution. We show that this clarifies several difficult issues in plan recognition including the execution of multiple interleaved root goals, partially ordered plans, and failing to observe actions. We present the PHATT algorithm's theoretical basis, and an implementation based on tree structures. We also investigate the algorithm's complexity, both analytically and empirically. Finally, we present PHATT's integrated constraint reasoning for parametrized actions and temporal constraints.

References

[1]

D. Avrahami-Zilberbrand, G.A. Kaminka, Fast and complete symbolic plan recognition, in: Proceedings of the International Joint Conference on Artificial Intelligence, 2005

[2]

Bellman, R., On a routing problem. Quarterly of Applied Mathematics. v16 i1. 87-90.

[3]

Boddy, M., Temporal reasoning for planning and scheduling: Lessons learned. In: Tate, A. (Ed.), Advanced Planning Technology, AAAI Press.

[4]

Boddy, M., Carciofini, J. and Hadden, G., Scheduling with partial orders and a causal model. In: Proceedings of the Space Applications and Research Workshop, Johnson Space Flight Center.

[5]

M. Boddy, R. Goldman, Empirical results on scheduling and dynamic backtracking, in: Proceedings of the International Symposium on Artificial Intelligence, Robotics, and Automation for Space, 1994

[6]

Bui, H.H., Venkatesh, S. and West, G., Policy recognition in the abstract hidden Markov model. Journal of Artificial Intelligence Research. v17. 451-499.

[7]

Chan, H. and Darwiche, A., When do numbers really matter?. Journal of Artificial Intelligence Research. v17. 265-287.

[8]

Charniak, E. and McDermott, D., Introduction to Artificial Intelligence. 1987. Addison-Wesley, Reading MA.

[9]

Charniak, E. and Goldman, R.P., Plan recognition in stories and in life. In: Henrion, M., Schachter, R., Lemmer, J. (Eds.), Uncertainty in Artificial Intelligence 5, Elsevier Science Publishing Co., Inc., New York, NY. pp. 343-351.

[10]

Charniak, E. and Goldman, R.P., A Bayesian model of plan recognition. Artificial Intelligence. v64 i1. 53-79.

[11]

Charniak, E. and Shimony, S.E., Cost-based abduction and MAP explanation. Artificial Intelligence. v66 i2. 345-374.

[12]

Cohen, P.R., Perrault, C.R. and Allen, J.F., Beyond question answering. In: Lehnert, W., Ringle, M. (Eds.), Strategies for Natural Language Processing, Lawrence Erlbaum Associates. pp. 245-274.

[13]

C. Conati, A.S. Gertner, K. VanLehn, M.J. Druzdzel, On-line student modeling for coached problem solving using Bayesian networks, in: Proceedings of the Sixth International Conference on User Modeling, 1997

[14]

Cooper, G.F., The computational complexity of probabilistic inference using Bayesian belief networks. Artificial Intelligence. v42. 393-405.

[15]

Dechter, R., Meiri, I. and Pearl, J., Temporal constraint networks. Artificial Intelligence. v49 i1. 61-95.

[16]

K. Erol, J. Hendler, D.S. Nau, UMCP: A sound and complete procedure for hierarchical task network planning, in: Proceedings of the Second International Conference on Artificial Intelligence Planning Systems (AIPS 94), 1994, pp. 249--254

[17]

Edward Barton, J.G., On the complexity of ID/LP parsing. Computational Linguistics. v11 i4. 205-218.

[18]

Garey, M.R. and Johnson, D.S., Computers and Intractability. 1979. W.H. Freeman and Company, New York.

[19]

Geib, C., Plan recognition. In: Kott, A., McEneaney, W. (Eds.), Adversarial Reasoning, Chapman and Hall/CRC.

[20]

C.W. Geib, R.P. Goldman, Partial observability in collaborative task tracking, in: Proceedings of the AAAI 2001 Fall Symposium on Collaborative Task Tracking, 2001

[21]

C.W. Geib, R.P. Goldman, Plan recognition in intrusion detection systems, in: Proceedings of DISCEX II, 2001

[22]

C.W. Geib, R.P. Goldman, Probabilistic plan recognition for hostile agents, in: Proceedings of the FLAIRS 2001 Conference, 2001

[23]

C.W. Geib, R.P. Goldman, Recognizing plan/goal abandonment, in: Proceedings of IJCAI 2003, 2003

[24]

Ghallab, M., Nau, D. and Traverso, P., Automated Planning: Theory and Practice. 2004. Morgan Kaufmann Publishers, Inc.

[25]

R.P. Goldman, C.W. Geib, C.A. Miller, A new model of plan recognition, in: Proceedings of the 1999 Conference on Uncertainty in Artificial Intelligence, 1999

[26]

Hobbs, J.R., Stickel, M.E., Appelt, D.E. and Martin, P.A., Interpretation as abduction. Artificial Intelligence. v63 i1--2. 69-142.

[27]

A. Hoogs, A.A. Perera, Video activity recognition in the real world, in: Proceedings of the Conference of the American Association of Artificial Intelligence (2008), 2008, pp. 1551--1554

[28]

Hopcroft, J.E. and Ullman, J.D., Introduction to Automata Theory, Languages, and Computation. 1979. Addison Wesley.

[29]

I. Horrocks, Using an expressive description logic: FaCT or fiction? in: Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR '98), 1998

[30]

E. Horvitz, J. Breese, D. Heckerman, D. Hovel, K. Rommelse, The Lumiere project: Bayesian user modeling for inferring the goals and needs of software users, in: Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, 1998

[31]

M.J. Huber, E.H. Durfee, M.P. Wellman, The automated mapping of plans for plan recognition, in: Proceedings of the Twelfth National Conference on Artificial Intelligence 1994, pp. 344--351

[32]

M. Jan Nederhof, G. Satta, S.M. Shieber, Partially ordered multiset context-free grammars and ID/LP parsing, in: Proceedings of the Eighth International Workshop on Parsing Technologies, Nancy, France, April 2003, pp. 171--182

[33]

Joshi, A. and Schabes, Y., Tree-adjoining grammars. In: Handbook of Formal Languages, vol. 3. Springer Verlag. pp. 69-124.

[34]

Kaminka, G., Pynadath, D. and Tambe, M., Monitoring teams by overhearing: A multi-agent plan-recognition approach. Journal of Artificial Intelligence Research. v17 i1. 83-135.

[35]

H. Kautz, A formal theory of plan recognition and its implementation, PhD thesis, University of Rochester, 1991

[36]

H. Kautz, J.F. Allen, Generalized plan recognition, in: Proceedings of the Conference of the American Association of Artificial Intelligence (AAAI-86), 1986, pp. 32--38

[37]

Ford, J.L.R. and Fulkerson, D.R., Flows in Networks. 1962. Princeton University Press, Princeton.

[38]

L. Liao, D. Fox, H. Kautz, Learning and inferring transportation routines, in: Proceedings of AAAI 2004, 2004

[39]

Liao, L., Fox, D. and Kautz, H., Extracting places and activities from GPS traces using hierarchical conditional random fields. International Journal of Robotics Research. v26. 119-134.

[40]

L. Liao, D. Fox, H.A. Kautz, Location-based activity recognition using relational Markov networks, in: Proceedings of the 19th International Joint Conference on Artificial Intelligence, 2005, pp. 773--778

Digital Library

[41]

McCarthy, J., Circumscription --- A form of non-monotonic reasoning. Artificial Intelligence. v13. 27-39.

[42]

J. Modayil, T. Bai, H. Kautz, Improving the recognition of interleaved activities, in: Proceedings of the Tenth International Conference on Ubiquitous Computing, 2008

[43]

Peot, M. and Shachter, R., Learning from what you don't observe. In: Uncertainty in Artificial Intelligence, Proceedings of the Fourteenth Conference, San Francisco, CA, Morgan Kaufmann Publishers. pp. 439-446.

[44]

Poole, D., Logic programming, abduction and probability: A top-down anytime algorithm for estimating prior and posterior probabilities. New Generation Computing. v11 i3--4. 377-400.

[45]

Poole, D., Probabilistic Horn abduction and Bayesian networks. Artificial Intelligence. v64. 81-129.

[46]

Pradhan, M., Henrion, M., Provan, G., Favero, B.D. and Huang, K., The sensitivity of belief networks to imprecise probabilities: An experimental investigation. Artificial Intelligence. v85 i1--2. 363-397.

[47]

D. Pynadath, M. Wellman, Probabilistic state-dependent grammars for plan recognition, in: Uncertainty in Artificial Intelligence, Proceedings of the Sixteenth Conference, 2000, pp. 507--514

[48]

Santos Jr., E., A linear constraint satisfaction approach to cost-based abduction. Artificial Intelligence. v65 i1. 1-28.

[49]

Schmidt, C., Sridharan, N. and Goodson, J., The plan recognition problem: An intersection of psychology and artificial intelligence. Artificial Intelligence. v11. 45-83.

[50]

Shimony, S.E., Finding MAPs for belief networks Is NP-hard. Artificial Intelligence. v68 i2. 399-410.

[51]

Sidner, C.L., Plan parsing for intended response recognition in discourse. Computational Intelligence. v1 i1. 1-10.

[52]

D.L. Vail, M.M. Veloso, Feature selection for activity recognition in multi-robot domains, in: Proceedings of the Conference of the American Association of Artificial Intelligence (2008), 2008, pp. 1415--1420

[53]

M. Vilain, Deduction as parsing, in: Proceedings of the Conference of the American Association of Artificial Intelligence (1991), 1991, pp. 464--470

[54]

Wellman, M.P., Breese, J.S. and Goldman, R.P., From knowledge bases to decision models. Knowledge Engineering Review. v7 i1. 35-53.

[55]

Wilensky, R., Planning and Understanding. 1983. Addison-Wesley.

Cited By

Harman HSimoens P(2024)Cyclic Action Graphs for goal recognition problems with inaccurately initialised fluentsKnowledge and Information Systems10.1007/s10115-023-01976-666:2(1257-1300)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10115-023-01976-6
Dann MYao YAlechina NLogan BMeneguzzi FThangarajah JElkind E(2023)Multi-agent intention recognition and progressionProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/11(91-99)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/11
Nguyen DNguyen PLe HDo KVenkatesh STran TWilliams BChen YNeville J(2023)Memory-augmented theory of mind networkProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26374(11630-11637)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26374
Show More Cited By

Recommendations

Goal and Plan Recognition Design for Plan Libraries
Survey Papers and Regular Papers

This article provides new techniques for optimizing domain design for goal and plan recognition using plan libraries. We define two new problems: Goal Recognition Design for Plan Libraries (GRD-PL) and Plan Recognition Design (PRD). Solving the GRD-PL ...
A unified constraint-based approach for plan and goal recognition from unreliable observations
Abstract
Given a sequence of observations over a plan execution, plan and goal recognition are considered as interchangeable tasks in AI planning. However, strictly speaking, the former tries to identify a plan, and the latter a set of goals, that explain ...
Epistemic Plan Recognition
AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems

The plan recognition task is to infer an actor's plan and goal given observations about its behavior. We submit that in some cases, for plan recognition to be effective and complete, it must appeal to a notion of epistemics to i) recognize epistemic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier B.V. © 2009.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 July 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Harman HSimoens P(2024)Cyclic Action Graphs for goal recognition problems with inaccurately initialised fluentsKnowledge and Information Systems10.1007/s10115-023-01976-666:2(1257-1300)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10115-023-01976-6
Dann MYao YAlechina NLogan BMeneguzzi FThangarajah JElkind E(2023)Multi-agent intention recognition and progressionProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/11(91-99)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/11
Nguyen DNguyen PLe HDo KVenkatesh STran TWilliams BChen YNeville J(2023)Memory-augmented theory of mind networkProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26374(11630-11637)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26374
Nguyen DNguyen PLe HDo KVenkatesh STran TPelachaud CTaylor MFaliszewski PMascardi V(2022)Learning Theory of Mind via Dynamic Traits AttributionProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3535957(954-962)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3535957
Gupta ACarpenter DMin WRowe JAzevedo RLester JWare SEger M(2022)Enhancing multimodal goal recognition in open-world games with natural language player reflectionsProceedings of the Eighteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment10.1609/aiide.v18i1.21945(37-44)Online publication date: 24-Oct-2022
https://dl.acm.org/doi/10.1609/aiide.v18i1.21945
Xu DHu RWang ZLuo LLi DZeng WMagalhães Jdel Bimbo ASatoh SSebe NAlameda-Pineda XJin QOria VToni L(2022)Gaze- and Spacing-flow Unveil Intentions: Hidden Follower DiscoveryProceedings of the 30th ACM International Conference on Multimedia10.1145/3503161.3548207(2115-2123)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3503161.3548207
Lieck RRohrmeier MRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Recursive Bayesian networksProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3540595(4370-4383)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3540595
Winikoff MSidorenko GDignum VDignum F(2021)Why bad coffee? Explaining BDI agent behaviour with valuingsArtificial Intelligence10.1016/j.artint.2021.103554300:COnline publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.artint.2021.103554
Harman HSimoens P(2020)Action graphs for proactive robot assistance in smart environmentsJournal of Ambient Intelligence and Smart Environments10.3233/AIS-20055612:2(79-99)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.3233/AIS-200556
Zhuo HZha YKambhampati STian X(2020)Discovering Underlying Plans Based on Shallow ModelsACM Transactions on Intelligent Systems and Technology10.1145/336827011:2(1-30)Online publication date: 24-Jan-2020
https://dl.acm.org/doi/10.1145/3368270
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents