Fundamenta Informaticae - Volume 63, issue 2-3

Article Type: Other

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. i-iii, 2004

Authors: Shehory, Onn

Article Type: Research Article

Abstract: Coalition formation research in the last decade has produced an array of coalition formation mechanisms. Although these address a variety of environments and settings, they are usually inadequate for practical applications. The major limitations of the proposed mechanisms that render them inapplicable are a high computational complexity, and unrealistic assumptions regarding the availability of information. In this article we present two recent coalition formation mechanisms that attempt to overcome these limitations. One …of the mechanisms introduces a very low complexity, allowing scaling to thousands of agents, and the other mechanism does not assume complete information. Rather, it assumes private, subjective and inaccurate valuation of coalitions. These two mechanisms do not solve all of the problems present in the field, however they point at promising directions that might lead to fully applicable solutions in future research. Show more

Keywords: coalition formation

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 107-124, 2004

Authors: Weyns, Danny | Holvoet, Tom

Article Type: Research Article

Abstract: Contrary to cognitive approaches of agency where a lot of effort is devoted to the formalization of agent concepts, little work has been done on the formalization of situated multi-agent systems (situated MASs). In this paper we present a generic model for situated MASs. This model formally describes an abstract architecture for situated MASs. In this architecture each agent is situated in its local context that it is able to perceive and in which it can …act. Since intelligence in situated MASs results from the interactions of agents with the environment rather than from their individual capabilities, the model takes an action-centric approach. The model deals with (1) the actions of agents in the environment, (2) ongoing activities in the environment, such as moving objects, and (3) the interactions between agents and ongoing activities through the environment. One model for situated MASs was described by J.Ferber and J.P. M¨ller. In this model all agents of the MAS act at one global pace, i.e.the agents are globally synchronized. Drawbacks of global synchronization are centralized control and poor scalability. We present a model that allows agents to synchronize locally. In this model there is no centralized entity that imposes all agents to act at one global pace, but instead agents themselves decide when they perform their next actions. The model supports simultaneous actions through regional synchronization. With regional synchronization agents form synchronized groups on the basis of their actual locality. Different groups can act asynchronously, while agents within one group act synchronously. The result is a model that does not suffer from the drawbacks of global synchronization while it preserves the properties for handling simultaneous actions. In the paper we apply the model to a simple MAS application. We show how the abstract model can be instantiated for a practical application. Then we follow a trace in the evolution of the application and demonstrate how the model deals with each particular step. Show more

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 125-158, 2004

Authors: Aldewereld, Huib | van der Hoek, Wiebe | Meyer, John-Jules

Article Type: Research Article

Abstract: This paper describes a possible extension to the logical framework KARO to make it able to handle multiple agents. The KARO framework, which was initially developed by van der Hoek, van Linder and Meyer, makes use of epistemic and dynamic logics to express rational agents. These agents are capable of reasoning about their own actions and, somewhat limited, about the actions of other agents. This paper intends to extend the KARO system such that one is …also able to reason about cooperation between agents. Show more

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 159-183, 2004

Authors: Jamroga, Wojciech | van der Hoek, Wiebe

Article Type: Research Article

Abstract: 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. Show more

Keywords: multiagent systems, temporal logic, epistemic logic, knowledge, transition systems, games with incomplete information

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 185-219, 2004

Authors: Kacprzak, M. | Lomuscio, A. | Penczek, W.

Article Type: Research Article

Abstract: This paper addresses the problem of verification of temporal epistemic properties of multi-agent systems by means of symbolic model checking. An overview of the technique of bounded model checking for temporal epistemic logic, and an analysis of some limitations of the method are provided. An extension of this technique called unbounded model checking to solve these limitations is explored. Similarities and differences of the two methods are explicitly exemplified by the analysis of a scenario in …the two formalisms. Show more

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 221-240, 2004

Authors: Mazurkiewicz, Antoni

Article Type: Research Article

Abstract: In general, negotiations within a group of participants are processes, that starting with participants in some arbitrary (initial) states eventually will achieve an agreement with all participants being in the required negotiated states. Process of negotiation is performed according to a negotiation protocol. Here, an ordering of participants is taken as the negotiation goal; constructing a negotiation protocol for this purpose is referred to as the ranking problem. The formal method used for discussing the …considered issue are local computations; in general, they consist in transforming states of the whole structure by way of transforming states of its substructures. The paper aims to discuss communication structures that admit negotiations limited to direct communications between participants of a single 'association' at a time. Necessary and sufficient conditions for existence of such a ranking protocol for considered structures are formulated and a universal protocol for ranking is given. The paper is a generalization of bilateral negotiations presented in [14], where negotiations are limited to associations containing at most two members; the multilateral protocol presented in this paper covers the case of bilateral negotiations. Show more

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 241-258, 2004

Authors: de Haan, Hendrik Wietze | Hesselink, Wim H. | Renardel de Lavalette, Gerard R.

Article Type: Research Article

Abstract: A knowledge-based program is a high-level description of the behaviour of agents in terms of knowledge that an agent must have before (s)he may perform an action. The definition of the semantics of knowledge-based programs is problematic, since it involves a vicious circle; the knowledge of an agent is defined in terms of the possible behaviours of the program, while the possible behaviours are determined by the actions which depend on knowledge. We define the semantics …of knowledge-based programs via an iteration approach generalizing the well-known fixpoint construction. We propose a specific iteration as the semantics of a knowledge-based program, and justify our choice by a number of examples, including the Unexpected Hanging Paradox. Show more

Keywords: knowledge-based programming, semantics of programming languages, concurrent programming, asynchronicity, unexpected hanging paradox

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 259-281, 2004

Authors: Dunin-Keplicz, Barbara | Verbrugge, Rineke

Article Type: Research Article

Abstract: In this paper we aim to formally model individual, social and collective motivational attitudes in teams of agents involved in Cooperative Problem Solving. Particular attention is given to the strongest motivational attitude, collective commitment, which leads to team action. First, building on our previous work, a logical framework is sketched in which social commitments and collective intentions are formalized. Then, different versions of collective commitments are given, reflecting different aspects of Cooperative …Problem Solving, and applicable in different situations. The definitions differ with respect to the aspects of teamwork of which the agents involved are aware, and the kind of awareness present within a team. In this way a kind of tuning mechanism is provided for the system developer to tune a version of collective commitment fitting the circumstances. Finally, we focus attention on a few exemplar versions of collective commitment resulting from instantiating the general tuning scheme, and sketch for which kinds of organization and application domains they are appropriate. Show more

Citation: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 283-307, 2004