Planning with Subjective Knowledge in a Multi-Agent Scenario
Pages 1 - 9
Abstract
The AI community has always been interested in designing intelligent agents which function in a multi-agent arrangement or a man-machine scenario. More often than not, such settings may require agents to work autonomously (or under intermittent supervision at the least) in partially observable environments. Over the last 10 years or so, the planning community has started looking at this interesting class of problems from an epistemic standpoint, by augmenting the notions of knowledge and beliefs to AI planning. In this paper, we present a system that synthesizes plans from the primary agent’s perspective, based on its subjective knowledge, in a multi-agent environment. We adopt a semantic approach to represent the mental model of the primary agent whose uncertainty about the world is represented using Kripke’s possible worlds interpretation of epistemic logic. Planning in this logical framework is computationally challenging, and, to the best of our knowledge, most of the existing planners work with the notion of knowledge, instead of an agent’s subjective knowledge. We demonstrate the system’s capability of projecting beliefs of the primary agent on to others, reasoning about the role of other agents in the prospective plans, and preferring the plans that hinge on the primary agent’s capabilities to those which demand others’ cooperation. We evaluate our system on the problems discussed in the literature and show that it takes fractions of seconds to search for a plan for a given problem. We also discuss the issues that arise in modeling dynamic domains with the representation our system employs.
References
[1]
Guillaume Aucher and Thomas Bolander. 2013. Undecidability in epistemic planning. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI-13).
[2]
Alexandru Baltag and Lawrence S Moss. 2004. Logics for epistemic programs. Synthese 139, 2 (2004), 165–224.
[3]
Chitta Baral, Thomas Bolander, Hans van Ditmarsch, and Sheila McIlrath. 2017. Epistemic Planning (Dagstuhl Seminar 17231). In Dagstuhl Reports, Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[4]
Chitta Baral, Gregory Gelfond, Enrico Pontelli, and Tran Cao Son. 2015. An action language for multi-agent domains: Foundations. arXiv preprint arXiv:1511.01960(2015).
[5]
Thomas Bolander. 2017. A gentle introduction to epistemic planning: The DEL approach. In Electronic Proceedings in Theoretical Computer Science. Vol. 243. Open Publishing Association, 1–22.
[6]
Thomas Bolander. 2018. Seeing Is Believing: Formalising False-Belief Tasks in Dynamic Epistemic Logic. Springer International Publishing, Cham, 207–236. https://doi.org/10.1007/978-3-319-62864-6_8
[7]
Thomas Bolander and Mikkel Birkegaard Andersen. 2011. Epistemic planning for single-and multi-agent systems. Journal of Applied Non-Classical Logics 21, 1 (2011), 9–34.
[8]
Tristan Charrier, Bastien Maubert, and François Schwarzentruber. 2016. On the impact of modal depth in epistemic planning. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16). 1030–1036.
[9]
David Christian and R Michael Young. 2004. Strategic deception in agents. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 1. IEEE Computer Society, 218–226.
[10]
Joao Dias, Samuel Mascarenhas, and Ana Paiva. 2014. Fatima modular: Towards an agent architecture with a generic appraisal framework. In Emotion modeling. Springer, Cham, 44–56.
[11]
João Dias and Ana Paiva. 2005. Feeling and reasoning: A computational model for emotional characters. In Proceedings of the 12th Portuguese conference on Progress in Artificial Intelligence. Springer, Berlin, Heidelberg, 127–140.
[12]
Julia Donaldson. 1999. The Gruffalo. Pan Macmillan.
[13]
Markus Eger and Chris Martens. 2017. Character beliefs in story generation. In Thirteenth Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE-17).
[14]
Thorsten Engesser, Thomas Bolander, Robert Mattmüller, and Bernhard Nebel. 2017. Cooperative epistemic multi-agent planning for implicit coordination. In Electronic Proceedings in Theoretical Computer Science. Vol. 243. Open Publishing Association, 75–90.
[15]
Ronald Fagin, Joseph Y Halpern, Yoram Moses, and Moshe Vardi. 2004. Reasoning about knowledge. MIT press.
[16]
James Hales, Tim French, and Rowan Davies. 2012. Refinement Quantified Logics of Knowledge and Belief for Multiple Agentsc.Advances in Modal Logic 9 (2012), 317–338.
[17]
Jaakko Hintikka. 1962. Knowledge and Belief. Ithaca, N.Y.:Cornell University Press.
[18]
Xiao Huang, Biqing Fang, Hai Wan, and Yongmei Liu. 2017. A General Multi-agent Epistemic Planner Based on Higher-order Belief Change. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17). 1093–1101.
[19]
Filippos Kominis and Hector Geffner. 2015. Beliefs in multiagent planning: From one agent to many. In Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling (ICAPS-15).
[20]
Filippos Kominis and Hector Geffner. 2017. Multiagent online planning with nested beliefs and dialogue. In Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling (ICAPS-17).
[21]
Gerhard Lakemeyer and Yves Lespérance. 2012. Efficient Reasoning in Multiagent Epistemic Logics. In Proceedings of the Twentieth European Conference on Artificial Intelligence. IOS Press, 498–503.
[22]
Tiep Le, Francesco Fabiano, Tran Cao Son, and Enrico Pontelli. 2018. EFP and PG-EFP: Epistemic forward search planners in multi-agent domains. In Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS-18).
[23]
Qiang Liu and Yongmei Liu. 2018. Multi-agent epistemic planning with common knowledge. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-18). 1912–1920.
[24]
Benedikt Löwe, Eric Pacuit, and Andreas Witzel. 2011. DEL Planning and Some Tractable Cases. In Logic, Rationality, and Interaction, Hans van Ditmarsch, Jérôme Lang, and Shier Ju(Eds.). Springer, Berlin, Heidelberg, 179–192.
[25]
Christian Muise, Vaishak Belle, Paolo Felli, Sheila McIlraith, Tim Miller, Adrian R Pearce, and Liz Sonenberg. 2015. Planning over multi-agent epistemic states: A classical planning approach. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15).
[26]
Linh Anh Nguyen. 2000. Constructing the least models for positive modal logic programs. Fundamenta Informaticae 42, 1 (2000), 29–60.
[27]
Linh Anh Nguyen. 2008. Constructing finite least Kripke models for positive logic programs in serial regular grammar logics. Logic Journal of IGPL 16, 2 (2008), 175–193.
[28]
Chris Pearce, Ben Meadows, Pat Langley, and Mike Barley. 2014. Social planning: Achieving goals by altering others’ mental states. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14).
[29]
Henrique Daniel Santarém Reis. 2012. Lie to me: Lying virtual agents. Ph.D. Dissertation. Master’s thesis, Universidade Técnica de Lisboa.
[30]
Alireza Shirvani, Rachelyn Farrell, and Stephen G Ware. 2018. Combining Intentionality and Belief: Revisiting Believable Character Plans. In Fourteenth Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE-18).
[31]
Maayan Shvo. 2019. Towards Empathetic Planning and Plan Recognition. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society. 525–526.
[32]
Shikha Singh and Deepak Khemani. 2019. Deception: An Epistemic Planned Event?Workshop on Logic and Cognition, ICLA-19.
[33]
Shikha Singh and Deepak Khemani. 2019. Planning to Deceive in a Multi-agent Scenario. In Proceedings of the Seventh Annual Conference on Advances in Cognitive Systems (ACS-19), M. T. Cox (Ed.). Tech. Rep. No. COLAB2-TR-4. Dayton, OH: Wright State University, Collaboration and Cognition Laboratory, 473–491.
[34]
Tran Cao Son, Enrico Pontelli, Chitta Baral, and Gregory Gelfond. 2014. Finitary S5-Theories. In Logics in Artificial Intelligence, Eduardo Fermé and João Leite (Eds.). Springer, Cham, 239–252.
[35]
Tran Cao Son, Enrico Pontelli, Chitta Baral, and Gregory Gelfond. 2015. Exploring the kd45 property of a kripke model after the execution of an action sequence. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15). 1604–1610.
[36]
Jonathan Teutenberg and Julie Porteous. 2015. Incorporating global and local knowledge in intentional narrative planning. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS-15). International Foundation for Autonomous Agents and Multiagent Systems, 1539–1546.
[37]
Wiebe Van Der Hoek and Michael Wooldridge. 2002. Tractable multiagent planning for epistemic goals. In Proceedings of the first international joint conference on Autonomous agents and multiagent systems (AAMAS-02), C. Castelfranchia and W. Johnson (Eds.). ACM Press, New York, 1167–1174.
[38]
Hans Van Ditmarsch, Wiebe van Der Hoek, and Barteld Kooi. 2007. Dynamic epistemic logic. Vol. 337. Springer Science & Business Media.
- Planning with Subjective Knowledge in a Multi-Agent Scenario
Recommendations
A Plan Based Coalition Formation Model for Multi-agent Systems
WI-IAT '11: Proceedings of the 2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology - Volume 02This article addresses the coalition formation problem in a multi-agent context where agents plan their activities dynamically and use these plans to coordinate their actions and form suitable coalitions. In most coalition formation methods, when ...
An abstract knowledge based approach to diagnosis and recovery of plan failure in multi-agent systems
Open multi-agent systems (MAS) are decentralised and distributed systems that consist of a large number of loosely coupled autonomous agents. In the absence of centralised control they tend to be difficult to manage, especially in an open environment, ...
Multi-Agent Planning and Diagnosis with Commonsense Reasoning
DAI '23: Proceedings of the Fifth International Conference on Distributed Artificial IntelligenceIn multi-agent systems, multi-agent planning and diagnosis are two key subfields – multi-agent planning approaches identify plans for the agents to execute in order to reach their goals, and multi-agent diagnosis approaches identify root causes for ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2020
249 pages
ISBN:9781450388788
DOI:10.1145/3411408
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 September 2020
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
SETN 2020
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 133Total Downloads
- Downloads (Last 12 months)18
- Downloads (Last 6 weeks)1
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format