Multi-Agent Systems and Applications V

This paper presents and evaluates a multi-agent approach for range image segmentation. A set of reactive and autonomous agents perform a collective segmentation by partitioning a range image in its different planar regions. The agents move over the image and perform cooperative and competitive actions on the pixels, allowing a robust region extraction, and an accurate edge detection. An artificial potential field, created around the pixels of interest, ensures the agent coordination. It allows the agents to concentrate their actions around the edges and the noise regions. The experimental results show the potential of the proposed approach for scene understanding in range images, regarding both segmentation efficiency, and detection accuracy.

With the recent development of many model-checkers for the temporal logic of knowledge, abstraction techniques are necessary to increase the size of the systems that can be verified. In this paper, we introduce several abstraction techniques for interpreted systems and we prove several preservation results. These results consider the temporal logic of knowledge under Kleene’s 3-valued interpretation along infinite and maximal finite paths.

This paper presents an agent-based approach to Network Intrusion Prevention on corporate networks, emphasizing the protection from fast-spreading mobile malicious code outbreaks (e.g. worms) and related threats. Agents are not only used as a system-integration platform, but we use modern agent approaches to trust modeling and distributed task allocation to efficiently detect and also counter the attack by automatically created and deployed filters. The ability of the system to react autonomously, without direct human supervision, is crucial in countering the fast-spreading worms, that employ efficient scanning strategies to immediately spread farther once they infect a single host in the network.

In this paper we propose a dialogue game for agents to deliberate over a proposed action. The agents’ dialogue moves are defined by a structured set of argument schemes and critical questions (CQs). Thus, a dialogue move is an instantiated scheme (

i.e.

an argument) or a CQ (

i.e.

a challenge on the argument instantiated in the scheme). The proposed dialogue game formalises the protocol based exchange of arguments defined in the

ProCLAIM

model. This model provides a setting for agents to deliberate over whether, given the arguments for and against, a proposed action is justified or not.

In this paper we introduce a formal attacker model for normative multi-agent systems. In this context, an attacker is an agent trying to profit from norm violation, for example because the violation is not detected, it is not being sanctioned, or the sanction is less than the profit of violation. To deliberate about norm violations, an attacker has a self model and a model of the normative multi-agent system, which in our case have the same structure. Moreover, we assume that an attacker violates a norm only when it profits from it, and the attacker therefore plays a violation game with the system. On a variety of examples, we show also how our model of violation games based also on agent abilities or power extends our earlier model based on motivations only.

Two-party communication is the most-studied model to support interaction between two cognitive agents, whereas that is only one case of what an agent should be able to do. Multi-party communications enhance this model, by taking into account all the roles an agent can have in a communication. Nevertheless, there are no generic models and infrastructures that enable to apply multi-party communication in a standardized way. We emphasize that the environment, in the sense of a common medium for the agents, is a suitable paradigm to support multi-party communication. We propose a general and operational model called Environment as Active Support of Interaction (EASI), that enables each agent to actively modify the environment according to its communication needs. Algorithms are proposed and assessed with an example stemming from the ambient intelligence domain.

In this paper, we introduce a formal-language interaction protocol for agent communication that may contribute to the building of better human-computer dialogues through a simulation of human language use. The paper centers on formal dialogue research. We introduce the definition of a formal model of dialogue based on Eco-Grammar Systems (EGS) and inspired in the Multi-Agent Protocol (MAP) language. The result is a simple formal device that could be used for the design of dialogue systems with limited human-like behaviour.

We present a multi-agent system designed to detect malicious traffic in high-speed networks. In order to match the performance requirements related to the traffic volume, the network traffic data is acquired by hardware accelerated probes in NetFlow format and preprocessed before processing by the detection agent. The proposed detection algorithm is based on extension of trust modeling techniques with representation of uncertain identities, context representation and implicit assumption that significant traffic anomalies are a result of potentially malicious action. In order to model the traffic, each of the cooperating agents uses an existing anomaly detection method, that are then correlated using a reputation mechanism. The output of the detection layer is presented to operator by a dedicated analyst interface agent, which retrieves additional information to facilitate incident analysis. Our performance results illustrate the potential of the combination of high-speed hardware with cooperative detection algorithms and advanced analyst interface.

Agent Communication Languages (ACLs) play a fundamental role in open multiagent systems where message exchange is the main if not the only way for agents to coordinate themselves. New proposals about ACL semantics based on social commitments aim at countering the shortcomings of the mainstream mental-state-based ones. The commitment solution does not come for free and calls for an adequate monitoring system that checks whether commitments are fulfilled or not.

Sharing information about profiles and offered competencies of individual members within an alliance of cooperating companies facilitates searching for potential members of Virtual Organizations. This paper presents a concept of structuring of the competencies as well as a prototype proving this concept. The prototype follows a naturally hybrid architecture of alliances that consists of mutually independent alliance partners, who may be supported by central institutions of the alliance. The use of the agent-based solution enables information sharing among partners in such distributed and dynamic environment.

We consider the problem of verifying game equilibria in multi-agent systems. We first identify a certain class of games where Nash or Bayesian Nash equilibria can be verified in polynomial time. Second, we show that verifying a dominant strategy equilibrium is NP-complete even for normal form games. Eventually, we consider general games and discuss the complexity of equilibrium verification.

In this paper, we present a scheme for the design of mobile agents applications based on components. There is still a paramount issue to overcome in mobile agent technology to allow its popularization: the high programming complexity. The proposed scheme enables secure mobile agent creation by the composition of code components, significantly simplifying the work for the developer. Agent features like itinerary protection, results retrieving, or fault-tolerance can be achieved through reusable components. Our proposal is a steady step forward for the promotion of mobile agent applications.

Natural systems are regarded as rich sources of inspiration for engineering artificial systems, particularly when adopting the multiagent system (MAS) paradigm. To promote a systematic reuse of mechanisms featured in self-organising systems, we analyse a selection of design patterns devised from the self-organisation literature. Starting from our reference MAS metamodel, we propose a pattern scheme that reflects the peculiarities of self-organising systems. Then, we provide a complete characterisation of each pattern, with particular attention to the problem description, the solution with respect to our metamodel, the natural systems which have inspired the pattern and known applications.

In this paper, we present an approach for adaptive replication to support fault tolerance. This approach uses a feedback control theory methodology within an adaptive replication infrastructure to determine replication degrees of replica groups. We implemented this approach in a multi-agent system to survive Byzantine failures. At the end of the paper, we also provide some experimental results to show the effectiveness of our approach.

In small scale multi-agent environments, every agent is aware of all of the others. This allows agents to evaluate the potential outcomes of their interaction for each of their possible interaction partners. However, this farsighted knowledge becomes an issue in large scale systems, leading to a combinatorial explosion in evaluation and is unrealistic in communication terms. Limited awareness of other agents is therefore the only plausible scenario in many large-scale environments. This limited awareness can be modeled as a sparse social network in which agents only interact with a limited subset of agents known to them. In this paper, we explore a model of dynamic multi-agent coalition formation in which agents are connected via fixed underlying social networks that exhibit different well known structures such as

Small World

,

Random

and

Scale Free

topologies. Agents follow different exploratory policies and are distributed in the network according to a variety of metrics. The primary results of the paper are to demonstrate different positive and negative properties of each topology for the coalition formation problem. In particular we show that despite positive properties for many problems,

Small World

topologies introduce blocking factors which hinder the emergence of good coalition solutions in many configurations.

In this paper we focus on a new approach for the definition of context-based compatibility and substitutability of roles in MAS, and provide a formal framework for modeling roles together with their composition. First, we introduce the concept of usability of roles, and based on that we define two flexible roles compatibility relations depending on the context (environment). The proposed compatibility relations take into account the property preservation such as the completion and the proper termination of roles. Then, our formal framework is enhanced with the definition of two flexible behavioral subtyping relations related to the principle of substitutability. Finally, we show the existing link between compatibility and substitutability of roles, namely the preservation of the proposed compatibility relations by substitutability.

Multiagent systems may be elegantly modeled and designed by enhancing the role of the environment in which agents evolve. In particular, the environment may have the role of a governing infrastructure that regulates with laws or norms the actions taken by the agents. The focus of modeling and design is thus shifted from a subjective view of agents towards a more objective view of the whole multiagent system. In this paper, we apply the idea of a governing environment to model and design a multi-agent system that micro-simulates the Swiss highway network. The goal of the simulation is to show how traffic jams and accordion phenomena may be handled with appropriate local regulations on speed limits. A natural modeling would give segments the capacity to regulate the speed based on observed local events. We developed the simulation platform from scratch in order to accommodate our design choices and a realistic complexity. This paper presents in details our modeling choices, and first experimental results.

Multi-Agent Systems (MAS) in health-care domains are showing a rapid increase, in order to manage complex tasks and adapt gracefully to unexpected events. On the other hand, the lack of well-established agent-oriented engineering methodologies to transform knowledge level descriptions into deployable agent systems slackens MAS development. This paper presents a new methodology in modelling and automatically implementing agents in a home care domain. The representation of the application knowledge together with the codification of health care treatments lead to flexible realization of an agent platform that has the capability to capture new medical knowledge emerging from physicians.

In this paper we present a logic to provide a framework for the formal specification of multiagent real-time systems which allows explicit reasoning about the actions of agents, the nondeterministic model of interaction between agents and environment, the cooperation and competition of agents and the reaction time limits of a system. The logic combines Propositional Dynamic Logic

PDL

and Alternating-time Temporal Logic

ATL

and extends the formalism with reaction time constraints. We introduce a multiagent system abstract model and show how the logic can be used to specify the model properties.

At present the agent paradigm is often used for computational modeling of human behavior in an organizational setting. However, not many of the existing computational approaches make use of a rich theoretical basis developed in social science. Therefore, often mathematically sound models are invalid in practice. This paper proposes a formal approach for modeling of characteristics and behavior of agents in organizations, diverse aspects of which are represented using an expressive formal framework. The approach is based on the theoretical findings from social science and enables analysis of how different organizational and environmental factors influence the behavior and performance of agents. The approach is illustrated by a simulation case study.

In agent systems, meta-level reasoning is commonly used in enforcing rationality in the choice of goals and actions performed by an agent, ensuring that an agent behaves as effectively and efficiently as possible. Through meta-reasoning an agent is able to explicitly consider goals before committing to them, and consider courses of action before executing plans. In this paper, we argue that although seldom considered, a flexible meta-level reasoning component is a valuable addition to any agent architecture. We describe such a component for use in BDI architectures, underpinned by a model of motivation and a motivation-based description language, and demonstrate its effectiveness empirically.

Software-Engineering provides techniques to ease handling the essential complexity of software. A number of engineering paradigms and architectures have been devised and each generation claims to relieve future development efforts. But to date little is known about how different development approaches affect the underlying implemenation structures, making their contributions arguable. Recently, the statistical analysis of large–scale modular software systems – represented as directed graphs – revealed complex system characteristics, namely

scale–free

and

small–world

phenomena. In this paper, we argue that the exhibited network characteristics reflect utilized design approaches and apply graph analysis to examine the structural differences imposed by the utilization of Agent–Oriented Software Engineering. As this novel development paradigm proposes autonomous and pro–active entities as an atomic design and development metaphor for complicated and inherently distributed software systems, an initial analysis and comparison of graphs abstracting both agent– and object–oriented system designs reveals structural differences which suggest that agent autonomy influences the resulting underlying implementation structures.

We are interested in understanding and simulating how humans elaborate plans in situations where knowledge is incomplete and how they interact to obtain missing information. Our human interaction model is based on the speech act theory to model the utterances and it uses timed automata to describe the dynamics of the dialogs. Our human planning model is implemented as a hierarchical blackboard architecture which manages opportunistic planning. The system

BDIggy

we propose, is a concurrent implementation of the planning model and the interaction model through the BDI concept. This system is used to simulate the human processes during cooperative problem solving.

Organizational Theory concepts have been adapted to improve, extend and facilitate Agent Organizations modeling. Thus, three basic organizational topologies from which other more complex organizations can be composed have been identified. Moreover, this organizational modeling has been implemented in a specific MAS platform (SPADE) making use of Multiuser Conference technology. We have also defined several services for SPADE that ease the implementation of organization dynamics, such as member access and agent interaction control.

In this paper we present an experimental analysis of a fuzzy constraint based framework for automated purchase negotiations in competitive trading environments. The main goal of this work is to show by experimental analysis which combination of different agents’ negotiation attitudes allows buyer and seller agents to improve the multi-attribute bilateral negotiation processes. Agents’ attitudes are related to the agents’ strategic behaviour in the negotiation process, where strategic behaviours are described in terms of expressiveness and receptiveness.

We propose a new multi-agent development method, named MDAD (

Model Driven Agent Development

). It is based on the MDA (

Model Driven Architecture

) paradigm. The aim of MDAD method is to reduce the cost of building MAS applications by starting from abstract specification of system thanks to MAS meta-models, and producing the final system by means of transformations of this specification into computational entities. We present in this paper the application of MDAD to the INAF framework. First we give an overview of MDA approach and its application to MAS. Thus, several abstraction levels are determined and a set of meta-models is introduced. Then, we give the transformation rules used to produce INAF compliant models. MDAD method is illustrated with the timetable management benchmark.

In this paper, we propose a logic for reasoning about probabilistic belief, called

PBL

r

. Our language introduces formulas that express “agent

i

believes that the probability of

ϕ

is at least

p

”. We first provide an inference system of

PBL

r

, and then introduce a probabilistic semantics for

PBL

r

. The soundness and finite model property of

PBL

r

are proved, which ensure the weak completeness and decidability of

PBL

r

.

This paper focuses on modelling perception and vague concepts in the context of multiagent B

gi

(

Beliefs, Goals

and

Intentions

) systems. The starting point is the multimodal formalization of such systems. Then we make a shift from Kripke structures to similarity structures, allowing us to model perception and vagueness in an uniform way, “compatible” with the multimodal approach. As a result we introduce and discuss

approximate B

gi

systems

, which can also be viewed as a way to implement multimodal specifications of B

gi

systems in the context of perception.

Future agent mediated eCommerce will involve open systems of agents interoperating between different institutions, where different auction protocols may be in use. We argue that in order to achieve this agents will need a method to automatically verify the properties of a previously unseen auction protocol; for example, they may wish to verify that it is fair and robust to deception. We are therefore interested in the problem of automatically verifying the game-theoretic properties of a given auction mechanism, especially the property of strategyproofness. In this paper we show how the

Alloy

model checker can be used to automatically verify such properties. We illustrate the approach via two examples: a simple two player Vickrey auction and a quantity restricted multi-unit auction using the Vickrey-Clarke-Groves mechanism.

Distributed join calculus can be used to formally reason about concurrent systems. This paper introduces notion of an environment where agents interact. Based on the introduced formalisms a notion of knowledge which is exchanged by facts and common to all agents is presented. Introduction of the environment and knowledge extends number of agent system which can be expressed using join calculus algebra.

During several recent decades a lot of research projects have been done in the area of intelligent distance learning systems. Such systems became wide spread in different educational and industrial organizations due to rapid evolution of network engineering and Internet. The physical presence of teacher and students in one class is not required due to usage of such systems. Usually, such systems have distributed architecture. This was a major motivation to make a research to analyze possibility of multiagent technologies usage in intelligent distance learning systems. The paper presents the developed architecture of agent community for such systems and a research prototype allowing to model agents’ interaction for user interface control based on several pedagogical strategies.

The construction of web applications is a complex task as different kinds of technologies need to be integrated. To ease the task of developing web applications many different web frameworks have been conceived. These frameworks aim at providing support for recurring and tedious development tasks and address complexity by separating the basic concerns of applications. Most of the currently available web frameworks adhere to the widely accepted Model 2 design pattern that targets a clean separation of model, view and controller parts of an application in the sense of the model view controller (MVC) pattern. In this paper it is shown how the basic Model 2 archiecture can be adapted for enabling its usage in combination with business logic realized with agent technology. Besides the architecture itself additionally its realization within the Jadex Webbridge framework is sketched.

Multi-agent system research deals with organization theoretical concepts in order to analyse and control supra-individual phenomena. However, there exists a conceptual gap between organizational specifications and their multi-agent implementation. We address this problem by presenting an integrated approach for the specification and deployment of organizational models based on Petri nets.

In this paper we propose a modification to a fuzzy constraint based framework for automated purchase negotiations in competitive trading environments. The goal of this work is to improve the performance of the negotiation processes in terms of computation time and joint utility. This modification is based on the use of clustering techniques in the seller’s decision mechanisms.

Cooperation is the fundamental characteristic of multi-agent systems where the overall system exhibits significantly greater functionality than the individual components. In this paper, we propose a P2P cooperation framework for multiple Case-based Reasoning (CBR) agents to handle the student models initialization problem in Intelligent Tutoring Systems (ITSs). Our work shows that using the “committee” collaboration policy the agents can obtain better results that working alone, allowing to enhance the system overall performance.

The use of Multi-agent systems (MAS) in healthcare domain has been widely recognized. But, due to uncertainty in medical domain, it is difficult to decide the appropriate agent with whom to collaborate in order to find the proper diagnosis for a given set of sign-symptoms. To overcome this problem, a Bayesian network (BN) based decision making framework is presented. The proposed methodology is applied to an Intelligent Pediatric Agent (IPA), a part of MAS for child care [1].

This paper presents a proposal for a flexible agent mobility architecture based on IEEE-FIPA standards and intended to be one of them. This proposal is a first step towards interoperable mobility mechanisms, which are needed for future agent migration between different kinds of platforms. Our proposal is presented as a flexible and robust architecture that has been successfully implemented in the JADE and AgentScape platforms. It is based on an open set of protocols, allowing new protocols and future improvements to be supported. With this proposal we demonstrate that a standard architecture for agent mobility capable of supporting several agent platforms can be defined and implemented.

HeCaSe2

is a multi-agent system that intends to help doctors to apply clinical guidelines to their patients in a semi-automatic fashion.

HeCaSe2

agents need a lot of (scattered) information on health care organisations, as well as medical knowledge, in order to provide an efficient support to health care practitioners. Modelling all these data is certainly a hard task. The paper describes how the inclusion of an especially designed ontology allows different agents to coordinate their activities in the enactment of clinical guidelines.

Nowadays, there exist some toolkits that design and implement multi-agent systems. However, these toolkits have certain deficiencies when applied in specific environments (i.e. real-time environments). In these environment there may be strict temporal restrictions that require the use of specific agent architectures. Since these architectures are not covered in the development process of existing tools, this paper presents a new toolkit for the implementation of real-time multi-agent systems based on the jART platform.

In this work we describe the development process of multi-agent application design and implementation with M

ulan

. Our approach can be characterized as model driven development by using models in all stages and levels of abstraction regarding design, implementation and documentation. Both, standard methods from software development as well as customized ones are used to satisfy the needs of multi-agent system development.

Intelligent Tutoring Systems (ITSs) base their interoperability on the interchange of domain knowledge about learning and teaching processes and about students. To enable the interchange of domain knowledge between ITSs and heterogeneous Health Information Systems (HIS) we propose a multi-agent architecture allowing sharing patient’s clinical data in Health Information Systems. The Health Level (HL7) is used as a standard messaging protocol for collecting the clinical patient data distributed over Health Information Systems.

The issue of multi-agent planning in highly dynamic environments is a major impediment to conventional planning solutions. Plan repair and replanning solutions alike have difficulty adapting to frequently changing environment states. To adequately handle such situations, this paper instead focuses on preserving individual agent plans through multi-agent coordination techniques. We describe a reactive agent system architecture in which the main focus of an agent is to be able to achieve its subgoals without interfering with any other agent. The system is a 3-level architecture, where each level is guided by the following fundamental principles, respectively:

when

is it valid to generate a plan for a subgoal,

who

is most appropriate for completing the subgoal, and

how

should the plan be carried out.

Ontology matching plays a vital role in a number of areas, such as knowledge integration, services composition or system interoperability. In this paper we present an architectural overview of an ontological service, wrapped up as an Ontology Agent, supporting automated ontology matching and facilitating inter-agent communication.

To allow for flexibility in software structures (architectures) especially plugins and agents are proposed solutions. While plugins are used to support the conceptual and practical issues within component oriented software environments, agents are used in software areas where social metaphors like (self-)adaptability, flexibility, mobility, interactivity etc. are of interest. Common to both approaches is a strong relation to a service-oriented view on exporting functionality. This contribution illustrates the idea of the integration of both concepts on the formal basis of high-level Petri nets.

This work focuses on the problem of inventory management which is an important element of the supply-chain management challenge. The goal of our research was to develop an application which supports decision making regarding optimal strategies for producing electrical machines. The multi-agent approach offers several valuable features which may be exploited for supply-chains management: problem decentralization, isolation of different kinds of sub–problems and solving them separately, as well as modeling and predicting the behavior of the particular modules and referring to the means offered by distributed intelligence.

Resource allocation in distributed systems is an exciting area of research. Inherent properties in this environment, such as strategic users acting selfishly and the structure of the environment within which exchanges occur, are relevant challenges to study. This paper proposes a market–based resource allocation in a distributed environment and explores the effects of network structure on the allocation of performance together. Further, we proposed mechanisms to improve the performance of the market. The proposed model, as well as mechanisms to maximize the allocation of objects/goods have been implemented and studied experimentally. The results obtained show how topology affects the performance of the market. Using information propagation mechanisms clearly contributes to its improvement.