Complexity Issues in Multiagent Logics

• Autorzy: Dziubiński M. , Verbrugge R. , Dunin-Kęplicz B.
• Języki publikacji: EN

Abstrakty

EN

Our previous research presents a methodology of cooperative problem solving for belief-desire-intention (BDI) systems, based on a complete formal theory called TeamLog. This covers both a static part, defining individual, bilateral and collective agent attitudes, and a dynamic part, describing system reconfiguration in a dynamic, unpredictable environment. In this paper, we investigate the complexity of the satisfiability problem of the static part of TeamLog, focusing on individual and collective attitudes up to collective intention. Our logics for teamwork are squarely multi-modal, in the sense that different operators are combined and may interfere. One might expect that such a combination is much more complex than the basic multi-agent logic with one operator, but in fact we show that it is not the case: the individual part of TeamLog is PSPACE-complete, just like the single modality case. The full system, modelling a subtle interplay between individual and group attitudes, turns out to be EXPTIME-complete, and remains so even when propositional dynamic logic is added to it. Additionally we make a first step towards restricting the language of TeamLog in order to reduce its computational complexity. We study formulas with bounded modal depth and show that in case of the individual part of our logics, we obtain a reduction of the complexity to NPTIME-completeness. We also show that for group attitudes in TeamLog the satisfiability problem remains in EXPTIME-hard, even when modal depth is bounded by 2. We also study the combination of reducing modal depth and the number of propositional atoms. We show that in both cases this allows for checking the satisfiability in linear time.

Słowa kluczowe

EN

multi-modal logical; system TEAMLOG

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 75, nr 1-4
• Strony: 239--262
• Opis fizyczny: bibliogr. 24 poz.

Twórcy

autor

Dziubiński M.

autor

Verbrugge R.

autor

Dunin-Kęplicz B.

• Institute of Informatics Warsaw University ul. Banacha 2 02-097 Warsaw, Poland,

Bibliografia

• [1] Aldewereld, H., van der Hoek,W.,Meyer, J.-J. C.: Rational Teams: Logical Aspects ofMulti-Agent Systems, Fundamenta Informaticae, 63 (2,3), 2004, 159-183.
• [2] van Benthem, J.: Correspondence Theory, in: Handbook of Philosophical Logic (D. Gabbay, F. Guenthner, Eds.), vol. 2, Reidel, Dordrecht, 1984, 167-247.
• [3] Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic, vol. 53 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 2002, ISBN 0-521-52714-7.
• [4] Blackburn, P., Spaan, E.: A Modal Perspective on the Computational Complexity of Attribute Value Grammar, Journal of Logic, Language and Information, 2, 1993, 129-169.
• [5] Cadoli, M.: Tractable Reasoning in Artificial Intelligence, Number 941 in Lecture Notes in Artificial Intelligence,Springer, 1995.
• [6] Chlebus, B.: Domino-tiling Games, Journal of Computer and System Sciences, 32, 1986, 374-392.
• [7] Doherty, P., Łukaszewicz, W., Skowron, A., Szałas, A.: Knowledge Representation Techniques. A Rough Set Approach, vol. 202 of Studies in Fuziness and Soft Computing, Springer Verlag, 2006.
• [8] Doherty, P., Łukaszewicz,W., Szałas, A.: Computing Strongest Necessary andWeakest Sufficient Conditions of First-Order Formulas, International Joint Conference on AI (IJCAI'2001), 2000, 145 - 151.
• [9] Dunin-Kęplicz, B., Verbrugge, R.: Collective Intentions, Fundamenta Informaticae, 51(3), 2002, 271-295.
• [10] Dunin-Kęplicz, B., Verbrugge, R.: Evolution of Collective Commitments During Teamwork, Fundamenta Informaticae, 56, 2003, 329-371.
• [11] Dunin-Kęplicz, B., Verbrugge, R.: A Tuning Machine for Cooperative Problem Solving, Fundamenta Informaticae, 63, 2004, 283-307.
• [12] Dunin-Kęplicz, B., Verbrugge, R.: Creating Common Beliefs in Rescue Situations, Monitoring, Security, and Rescue Techniques in Multiagent Systems (B. Dunin-Kęplicz, A. Jankowski, A.Skowron, M.Szczuka, Eds.), Advances in Soft Computing, Springer Verlag, Berlin, 2005.
• [13] Dziubiński, M., Verbrugge, R., Dunin-Kęplicz, B.: Complexity of a Theory of Collective Attitudes in Teamwork, International Conference on Intelligent Agent Technology (IAT 2005), IEEE Computer Society, Los Alamitos (CA), 2005.
• [14] Fagin, R., Halpern, J., Moses, Y., Vardi, M.: Reasoning about Knowledge, MIT Press, Cambridge, MA, 1995.
• [15] Halpern, J. Y.: The Effect of Bounding the Number of Primitive Propositions and the Depth of Nesting on the Complexity of Modal Logic, Artificial Intelligence, 75(3), 1995, 361-372, ISSN 0004-3702.
• [16] Halpern, J. Y., Moses, Y.: A Guide to Completeness and Complexity for Modal Logics of Knowledge and Belief, Artificial Intelligence, 54(3), 1992, 319-379, ISSN 0004-3702.
• [17] Harel, D., Kozen, D., Tiuryn, J.: Dynamic Logic, MIT Press, Cambridge, MA, 2000.
• [18] Hustadt, U., Schmidt, R.: On Evaluating Decision Procedures for Modal Logics, Proceedings IJCAI'97 (M. Pollack, Ed.), Morgan Kauffman, Los Angeles (CA), 1997.
• [19] Kacprzak, M., Lomuscio, A., Penczek, W.: From Bounded to Unbounded Model Checking for Interpreted Systems, Fundamenta Informaticae, 63 (2,3), 2004, 107-308.
• [20] Kautz, H., Selman, B.: Knowledge Compilation and Theory Approximation, Journal of the ACM, 43(2), 1996, 193-224.
• [21] Lin, F.: On strongest Necessary and Weakest sufficient Conditions, Proc. 7th International Conf. on Principles of Knowledge Representation and Reasoning, KR2000 (A. Cohn, F. Giunchiglia, B. Selman, Eds.), Morgan Kaufmann Pub., Inc., 2000.
• [22] Nguyen, L. A.: On the Complexity of Fragments of Modal Logics, Advances in Modal Logic 5, Papers from the Fifth Conference on "Advances inModal logic," held inManchester (UK) in September 2004 (R. Schmidt, I. Pratt-Hartmann, M. Reynolds, H. Wansing, Eds.), King's College Publications, 2004.
• [23] Pawlak, Z.: Information Systems - Theoretical Foundations, Information Systems, 6, 1981, 205-218.
• [24] Pawlak, Z.: Rough Sets. Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht,1991.