Wyniki wyszukiwania - BazTech

1

Complexity Issues in Multiagent Logics

Dziubiński M., Verbrugge R., Dunin-Kęplicz B.

Fundamenta Informaticae

|

2007

|

Vol. 75, nr 1-4

239-262

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.

2

A Multi-modal Logic for Disagreement and Exhaustiveness

Düntsch I., Konikowska B.

Fundamenta Informaticae

|

2007

|

Vol. 75, nr 1-4

215-238

EN

The paper explores two basic types of relations betwen objects of a Pawlak-style information system generated by the values of some attribute of those objects: disagreement (disjoint sets of values) and exhaustiveness (sets of values adding up to the whole universe of the attribute). Out of these two fundamental types of relations, most other types of relations on objects of an information system considered in the literature can be derived - as, for example, indiscernibility, similarity and complementarity. The algebraic properties of disagreement and indiscernibility relations are explored, and a representation theorem for each of these two types of relations is proved. The notions of disagreement and exhaustiveness relations for a single attribute are extended to relations generated by arbitrary sets of attributes, yielding two families of relations parametrized by sets of attributes. They are used as accessibility relations to define a multi-modal logic with modalities corresponding to the lower and upper approximation of a set in Pawlak's rough set theory. Finally, a complete Rasiowa-Sikorski deduction system for that logic is developed.

3

Evolution of Collective Commitment during Teamwork

Dunin-Kęplicz B., Verbrugge R.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 4

329-371

EN

In this paper we aim to describe dynamic aspects of social and collective attitudes in teams of agents involved in Cooperative Problem Solving (CPS). Particular attention is given to the strongest motivational attitude, collective commitment, and its evolution during team action. First, building on our previous work, a logical framework is sketched in which a number of relevant social and collective attitudes is formalized, leading to the plan-based definition of collective commitments. Moreover, a dynamic logic component is added to this framework in order to capture the effects of the complex actions that are involved in the consecutive stages of CPS, namely potential recognition, team formation, plan formation and team action. During team action, the collective commitment leads to the execution of agent-specific actions. A dynamic and unpredictable environment may, however, cause the failure of some of these actions, or present the agents with new opportunities. The abstract reconfiguration algorithm, presented in a previous paper, is designed to handle the re-planning needed in such situations in an efficient way. In this paper, the dynamic logic component of the logical framework addresses issues pertaining to adjustments in collective commitment during the reconfiguration process.