A Framework for Graded Beliefs, Goals and Intentions

• Autorzy: Dunin-Kęplicz B. , Nguyen L.A. L.A. , Szałas A.
• Języki publikacji: EN

Abstrakty

EN

In natural language we often use graded concepts, reflecting different intensity degrees of certain features. Whenever such concepts appear in a given real-life context, they need to be appropriately expressed in its models. In this paper, we provide a framework which allows for extending the BGI model of agency by grading beliefs, goals and intentions. We concentrate on TEAMLOG [6, 7, 8, 9, 12] and provide a complexity-optimal decision method for its graded version TEAMLOGK by translating it into CPDL_reg (propositional dynamic logic with converse and "inclusion axioms" characterized by regular languages). We also develop a tableau calculus which leads to the first EXPTIME (optimal) tableau decision procedure for CPDL_reg. As CPDL_reg is suitable for expressing complex properties of graded operators, the procedure can also be used as a decision tool for other multiagent formalisms.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 100, nr 1/4
• Strony: 53--76
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Dunin-Kęplicz B.

autor

Nguyen L.A. L.A.

autor

Szałas A.

• Institute of Informatics, Warsaw University, Warsaw, Poland and Polish Academy of Sciences, Warsaw, Poland,

Bibliografia

• [1] Casali, A., Godo, L., Sierra, C.: A Language for the Execution of Graded BDI Agents, Workshop on Formal Approaches to Multi-Agent Systems (FAMAS) at the Multi-Agent Logics, Languages, and Organisations Federated Workshops (MALLOW), Durham, UK, 6 and 7 September 2007 (B. Dunin-Keplicz, R. Verbrugge, Eds.), 2007.
• [2] Casali, A., Godo, L., Sierra, C.: A Logical Framework to Represent and Reason about Graded Preferences and Intentions, 11th International Conference on Principles of Knowledge Representation and Reasoning, KR'2008 (G. Brewka, J. Lang, Eds.), The AAAI Press, The AAAI Press, Sydney, 2008.
• [3] De Giacomo, G., Massacci, F.: Combining deduction and model checking into tableaux and algorithms for Converse-PDL, Information and Computation, 162(1-2), 2000, 117-137.
• [4] Demri, S., de Nivelle, H.: Deciding Regular Grammar Logics with Converse Through First-Order Logic, Journal of Logic, Language and Inform., 14(3), 2005, 289-329.
• [5] van Ditmarsch, H.: Prolegomena to dynamic logic for belief revision, Synthese, 147, 2005, 229275.
• [6] Dunin-Kęplicz, B., Verbrugge, R.: Collective Intentions, Fundamenta Informaticae, 51(3), 2002, 271-295.
• [7] Dunin-Kęplicz, B., Verbrugge, R.: Evolution of Collective Commitments During Teamwork, Fundam. Inform., 56, 2003, 329-371.
• [8] Dunin-Kęplicz, B., Verbrugge, R.: A Tuning Machine for Cooperative Problem Solving, Fundam. Inform., 63, 2004, 283-307.
• [9] Dunin-Kęplicz, B., Verbrugge, R.: Awareness as a Vital Ingredient of Teamwork, Proc. of AAMAS'06 (P. Stone, G. Weiss, Eds.), 2006.
• [10] Dunin-Keplicz, B., Verbrugge, R.: Teamwork in Multi-Agent Systems. A Formal Approach, John Wiley & Sons, Ltd., 2010.
• [11] Dziubiński, M., Verbrugge, R., Dunin-Kęplicz, B.: Complexity issues in multiagent logics, Fundamenta Informaticae, 75(1-4), 2007, 239-262.
• [12] Dziubiński,M., Verbrugge, R., Dunin-Kęplicz, B.: Reducing the complexity of logics formultiagent systems, Proceedings of AAMAS '07, ACM, 2007.
• [13] Goble, L.: Grades of Modality, Logique et Analyse, 13, 1970, 323-334.
• [14] Goré, R., Nguyen, L.: EXPTIME Tableaux with Global Caching for Description Logics with Transitive Roles, Inverse Roles and Role Hierarchies, Proc. of TABLEAUX 2007, LNAI 4548 (N. Olivetti, Ed.), Springer-Verlag, 2007.
• [15] Goré, R., Nguyen, L.: Clausal Tableaux for Multimodal Logics of Belief, Fundam. Inform., 94(1), 2009, 21-40.
• [16] Grant, J., Kraus, S., Perlis, D.: Formal Approaches to Teamwork, in: We Will Show Them: Essays in Honour of Dov Gabbay (S. Artemov, others, Eds.), vol. 1, College Publications, London, 2005, 39-68.
• [17] Grosz, B., Kraus, S.: Collaborative Plans for Complex Group Action, Artificial Intelligence, 86(2), 1996, 269-357.
• [18] Harel, D., Kozen, D., Tiuryn, J.: Dynamic Logic, MIT Press, 2000.
• [19] van der Hoek, W.: On the Semantics of Graded Modalities, Journal of Applied Non-Classical Logics, 2(1), 1992.
• [20] de Jongh, D., Ghosh, S.: Comparing strengths of beliefs explicitly, Proc. MALLOW FAMAS'09 Workshop on Formal Approaches to Multi-Agents Systems (B. Dunin-Kęplicz, R. Verbrugge, Eds.), 2007.
• [21] Levesque, H., Cohen, P., Nunes, J.: On acting together, Proc. Eighth National Conference on AI (AAAI90), MIT Press, Cambridge (MA), 1990.
• [22] Mateescu, A., Salomaa, A.: Formal Languages: an Introduction and a Synopsis, in: Handbook of Formal Languages - Volume 1, Springer, 1997, 1-40.
• [23] Nguyen, L.: Multimodal Logic Programming, Theoretical Computer Science, 360, 2006, 247-288.
• [24] Nguyen, L., Szałas, A.: An Optimal Tableau Decision Procedure for Converse-PDL, Proceedings of KSE'2009 (N.-T. Nguyen, T.-D. Bui, E. Szczerbicki, N.-B. Nguyen, Eds.), IEEE Computer Society, 2009.
• [25] Nguyen, L., Szałas, A.: A Tableau Calculus for Regular Grammar Logics with Converse, Proceedings of CADE-22, LNAI 5663 (R. Schmidt, Ed.), Springer-Verlag, 2009.
• [26] Pratt, V.: A Near-Optimal Method for Reasoning about Action, J. Comp. Syst. Sci., 20(2), 1980, 231-254.
• [27] Pynadath, D. V., Tambe,M.: The CommunicativeMultiagent Team Decision Problem: Analyzing Teamwork Theories and Models, Journal of Artificial Intelligence Research, 16, 2002, 389-423.
• [28] Rao, A., Georgeff,M.: Modeling Rational Agents within a BDI-architecture, Proc. of the Second Conference on Knowledge Representation and Reasoning (R. Fikes, E. Sandewall, Eds.), Morgan Kaufman, 1991.
• [29] Wooldridge, M., Jennings, N.: Cooperative Problem Solving, Journal of Logic and Computation, 9, 1999, 563-592.