Agents that Know How to Play

• Autorzy: Jamroga W. , Van der Hoek W.
• Języki publikacji: EN

Abstrakty

EN

We look at ways to enrich Alternating-time Temporal Logic (ATL) - a logic for specification and verification of multi-agent systems - with a notion of knowledge. Starting point of our study is a recent proposal for a system called Alternating-time Temporal Epistemic Logic (ATEL). We show that, assuming that agents act under uncertainty in some states of the system, the notion of allowable strategy should be defined with some caution. Moreover, we demonstrate a subtle difference between an agent knowing that he has a suitable strategy and knowing the strategy itself. We also point out that the agents should be assumed similar epistemic capabilities in the semantics of both strategic and epistemic operators. Trying to implement these ideas, we propose two different modifications of ATEL. The first one, dubbed Alternating-time Temporal Observational Logic (ATOL), is a logic for agents with bounded recall of the past. With the second, ATEL-R*, we present a framework to reason about both perfect and imperfect recall, in which we also incorporate operators for reasoning about the past. We identify some feasible subsystems of this expressive system.

Słowa kluczowe

EN

multi-agent systems; temporal logic; epistemic logics; knowledge; transition systems; games with incomplete information

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 63, nr 2,3
• Strony: 185--219
• Opis fizyczny: Bibliogr. 32 poz, tab., wykr.

Twórcy

autor

Jamroga W.

• Parlevink Group, University of Twente, PO Box 217, Nl-7500 AE Enschede, Netherlands

autor

Van der Hoek W.

• Department of Computer Science, University of Liverpool, UK

Bibliografia

• [1] Alur, R., de Alfaro, L., Henzinger, T. A., Krishnan, S., Mang, F., Qadeer, S., Rajamani, S., Tasiran, S.: MOCHA User Manual, Technical report, University of Berkeley, 2000.
• [2] Alur, R., Henzinger, T. A., Kupferman, O.: Alternating-Time Temporal Logic, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, 1997, Available at citeseer.ist.psu.edu/170985.htlm.
• [3] Alur, R., Henzinger, T. A., Kupferman, O.: Alternating-Time Temporal Logic, Lecture Notes in Computer Science, 1536, 1998, 23-60, Available at citeseer.ist.psu.edu/174802.htlm.
• [4] Alur, R., Henzinger, T. A., Kupferman, O.: Alternating-Time Temporal Logic, Journal of the ACM, 49, 2002, 672-713, Updated, improved, and extended text. Available at www.cis.upenn.edu/alur/Jacm02.pdf.
• [5] van Benthem, J.: Games in Dynamic Epistemic Logic, Bulletin of Economic Research, 53(4), 2001, 219-248, Proceedings of LOFT-4.
• [6] van Benthem, J.: The Epistemic Logic of IF Games (Hintikka Self-Applied), 2002, Under preparation. To appear in the Hintikka Volume, Library of Living Philosophers. Available at http://staff.science.uva.nl/~johan?H-H.pdf.
• [7] van Ditmarsch, H.: Knowledge Games, Ph.D. Thesis, University of Groningen, 2000.
• [8] Dunin-Keplicz, B., Verbrugge, R.: A Tuning Machine for Collective Commitments, Proceedings of Formal Approaches to Multi-Agent Systems (FAMAS 2003) (B. Dunin-Keplicz, R. Verbrugge, Eds.), 2003.
• [9] Emerson, E. A.: Temporal and Modal Logic, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Elsevier Science Publishers, 1990, 995-1072.
• [10] Emerson, E. A., Halpern, J. Y.: ”Sometimes” and ”Not Never” Revisited: On Branching versus Linear Time Temporal Logic, Journal of the ACM, 33(1), 1986, 151-178.
• [11] Fagin, R., Halpern, J. Y.,Moses, Y., Vardi, M. Y.: Reasoning about Knowledge, MIT Press: Cambridge, MA, 1995.
• [12] Goranko, V.: Coalition Games and Alternating Temporal Logics, Proc. of the 8th Conference on Theoretical Aspects of Rationality and Knowledge (TARK VIII) (J. van Benthem, Ed.), Morgan Kaufmann, 2001, Corrected version. Available at http://general.rau.ac.za/maths/goranko/papers/gltl31.pdf.
• [13] Goranko, V., van Drimmelen, G.: Complete Axiomatization and Decidability of the Alternating-time Temporal Logic, 2003, Submitted.
• [14] Goranko, V., Jamroga, W.: Comparing Semantics of Logics forMulti-agent Systems, Synthese, 2004, 139(2), pp. 241-280.
• [15] Hafer, T., Thomas, W.: Computation tree logic CTL* and Path Quantifiers in the Monadic Theory of the Binary Tree, in: Proceedings of 14th ICALP, Karlsruhe (F. Baader, G. Brewka, T. Eiter, Eds.), vol. 267 of Lecture Notes in Computer Science, Springer, 1987, 269-279.
• [16] Hintikka, J., Sandu, G.: Game-Theoretical Semantics, in: Handbook of Logic and Language (J. van Benthem, A. ter Meulen, Eds.), Elsevier: Amsterdam, 1997, 361-410.
• [17] van der Hoek, W., Wooldridge, M.: Tractable Multiagent Planning for Epistemic Goals, Proceedings of the First International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-02) (C. Castelfranchi,W. Johnson, Eds.), ACM Press, New York, 2002.
• [18] van der Hoek, W., Wooldridge, M.: Cooperation, Knowledge and Time: Alternating-time Temporal Epistemic Logic and its Applications, Studia Logica, 75(1), 2003, 125-157.
• [19] van der Hoek, W., Wooldridge, M.: Model Checking Cooperation, Knowledge and Time - A Case Study, Research in Economics, 57(3), 2003, 235-265.
• [20] van der Hoek, W., Wooldridge, M.: Towards a Logic of Rational Agency, Logic Journal of the IGPL, 11(2), 2003, 135-160.
• [21] Huth, M., Ryan, M.: Logic in Computer Science: Modeling and reasoning about systems, Cambridge University Press, 2000.
• [22] Jamroga, W.: Some Remarks on Alternating Temporal Epistemic Logic, Proceedings of Formal Approaches to Multi-Agent Systems (FAMAS 2003) (B. Dunin-Keplicz, R. Verbrugge, Eds.), 2003.
• [23] Jonker, G.: Feasible Strategies in Alternating-time Temporal Epistemic Logic, 2003, Master thesis.
• [24] Laroussinie, F.: About the expressive power of CTL combinators, Information Processing Letters, 54(6), 1995, 343-345.
• [25] Laroussinie, F., Schnoebelen, P.: A hierarchy of temporal logics with past, Theoretical Computer Science, 148(2), 1995, 303-324.
• [26] Moore, R.: A Formal Theory of Knowledge and Action, in: Formal Theories of the Commonsense World (J. Hobbs, R. Moore, Eds.), Ablex Publishing Corp., 1985.
• [27] Morgenstern, L.: Knowledge and the Frame Problem, International Journal of Expert Systems, 3(4), 1991.
• [28] von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behaviour, Princeton University Press: Princeton, NJ, 1944.
• [29] Quine, W.: Quantifiers and Propositional Attitudes, Journal of Philosophy, 53, 1956, 177-187.
• [30] Schnoebelen, P.: The Complexity of Temporal Model Checking, Advances in Modal Logics, Proceedings of AiML 2002,World Scientific, 2003.
• [31] Schobbens, P. Y.: Alternating-Time Logic with Imperfect Recall, Electronic Notes in Theoretical Computer Science, 85(2), 2004.
• [32] Wooldridge, M.: Reasoning about Rational Agents, MIT Press : Cambridge, Mass, 2000