Inferring Agents’ Goals from Observing Successful Traces
Source abstract
Abstract
Goal recognition is a sub-field of plan recognition that focuses on the goals of an agent. Current approaches in goal recognition have not yet tried to apply concept learning to a propositional logic formalism. In this paper, we extend our method for inferring an agent’s possible goal by observing this agent in a series of successful attempts to reach its goal and using concept learning on these observations. We propose an algorithm, LFST (Learning From Successful Traces), to produce concise hypotheses about the agent’s goal. We show that if such a goal exists, our algorithm always provides a possible goal for the agent, and we evaluate the performance of our algorithm in different settings. We compare it to another concept-learning algorithm that uses a formalism close to ours, and we obtain better results at producing the hypotheses with our algorithm. We introduce a way to use assumptions about the agent’s behavior and the dynamics of the environment, thus improving the agent’s goal deduction by optimizing the potential goals’ search space.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Multi-Agent Systems and Negotiation · Reinforcement Learning in Robotics
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
Department of Informatics, The Graduate University for Advanced Studies, SOKENDAI, Tokyo 101-8430, Japan
LIP6, Sorbonne Université—CNRS UMR 7606, 75005 Paris, France
References (36)
Show source-provided references
1. E-Martin, Y., R-Moreno, M.D., and Smith, D.E. (2015, January 26–27). Practical Goal Recognition for ISS Crew Activities. Proceedings of the IJCAI the International Workshop on Planning and Scheduling for Space 2015 (IWPSS), Buenos Aires, Argentina.
2. Ognibene, D., Mirante, L., and Marchegiani, L. (2019, January 26–29). Proactive Intention Recognition for Joint Human-Robot Search and Rescue Missions through Monte-Carlo Planning in POMDP Environments. Proceedings of the International Conference on Social Robotics, Madrid, Spain.10.1007/978-3-030-35888-4_31 ↗
3. The Plan Recognition Problem: An Intersection of Psychology and Artificial Intelligence10.1016/0004-3702(78)90012-7 ↗
4. A Bayesian model of plan recognition10.1016/0004-3702(93)90060-O ↗
5. A probabilistic plan recognition algorithm based on plan tree grammars10.1016/j.artint.2009.01.003 ↗
6. Singla, P., and Mooney, R.J. (2011, January 7–11). Abductive Markov Logic for Plan Recognition. Proceedings of the Twenty-Fifth National Conference on Artificial Intelligence 2011, San Francisco, CA, USA.
7. Kabanza, F., Bellefeuille, P., Bisson, F., Benaskeur, A.R., and Irandoust, H. (2010, January 11–15). Opponent Behaviour Recognition for Real-time Strategy Games. Proceedings of the 5th AAAI Conference on Plan, Activity, and Intent Recognition, Atlanta, GA, USA.
8. Ha, E., Rowe, J.P., Mott, B.W., and Lester, J.C. (2011, January 10–14). Goal Recognition with Markov Logic Networks for Player-Adaptive Games. Proceedings of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 2011, Stanford, CA, USA.
9. Min, W., Mott, B., Rowe, J., Liu, B., and Lester, J. (2016, January 9–15). Player Goal Recognition in Open-world Digital Games with Long Short-term Memory Networks. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, New York, NY, USA.
10. Techniques for Plan Recognition10.1023/A:1011118925938 ↗
11. Sukthankar, G., Geib, C., Bui, H.H., Pynadath, D.V., and Goldman, R.P. (2014). Plan, Activity, and Intent Recognition, Elsevier.
12. Ramirez, M., and Geffner, H. (2009, January 9). Plan Recognition As Planning. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), New York, NY, USA.
13. Cardona-Rivera, R.E., and Michael Young, R. (2017, January 4–9). Toward Combining Domain Theory and Recipes in Plan Recognition. Proceedings of the AAAI 2017 Workshop on Plan, Activity, and Intent Recognition, San Francisco, CA, USA.
14. Escudero Martin, Y., and Smith, D.E. (2017, January 4–9). Goal Recognition with Noisy Observations. Proceedings of the AAAI 2017 Workshop on Plan, Activity, and Intent Recognition, San Francisco, CA, USA.
15. Mirsky, R., Stern, R., Gal, Y., and Kalech, M. (2017, January 4–9). Plan Recognition Design. Proceedings of the AAAI 2017 Workshop on Plan, Activity, and Intent Recognition, San Francisco, CA, USA.10.1609/aaai.v31i1.11092 ↗
16. Goldman, R.P., Friedman, S.E., and Rye, J.M. (2018, January 8–14). Plan Recognition for Network Analysis: Preliminary Report. Proceedings of the AAAI 2018 Workshop on Plan, Activity, and Intent Recognition, Munich, Germany.
17. Vered, M., Pereira, R.F., Magnaguagno, M.C., Meneguzzi, F., and Kaminka, G.A. (2018, January 8–14). Online Goal Recognition as Reasoning over Landmarks. Proceedings of the AAAI 2018 Workshop on Plan, Activity, and Intent Recognition, Munich, Germany.
18. Lang, J. (2004, January 3–7). A Preference-based Interpretation of Other Agents’ Actions. Proceedings of the International Conference on Automated Planning and Scheduling 2004, Whistler, BC, Canada.
19. Ramırez, M., and Geffner, H. (2010, January 11–15). Probabilistic plan recognition using off-the-shelf classical planners. Proceedings of the Conference of the Association for the Advancement of Artificial Intelligence (AAAI 2010), Atlanta, GA, USA.
20. Ramırez, M., and Geffner, H. (2011, January 16–22). Goal recognition over POMDPs: Inferring the intention of a POMDP agent. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, Barcelona, Spain.
21. Baker, C.L., Tenenbaum, J.B., and Saxe, R.R. (2007, January 1–4). Goal inference as inverse planning. Proceedings of the Annual Meeting of the Cognitive Science Society, Nashville, TN, USA.
22. Action understanding as inverse planning10.1016/j.cognition.2009.07.005 ↗
23. Rational quantitative attribution of beliefs, desires and percepts in human mentalizing10.1038/s41562-017-0064 ↗
24. Goal Recognition Through Goal Graph Analysis
25. Lorthioir, G., Bourgne, G., and Inoue, K. (2018, January 18–20). Identifying Goals of Agents by Learning from Observations. Proceedings of the International Conference on Multi-disciplinary Trends in Artificial Intelligence, Hanoi, Vietnam.10.1007/978-3-030-03014-8_11 ↗
26. Henniche, M. (December, January 29). MGI: An Incremental Bottom-Up Algorithm. Proceedings of the Australian New Zealand Intelligent Information Systems Conference, Brisbane, Australia.
27. Salzberg, S.L. (1993). C4. 5: Programs for Machine Learning by j. Ross Quinlan, Morgan Kaufmann Publishers, Inc.
28. Induction of Decision Trees10.1007/BF00116251 ↗
29. Synnaeve, G., and Bessiere, P. (2011, January 11–14). A Bayesian model for plan recognition in RTS games applied to StarCraft. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Palo Alto, CA, USA.10.1609/aiide.v7i1.12429 ↗
30. Weber, B.G., and Mateas, M. (2009, January 7–10). A data mining approach to strategy prediction. Proceedings of the 2009 IEEE Symposium on Computational Intelligence and Games, Milan, Italy.10.1109/CIG.2009.5286483 ↗
31. Cohen, W.W. (1996, January 4–8). Trees and Rules with Set-Valued Features. Proceedings of the AAAI Thirteenth National Conference on Artificial Intelligence, Portland, OR, USA.
32. A theory of the learnable10.1145/1968.1972 ↗
33. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution10.1006/jcss.1997.1533 ↗
34. More efficient PAC-learning of DNF with membership queries under the uniform distribution10.1016/j.jcss.2003.10.002 ↗
35. Learning from interpretation transition10.1007/s10994-013-5353-8 ↗
36. Bourgne, G., El Fallah Segrouchni, A., and Soldano, H. (2007, January 14–18). Smile: Sound multi-agent incremental learning. Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, Honolulu, HI, USA.10.1145/1329125.1329171 ↗