First International Conference on Multiagent Systems

Back to ICMAS page.

Tutorials

Invited Talks

Papers

Posters

Papers

Generalised Proof-theoretic Multi-agent Autoepistemic Reasoning

Yongyuth Aramkulchai and Y.J.Jiang

Abstract

---

A Multi-Agent Intelligent Design System Integrating Manufacturing and Shop-Floor Control

Sivaram Balasubramanian and Douglas H. Norrie

Abstract

---

Motor Schema-based Formation Control for Multiagent Robot Teams

Tucker Balch and Ronald C. Arkin

Abstract

---

COOL: A Language for Describing Coordination in Multiagent Systems

Mihai Barbuceanu and Mark S. Fox

Abstract

---

Formal Specification of Multi-Agent Systems: a Real-World Case

F. Brazier, B. Dunin-Keplicz, N. Jennings, J. Treur

Abstract

---

The DRESUN Testbed for Research in FA/C Distributed Situation Assessment: Extensions to the Model of External Evidence

N. Carver and V. Lesser

Abstract

---

Commitments: from individual intentions to groups and organizations

Cristiano Castelfranchi

Abstract

---

Communication for conflict resolution in multi-agent collaborative planning

Jennifer Chu-Carroll, Sandra Carberry

Abstract

---

Multiagent Reasoning with Belief Contexts II: Elaboration Tolerance

A. Cimatti, L. Serafini

Abstract

---

Communicative Actions for Artificial Agents

Philip R. Cohen and Hector J. Levesque

Abstract

---

Designing a Family of Coordination Algorithms

Keith Decker and Victor Lesser

Abstract

---

Knowledge-Based Distributed Search Using Teamwork

Joerg Denzinger

Abstract

---

A Tool For Coordinating Autonomous Agents With Conflicting Goals

Love Ekenberg, Magnus Boman, Mats Danielson

Abstract

---

A Tractable Heuristic That Maximizes Global Utility Through Local Plan Combination

Eithan Ephrati, Martha Pollack, and Jeffrey S. Rosenschein

Abstract

---

Coordination without Communication: Experimental Validation of Focal Point Techniques

M. Fenster, S. Kraus, J. S. Rosenchein

Abstract

---

A Model For Cooperative Transportation Scheduling

K. Fischer, J.P.Mueller, M. Pischel

Abstract

---

Dilemmas in computational societies

N.S. Glance and T. Hogg

Abstract

---

A Rigorous, Operational Formalization of Recursive Modeling

Piotr J. Gmytrasiewicz and Edmund H. Durfee

Abstract

---

Towards a Pragmatic Theory of Interactions

A. Haddadi

Abstract

---

A Game-Theoretic Account of Cooperation in Communication

Koiti Hasida, Katashi Nagao, and Takashi Miyata

Abstract

---

Multiagent collaboration in directed improvisation

B. Hayes-Roth and L. Brownston

Abstract

---

Forming Coalitions for Breaking Deadlocks

Katsutoshi Hirayama and Jun'ichi Toyoda

Abstract

---

Deciding when to commit to action during observation-based coordination

Marcus J. Huber and Edmund H. Durfee

Abstract

---

A Multiagent System for Controlling Building Environments

B. A. Huberman and S. H. Clearwater

Abstract

---

How Agents Do It In Stream Logic Programming

Matthew M Huntbach, Nick R Jennings and Graem A Ringwood

Abstract

---

Two is not Always Better than One: Experiences in Real-Time Bidirectional Search

Toru Ishida

Abstract

---

Reasoning about belief based on common knowledge of observability of actions

Hideki Isozaki

Abstract

---

The Emergence of Cooperation in a Society of Autonomous Agents

Akira Ito and Hiroyuki Yano

Abstract

---

Self Organizational Approach for Integration of Distributed Expert Systems

Tatsuaki Itoh, Takashi Watanabe, and Takahira Yamaguchi

Abstract

---

Synchronizing Multiagent Plans using Temporal Logic Specifications

Froduald Kabanza

Abstract

---

Hierarchical and Lateral Coordination in MAS : An analysis of Message Traffic Flow

Alois Knoll, J. Meinkoehn

Abstract

---

A Cooperation Language

Michael Kolb

Abstract

---

On using KQML for Matchmaking

Daniel Kuokka and Larry Harada

Abstract

---

Exploiting Problem Structure for Distributed Constaint Optimization

JyiShane Liu and Katia Sycara

Abstract

---

A Formal Framework for Agency and Autonomy

Michael Luck and Mark d'Inverno

Abstract

---

Understanding Cooperation: an Agent's Perspective

Andreas Lux, Donald Steiner

Abstract

---

Unsupervised Multi-Agent Exploration Of Structured Environments

Dario Maio, Stefano Rizzi

Abstract

---

Time and the prisoner's dilemma

Yishay Mor and Jeffrey S. Rosenschein

Abstract

---

A Simple Computational Market for Network Information Services

T. Mullen and M. P. Wellman

Abstract

---

Introducing Blind Hunger Dilemma

Chisato Numaoka

Abstract

---

A Metalevel Coordination Strategy for Reactive Cooperative Planning

Ei-Ichi Osawa

Abstract

---

BDI Agents: from theory to practice

Anand Rao and Michael Georgeff

Abstract

---

PARAgente: Exploring the Issues in Agent-Based User Interfaces

J. A. Sanchez, F.S. Azevedo, & J.J. Leggett

Abstract

---

Issues in Automated Negotiation and Electronic Commerce: Extending the Contract Net Framework

Tuomas Sandholm and Victor Lesser

Abstract

---

Unsupervised Surrogate Agents and Search Bias Change in Flexible Distributed Scheduling

Sandip Sen and Edmund H. Durfee

Abstract

---

DIDE: A Multi-Agent Environment for Engineering Design

Weiming Shen, Jean-Paul Barthes

Abstract

---

Exploiting Social Reasoning to Deal with Agency Level Inconsistency

J. Sichman and Y. Demazeau

Abstract

---

Reusing past plans in distributed planning

Toshiharu Sugawara

Abstract

---

Recursive Agent and Agent-Group Tracking in a Real-time Dynamic Environment

Milind Tambe

Abstract

---

Recursive Agent Modeling using Limited Rationality

Jose M. Vidal and Edmund H. Durfee

Abstract

---

Understanding the Emergence of Conventions in Multi-Agent Systems

A. Walker, M.Wooldridge

Abstract

---

Distributed Scheduling of Multiagent Communication

Y. Xiang

Abstract

---

Resource contention in multiagent systems

M. Youssefmir and B.A. Huberman

Abstract

---

---

Posters

Knowledge and Behavior in Multiagent Systems

Stanislaw Ambroszkiewicz

Abstract

---

A Framework for Multi-Agent Inter-Organizational Applications: A Position Paper

Matthew Anderton, Jim Cunningham, Jeremy Pitt

Abstract

---

Rational Balancing of Planning and Communication in the Dynamic Multi-Agents World

Sachiyo Arai

Abstract

---

A communication protocol for conflict resolution

Pierre Azema, Francois Vernadat, Jean Luc Albacete

Abstract

---

Linear Prediction in a Multi-Agent Environment

Joachim Baczewski and Mario Tokoro

Abstract

---

A Game-Theoretic Approach to Distributed Control of Traffic Signals

A. Bazan

Abstract

---

An Agent System for Case Adaptation

R. Bhat

Abstract

---

Linguistic Support for Agent Migration

R. Bordini, A. Rocha Costa, J. Hubner, R. Viccari

Abstract

---

Map Making as a Support for Cooperation

F. Chimura and M. Tokoro

Abstract

---

Modeling and Studying Social Belief

Gregg Courand and Michael Fehling

Abstract

---

Distributed Flow Shop Scheduling Problem: Global versus Local Optimization

T. Daouas, K. Ghedira, J-P. Muller

Abstract

---

The Consensus Scheduling Model: Negotiation among Peers

William B. Day

Abstract

---

Asynchronous Teams: Autonomous Agents Organizations for Solving Combinatorial Problems

Pedro Sergio de Souza, Sarosh Talukdar

Abstract

---

A multi-agent approach to the design of coordination mechanisms

Monica Divitini, Carla Simone, Kjeld Schmidt, Peter Carstensen

Abstract

---

Actions with Typical Effects: Epistemic Characterization of Scenarios

Barbara Dunin-Keplicz, Anna Radzikowska

Abstract

---

Autonomous Agent Control: A Case for Integrating Models and Behaviors

I. A. Ferguson

Abstract

---

Unifying Control In A Layered Agent Architecture

K. Fischer, J.P.Mueller, M. Pischel

Abstract

---

Deriving Goals and Intentions

Graca Gaspar, Helder Coelho

Abstract

---

Agents as Reasoners, Observers, or Arbitrary Believers

Giunchiglia, Giunchiglia, and Serafini

Abstract

---

A quantitative analysis of the Contract Net Protocol

Cheng Gu and Toru Ishida

Abstract

---

Evolving Cooperation Strategies

Thomas Haynes, Roger Wainwright & Sandip Sen

Abstract

---

Distributed Symbolic-Subsymbolic Agent Architecture for Configuring Power Network Faults

R. Khosla, T. Dillon

Abstract

---

An agent algebra for the formal description and verification of multi-agent systems

Alexander Kick

Abstract

---

Coalition-based cooperation between intelligent agents

Matthias Klusch

Abstract

---

Self-Organization based on Coordinated Actions of Autonomous Agents

Satoshi Kurihara and Michio Okada

Abstract

---

AgenTalk: Coordination Protocol Description for Multiagent Systems

Kazuhiro Kuwabara, Toru Ishida, Nobuyasu Osato

Abstract

---

Multiagent Coordination in Distributed Interactive Battlefield Simulations

John E. Laird, Randolph M. Jones, and Paul E. Nielsen

Abstract

---

A Microeconomic Approach to Intelligent Resource Sharing in Multiagent Systems

Jaeho Lee and Edmund H. Durfee

Abstract

---

A view on the architecture and design of highly autonomous and situated agents

Masthoff, J., & Van Hoe, R

Abstract

---

An Adaptable Architecture for Environmental Monitoring

Jutta Mueller, Thies Wittig

Abstract

---

Organic Programming for Multi-Agents

Hideyuki Nakashima, Itsuki Noda, and Ichiro Ohsawa

Abstract

---

Hierarchy and Network: A Mathematical Model of Performance for Structural Choice

Toshizumi Ohta, Tadashi Yamamoto, and Kazunari Ishida

Abstract

---

RAPIDO: A Rapid Prototyping Toolkit for Developing Multi-Agent Systems

Mike Reddy

Abstract

---

Some Principles in Designing Cooperative Architectures of Autonomous Agents

Lorenzo Sommaruga, Nadia Catenazzi

Abstract

---

Learning Coordination Plans in Distributed OS Environments

Toshiharu Sugawara, Victor Lesser

Abstract

---

An Agent Model in a Multiagent System Architecture for Automating Distributed Systems

Truszkowski, Odubiyi, and Ruberton

Abstract

---

Beyond Cooperation-ism and Competition-ism (Exploring Social Phenomena with a Generalized Tit-For-Tat Model)

Elpida S. Tzafestas

Abstract

---

VIENA: A Multiagent Interface to a Virtual Environment

Ipke Wachsmuth, Britta Lenzmann, Yong Cao

Abstract

---

Automated Multiagent preference aggragation using fuzzy quantifiers

Ronald R. Yager

Abstract

---

Asynchronous Weak-commitment Search for Solving Large-Scale Distributed Constraint Satisfaction Problems

Makoto Yokoo

Abstract

---

The Consensus of Uncertainties in Distributed Expert Systems

Minjie Zhang and Chengqi Zhang

Abstract

---

---

Exploiting Social Reasoning to Deal with Agency Level Inconsistency

J. Sichman and Y. Demazeau

Back to titles

---

In a previous work (sichman94b), we presented the fundamental concepts of a social reasoning mechanism, which enables an agent to reason about the others using information about their goals, actions, resources and plans. In this paper we first place ourselves as an external observer to analyse the possible coupled outcomes of the social reasoning mechanisms of two different agents. We show that in some particular cases, different inferred dependence situations imply that the agents' mutual representations are inconsistent at an agency level. Then, we detail our analysis in a particular case where the agents have the same plans (and believe in that), showing that some particular coupled outcomes can be explained either by incorrectness or incompleteness of mutual representation. In order to do that, we extend our previous model by introducing the notion of goal situation. Finally, we conclude by showing that these properties may be detected by the agents themselves if we supply them with an internal mechanism where they can manipulate the outcomes inferred both by their own social reasoning mechanism and by those of the others. Keywords: reasoning about the others, dependence relations, incoherence of mutual representation, multi-agent belief revision Topics: social structures and their significance in multi-agent systems, conceptual and theoretical foundations of multi-agent systems.

---

Generalised Proof-theoretic Multi-agent Autoepistemic Reasoning

Yongyuth Aramkulchai and Y.J.Jiang

Back to titles

---

Over the past few years, several different approaches have been proposed to deal with Multi-Agent Autoepistemic reasoning. Most of them have some anomalous results while the rest do not have clear and constructive proof theory. For example, Parikh [91] only allows an agent to reason nonmonotonically about other agents' knowledge but not about other agents' nonmonotonic reasoning. Morgenstern [90] provides a limited way to deal with the problem but unfortunately it is not constructive. Although Halpern [94] develops an algorithmetic definition of multiagent nonmonotonic reasoning, his approach cannot deal with default reasoning even for single-agent case. It also does not allow nested nonmonotonic reasoning of an agent about other agents' nonmonotonic reasoning. More important perhaps, these approaches seem to have unintuitive results for multi-agent case and we shall show that by considering some examples from Speech Acts. Our purpose is to find out a simple yet generalised constructive proof-theoretic framework for Multi-Agent Autoepistemic reasoning which retains the advantages of existing approaches but does not have those peculiar results. Surprisingly, the new proof-theoretic framework can be obtained by a simple modification to Parikh's approach. Furthermore, the results show that our framework is not only generalise Morgenstern's and the others approaches but also Niemela's Constructive Tightly Grounded Autoepistemic Logic.

---

How Agents Do It In Stream Logic Programming

Matthew M Huntbach, Nick R Jennings and Graem A Ringwood

Back to titles

---

The key factor that will determine the speed and depth to which multi-agent systems penetrate the commercial marketplace is the ease with which applications can be developed. One approach is to use general purpose languages to construct layers of agent level constructs. Object-oriented languages have been advocated as suitable for tackling the complexity of distributed systems. According to Gasser and Briot [1992], the key problem with the common forms of object based concurrent programming is the fixed boundaries they give to agents are too inflexible. They do not reflect either the theoretical positions emerging in DAI or the reality of multilevel aggregations of actions and knowledge. This paper advocates the use of a rather different type of object based concurrent language, stream logic programming (SLP) that does not have this drawback. Classification: Agent programming languages; integrated testbeds and development environments.

---

Commitments: from individual intentions to groups and organizations

Cristiano Castelfranchi

Back to titles

---

The aim of this work is to introduce some notions of Commitment as a descriptive ontology crucial for the understanding of groups' and organizations' functioning, and of the relations between individual agents and collective activity. Some of the basic ingredients of such notions are identified and some steps are made towards their definition. In particular, it is claimed that a notion of Commitment is needed as a mediation between the individual and the collective one. Before constructing a notion of "Collective or Group Commitment" a notion of "Social Commitment" is to be defined. "Social commitment" is not an individual Commitment shared by many agents; it is the Commitment of one agent to another. The normative contents (entitlements / obligations) of this social relation are stressed and its connections with individual intentions and collective activity. On that basis, a notion of Organizational Commitment is proposed, that could account for the structure of stable Organizations. Commitment is a crucial notion both to analyse the structure of Organizations and to support cooperative work, but a deeper analysis is needed, connecting agent's mental states with social relations and structure. Topic areas: Conceptual and theoretical foundations of MAS; Agent architectures (Commitment)

---

Time and the prisoner's dilemma

Yishay Mor and Jeffrey S. Rosenschein

Back to titles

---

This paper examines the integration of computational complexity into game theoretic models. The example focused on is the Prisoner's Dilemma, repeated for a finite length of time. We show that a minimal bound on the players' computational ability is sufficient to enable cooperative behavior. In addition, a variant of the repeated Prisoner's Dilemma game is suggested, in which players have the choice of opting out. This modification enriches the game and suggests dominance of cooperative strategies. Competitive analysis is suggested as a tool for investigating sub-optimal (but computationally tractable) strategies and game theoretic models in general. Using competitive analysis, it is shown that for bounded players, a sub-optimal strategy might be the optimal choice, given resource limitations. Keywords : Conceptual and theoretical foundations of multiagent systems; Prisoner's Dilemma

---

Knowledge-Based Distributed Search Using Teamwork

Joerg Denzinger

Back to titles

---

We present a knowledge-based distribution concept for search problems that offer no natural way to determine several agents to cooperate in finding a solution. Systems based on our teamwork method use four types of agents: Experts and specialists use heuristics to generate results that are possible parts of solutions, referees judge the experts and their results determining the most promising ones and a supervisor collects these promising results to generate new problem descriptions that converge to a solution of the initial problem. The main difficulty of distributed systems, the communication overhead, is dealt with by restricting the work of referees and the supervisor to short moments, called team meetings, that interrupt the work of experts and specialists. The competition and cooperation of experts and specialists in this framework allow for synergetic effects that generate better and faster solutions to the search problems. We demonstrate these effects for instantiations of two very different kinds of search problems, automated theorem proving and optimization problems. Main area of paper: Distributed search

---

Hierarchical and Lateral Coordination in MAS : An analysis of Message Traffic Flow

Alois Knoll, J. Meinkoehn

Back to titles

---

The general goal of using multi agent networks for complex problem solving is the maximisation of the quality of the result to be obtained at minimum cost. Both the general granularity of the agent society and the competence assigned to each individual agent determine the information flow in the network. The great number of parameters involved make it difficult for the designer to optimally adapt the structure of the network to a given class of tasks. In this paper we outline possible network structures and present an approach for determining a number of important statistical parameters characterising the network at a relatively abstract level. The abstraction enables a comparison of different network structures. The methods for the analysis may, however, be readily refined to evaluate a specific problem. As an example we discuss the use of the multi-agent paradigm for structuring the cooperation of sensor networks in robotics. Our analysis is supple-mented by simulation results, which prove a superiority of lateral over pure hierarchical coordination, particularly under severe environmental conditions, such as agent failure.

---

Multiagent Reasoning with Belief Contexts II: Elaboration Tolerance

A. Cimatti, L. Serafini

Back to titles

---

As discussed in previous papers, belief contexts are a powerful and appropriate formalism for the representation and implementation of propositional attitudes in a multiagent environment. In this paper we show that a formalization using belief contexts is also elaboration tolerant. That is, it is able to cope with minor changes to input problems without major revisions. Elaboration tolerance is a vital property for building situated agents: it allows for adapting and re-using a previous problem representation in different (but related) situations, rather than building a new representation from scratch. We substantiate our claims by discussing a number of variations to a paradigmatic case study, the Three Wise Men problem. Keywords: - Theoretical Foundations for Multiagent Systems - Reasoning about Propositional Attitudes

---

DIDE: A Multi-Agent Environment for Engineering Design

Weiming Shen, Jean-Paul Barthes

Back to titles

---

Real-world concurrent engineering design projects require the cooperation of multidisciplinary design teams using sophisticated and powerful engineering tools. The individuals or the individual groups of the multidisciplinary design teams work parallelly and independently with the different engineering tools which are located in the different sites for often a long time. In order to ensure the coordination of the design activities of the different groups or the cooperation among the different engineering tools, it is necessary to develop an efficient distributed intelligent design environment. This paper proposes a distributed architecture for integrating such engineering tools in an open design environment organized as a population of asynchronous cognitive agents. Before introducing the general architecture and the communication protocol, issues about the agent architecture and the inter-agent communication are discussed. A prototype of such an environment with seven independent agents located in the different workstations and microcomputers is presented. A small mechanical design example is used for testing such an environment.

---

A Tool For Coordinating Autonomous Agents With Conflicting Goals

Love Ekenberg, Magnus Boman, Mats Danielson

Back to titles

---

We present an implementation of a suggested solution to one of the most fundamental problems of multi-agent systems; that of conflicting information distributed over cooperating agents. To this end, we use a theory for the treatment of problems arising as a decision making agent faces a situation involving a choice between a finite set of strategies, having access to a finite set of autonomous agents reporting their opinions. The decision making agent is allowed to assign different credibility to statements of the autonomous agents. The theory admits the representation of vague and numerically imprecise information, and the evaluation results in a set of admissible strategies, by using criteria conforming to classical statistical theory. The admissible strategies can be further investigated with respect to their strengths and also with respect to the range of values consistent with the given domain that makes them admissible. Topic area: Cooperation, Coordination, and Conflict

---

Towards a Pragmatic Theory of Interactions

A. Haddadi

Back to titles

---

This article provides a specification of the reasoning processes that guide communicative actions of agents towards a potential cooperation. For this purpose we develop a formal theory with an internal perspective, which enables us to identify the key data structures and specify the relationships between them. The reasoning processes are described in terms of beliefs, desires and intentions of individual agents. The logical model of these attitudes are used to formally define a number of important states including agent to agent commitment. The reasoning processes are in essence the transitions through these states, specified by a set of rules as part of our specification language. As a result of these processes, an agent may adopt goals to communicate. These goals are fed back into the reasoning process to find appropriate communication plans that fulfill them. Our approach is therefore pragmatic since it enables a direct coupling of our theoretical concepts to an implementable model. Topics: Conceptual and theoretical foundations of multiagent systems, Cooperation and Communication issues.

---

A Formal Framework for Agency and Autonomy

Michael Luck and Mark d'Inverno

Back to titles

---

With the recent rapid growth of interest in Multi-Agent Systems, both in Artificial Intelligence and Software Engineering, has come an associated difficulty concerning basic terms and concepts. In particular, the terms agency and autonomy are used with increasing frequency to denote different notions with different connotations. In this paper we lay the foundations for a principled theory of agency and autonomy, and specify the relationship between them. Using the Z specification language, we decribe a three-tiered hierarchy comprising objects, agents and autonomous agents where agents are viewed as objects with goals, and autonomous agents are agents with motivations. Topic Areas: Conceptual and theoretical foundations of multiagent systems

---

Unsupervised Multi-Agent Exploration Of Structured Environments

Dario Maio, Stefano Rizzi

Back to titles

---

Exploration is a central issue for autonomous agents which must carry out navigation tasks in environments whose description is not known a priori. In our approach the environment is described, from a symbolic point of view, by means of a graph; clustering techniques allow for further levels of abstraction to be defined, leading to a multi-layered representation. In this work we propose an unsupervised exploration algorithm in which several agents cooperate to acquire knowledge of the environment at the different abstraction levels; a broadcast model is adopted for inter-agent communication. All agents are structurally equal and pursue the same local exploration strategy; nevertheless, the existence of multiple levels of abstraction in the environment representation allows for the agents' behaviours to differentiate. Agents carry out exploration at different abstraction levels, aimed at reproducing an ideal exploration profile; each agent selects dynamically its exploration level, based on the current demand.

---

Understanding the Emergence of Conventions in Multi-Agent Systems

A. Walker, M.Wooldridge

Back to titles

---

In this paper, we investigate techniques via which a group of autonomous agents can reach a global agreement on the use of social conventions by using only locally available information. Such conventions play a central role in naturally-occurring social systems, and there are good reasons for supposing that they will play a similarly important role in artificial social systems. Following a short review of conventions and their use in distributed artificial intelligence, we present a formal model that rigorously defines both our experimental methodology, and the performance measures we use to quantify the success of our experiments. We then describe sixteen different mechanisms for bringing about agreement on conventions, and present experimental results obtained for each of these methods. A tentative analysis of these results is given, and the paper concludes with some comments and issues for future work. Topic areas: organization self-design, cooperation.

---

Formal Specification of Multi-Agent Systems: a Real-World Case

F. Brazier, B. Dunin-Keplicz, N. Jennings, J. Treur

Back to titles

---

In this paper the framework DESIRE, originally designed for formal specification of complex reasoning systems is used to specify a real world multi-agent application on a conceptual level. Some extensions to DESIRE are introduced to obtain a useful formal specification framework for multi-agent systems. Topic areas : Integrated testbeds and development environments, development and engineering methodologies

---

Understanding Cooperation: an Agent's Perspective

Andreas Lux, Donald Steiner

Back to titles

---

The Multi-agent Environment for Constructing Cooperative Applications (MECCA) is based upon a framework unifying the internal behaviour of agents and cooperation among agents. This paper presents a formalised view of agent behaviour relying on the basic loop of goal activation, plan execution and scheduling followed by task execution. This allows for a presentation of the semantics of cooperation primitives: interagent messages supporting cooperation, comprised of speech acts operating upon objects occuring in the basic loop. The formal semantics of cooperation primitives gives a meaning to indiviudal messages, independent from the cooperation protocol. Thus, agents can reason about exchanged messages and are able to dynamically create their own methods for cooperation. Topic Areas: Agent architectures , Cooperation, coordination, and conflict

---

A Cooperation Language

Michael Kolb

Back to titles

---

This paper introduces CooL, a programming language for building cooperative applications. It combines the expressiveness of a high-level AOP-language with the efficiency required by industrial applications. It integrates the support for planning and scheduling with efficient execution on the single agent as well as multi-agent levels (cooperation). CooL's knowledge representation and execu- tion facilities are introduced, yielding the mechanisms that allow for easy programming of cooperations on the basis of cooperation primitives with a formal semantics. Topic Areas: Integrated Testbeds and Development Environments, Cooperation, Coordination and Conflict, Multi-Agent Languages

---

A Model For Cooperative Transportation Scheduling

K. Fischer, J.P.Mueller, M. Pischel

Back to titles

---

The MARS system is described which models cooperative scheduling within a society of shipping companies as a multiagent system. Emphasis is placed on the functionality of the system as a whole --- the solution of the global scheduling problem emerges from local decision-making and problem-solving strategies. An extension of the contract net protocol is presented; we show that it can be used to obtain good initial solutions for complex resource allocation problems. By introducing global information based upon auction protocols, this initial solution can be improved significantly. Experimental results are provided evaluating the performance of different cooperative scheduling strategies. Although the concepts for resource scheduling are presented solely for the transportation domain, their abstraction is useful for a broad variety of resource allocation problems. The MARS system solves the dynamic scheduling problem where no complete specification of the problem is available a priori; thus, it is designed as an on-line system based upon anytime algorithms.

---

A Tractable Heuristic That Maximizes Global Utility Through Local Plan Combination

Eithan Ephrati, Martha Pollack, and Jeffrey S. Rosenschein

Back to titles

---

We consider techniques suitable for combining individual agent plans into a global system plan, maintaining a commitment to considerations of global utility that may differ radically from individual agent utilities. We present a three-stage heuristic reduction process, consisting of a transformation from local to global utility measures, a global assessment of the local evaluations of agents, and approximation algorithms to maximize resource usage over time. We also consider how these techniques can be used with self-motivated agents, and show how the overall process can be distributed among a group of agents. Keywords: Distributed Problem Solving, Planning, Search

---

A Multiagent System for Controlling Building Environments

B. A. Huberman and S. H. Clearwater

Back to titles

---

A working solution to the problem of thermal resource distribution in a building is demonstrated using a market-based system. In this system computational agents representing individual temperature controllers bid to buy or sell cool or warm air. They do so via a double-blind computerized auction which is moderated by a central computer auctioneer. The auctioneer sees to it that no agent buys resources for more than its bid and no agent sells resources for less than its bid. The market system has been implemented and runs on a regular basis as part of a building energy management system. Results show that the thermal auction leads to an equitable temperature distribution throughout the area under its control without incurring any extra costs such as excessive actuator movement.

---

Linear Prediction in a Multi-Agent Environment

Joachim Baczewski and Mario Tokoro

Back to titles

---

In Multi-Agent systems, prediction of future states of observed events in an open and distributed environment gains importance with the growing complexity of the events agents have to deal with. We develop a model for applying Linear Prediction to a Multi-Agent environment. We design a prediction mechanism which senses its environment just by observing plain sampled data. No complex model of the environment has to be built in order to do good predictions of future events. Thus, our agents can react in a real time manner by simply analyzing the observed events. After introducing the theoretical background of Linear Prediction, we show that Linear Prediction can give good results even for multiple step predictions over a wide range of dynamics. Further, we show that, if agents apply our model competitively in a heterogeneous society of multiple agents, the stability and the performance of the whole system improves.

---

Distributed Scheduling of Multiagent Communication

Y. Xiang

Back to titles

---

We consider a homogeneous cooperative multiagent system organized as a multiply sectioned Bayesian network (MSBN). Earlier work has shown that (1) multiagent MSBNs can be applied to distributed interpretation tasks; and (2) a distributed communication operation can be used to ensure the global consistency among agents. In this paper, we address the following problem: During a communication operation, each agent is unavailable to process new evidence for a time interval (called off-line time). We consider the minimization of total length of off-line time of the entire system. To concentrate on the factors affecting the off-line time, we abstract communication in MSBNs into a graphical model for off-line time study. Using the model, we present the optimal schedules when communication is initiated from an arbitrarily selected agent. We show now the optimal schedules can be constructed in a distributed fashion.

---

Multiagent collaboration in directed improvisation

B. Hayes-Roth and L. Brownston

Back to titles

---

Topic Areas: Conceptual foundations of multiagent systems Agent architecture Directed improvisation is a new paradigm for multiagent interaction. One or more human users direct one or more computer characters with scripted or interactive directions. The characters work together to improvise a course of behavior that follows the directions, expresses their distinctive individual styles, honors social conventions, and meets other objectives. The resulting "performance" reflects the collaboration among all of the human and computer agents. Directed improvisation has several attractive properties as a paradigm for multiagent human-computer interaction, which we illustrate in our testbed application, a "computer-animated improvisational theater" for children. Directed improvisation also presents distinctive agent requirements that make it a useful addition to the domain of multiagent paradigms: demand for situated, spontaneous, opportunistic behavior; demand for very intimate agent interaction and shared control; and emphasis on process-oriented evaluation criteria.

---

Exploiting Problem Structure for Distributed Constaint Optimization

JyiShane Liu and Katia Sycara

Back to titles

---

Distributed constraint optimization imposes considerable complexity in agents' coordinated search for an optimal solution. However, in many application domains, problems often exhibit special structures that can be exploited to facilitate more efficient problem solving. One of the most recurrent structures involves disparity among subproblems. We present a coordination mechanism, Anchor&Ascend, for distributed constraint optimization that takes advantage of disparity among subproblems to efficiently guide distributed local search for global optimality. The coordination mechanism assigns different overlapping subproblems to agents who must interact and iteratively converge on a solution. In particular, an anchor agent who conducts local best first search to optimize its subsolution interacts with the rest of the agents who perform distributed constraint satisfaction to enforce problem constraints and constraints imposed by the anchor agent. We focus our study on the well-known NP-complete job shop scheduling problem. We define and study two problem structure measures, disparity ratio and disparity composition ratio. We experimentally evaluated the effectiveness of the Anchor&Ascend mechanism on a suite of job shop scheduling problems over a wide range of values of disparity composition. Our experimental results show that (1) considerable advantage can be obtained by explicitly exploiting disparity (2) disparity composition ratio plays a more important role than disparity ratio in finding high quality solution with little computational cost.

---

Dilemmas in computational societies

N.S. Glance and T. Hogg

Back to titles

---

World-wide interlinked computer networks are forming the foundation for computational societies of software agents. Already, these new societies have encountered problems endemic to human communities, such as overusing common resources with thrashing over virtual memory and competition by packets for network time. Unlike with human societies, these inefficiencies can be overcome by re-working the algorithms governing the protocols. However, the public good problem, in which a common good is available to all regardless of contribution, can arise computationally in more subtle ways. We discuss how this can happen using Braess' Paradox and demonstrate that adding resources to a computational system can counterintuitively lower the overall performance. This is thus a case in which distributed algorithms are provably unable to achieve globally optimal performance. We illustrate our claim using a genetic algorithm and computational ecosystem.

---

PARAgente: Exploring the Issues in Agent-Based User Interfaces

J. A. Sanchez, F.S. Azevedo, & J.J. Leggett

Back to titles

---

Alternative styles for human-computer interaction and human-human computer-mediated communication are needed to assist users in dealing with the ever-growing and complex information spaces at their disposal. PARAgente is a comprehensive research initiative aimed at investigating the issues, requirements and potential of interfaces which are based on user agents. This paper discusses major issues that must be addressed if agents are to become accepted by users in their interaction with computer systems. A testbed designed to explore these issues in the context of an open hypermedia system is also presented. Keywords: User agents, agent-based user interfaces, hypermedia systems, PARAgente, HyperActive, AcTool. Topic Areas: User Interface Issues for Multi-agent Systems Integrated Testbeds and Development Environments

---

COOL: A Language for Describing Coordination in Multiagent Systems

Mihai Barbuceanu and Mark S. Fox

Back to titles

---

Agent interaction takes place at several levels. CUrrent work in the ARPA Knowledge Sharing Effort has addressed the information contentlevel by the KIF language and the intentional level by the KQML langauge. In this paper we address the coordination level by means of our coordination language (COOL) that relies on speech act based communication, but integrates it in a stuctured conversation framework that captures the coordination mechanisms agents use when working together. We are currently using this language (i) to represent coordination mechanisms for the supply chain of manufacturing modeled as intelligent agents, and (ii) as an environment fo rdesigning and validating coordination protocols for multi-agent systems. This paper describes the basic elements of this language: conversation objects, conversation rules, error recovery rules, continuation rules, conversation nesting. The actual COOL source code and a running trace for the n-queens problem are presented in the Appendix. Topic areas: Coordination, intelligent agents in enterprise integration

---

Communication for conflict resolution in multi-agent collaborative planning

Jennifer Chu-Carroll, Sandra Carberry

Back to titles

---

Conflict management, communication, and negotiation are important components of collaborative multi-agent activity. Thus, a collaborative agent must be able to handle situations in which conflicts arise and negotiate with other agents to reach an agreement. This paper presents a model which 1) captures multi-agent collaboration in a "Propose-Evaluate-Modify" cycle of actions, 2) initiates negotiation with the executing agent to resolve detected conflicts regarding proposed actions and proposed beliefs, 3) selects the focus of the modification process when multiple conflicts arise, and 4) handles the negotiation of proposed domain actions, proposed problem-solving actions, and proposed beliefs in a unified manner.

---

On using KQML for Matchmaking

Daniel Kuokka and Larry Harada

Back to titles

---

As agents see more use as entry points to increasingly complex distributed information networks, agent communication technologies such as the Knowledge Query and Manipulation Language and the SHADE Matchmaker will play an important role. We describe our experiences with these technologies as applied to two applications: collaborative engineering and satellite image retrieval. Based on these experiences, we outline the major observed benefits of KQML and matchmaking. In addition, we discuss several problematic issues and potential solutions, including representational challenges in advertising complex databases, the need for persistent requests in information brokering, the dilemma between explicit vs. implicit brokering, problems in error recovery and response timing, consistency among information providers, and efficiency. Topics: Communication issues Intelligent agents in enterprise integration systems

---

A Multi-Agent Intelligent Design System Integrating Manufacturing and Shop-Floor Control

Sivaram Balasubramanian and Douglas H. Norrie

Back to titles

---

A multi-agent architecture has been developed for the integration of design, manufacturing, and shop floor control activities. This is based on cooperating intelligent entities in the sub-domains which make decisions through negotiation, using domain- specific knowledge both distributed among the entities and accessible to them. Using this architectural framework, an Agent Based Concurrent Design Environment system has been developed for feature-based design, manufacturability evaluation, and dynamic process planning. This is a multi-agent prototype system involving the following types of agent: design agent; geometric interface agent; feature agent; part agent; machine agent; tool agent; environment manager; and shop floor manager. A new technique for evaluating manufacturability is introduced, based on interacting intelligent features of the part being designed. This proof-of-concept system was developed for three-dimensional prismatic parts, with twenty-five different feature types, but can be extended to other geometries. The system has been completed and tested, and is being integrated into a larger multi-agent environment incorporating routing, scheduling, and overall production control. Topic Area: Practical Applications of Multi-Agent Systems (Manufacturing)

---

Coordination without Communication: Experimental Validation of Focal Point Techniques

M. Fenster, S. Kraus, J. S. Rosenchein

Back to titles

---

Coordination is a central theme of Distributed Artificial Intelligence. Much work in this field can be seen as a search for mechanisms that allow agents with differing knowledge and goals to coordinate their actions for mutual benefit. Additionally, one cornerstone assumption of the field is that communication is expensive relative to local computation. Thus, coordination techniques that minimize communication are of particular importance. This paper considers how automated agents could use a coordination technique common to communication-free human interactions, namely {\em focal points}. Given a problem and a set of possible solutions from which the agents need to choose one, focal points are prominent solutions of the problem to which agents are drawn. Theoretical work on this subject includes~\cite{schelling63,kraus91a}. The purpose of the current research is to consider the practical use of focal point techniques in various domains. We present simulations over randomly generated domains; these simulations strongly suggest that focal points can act as an effective heuristic for coordination in real-world environments. KEYWORDS: Coordination, Distributed AI

---

Deciding when to commit to action during observation-based coordination

Marcus J. Huber and Edmund H. Durfee

Back to titles

---

We have developed a multiagent scheme which utilizes plan recognition as its primary means of acquiring the information necessary to coordinate the activities of agents. Preliminary research has demonstrated that the plan recognition system developed makes coordination of multiple agents possible. An important issue that arises when observation is the primary means of information acquisition is the introduction of uncertainty into the coordination process. We have explored the issue of early versus late commitment to the uncertain information thus gained and the resulting tradeoff between time and effort as the commitment level is changed. Our results show that while in some situations it is worthwhile delaying commitment until uncertainty is reduced, in other situations it is important to act even when uncertainty is high. The long--term goal of the research is to develop the notion of coordination through observation, where agents utilize plan recognition to acquire coordination information.

---

A Simple Computational Market for Network Information Services

T. Mullen and P. Wellman

Back to titles

---

Topic Areas: Resource allocation, Engineering methodologies Visionary projections of a wide-area network teeming with intelligent agents describe an environment where end-users and their agents can pick and choose among a great variety of potentially valuable information services. However, neither network capabilities nor users' time and money are infinite. Computational markets provide one type of mechanism for allocating limited resources in such an environment in a distributed, dynamic way. Moreover, the underlying economic theory provides an analytical framework for predicting aggregate behavior and designing individual agents. In this paper, we describe a prototypical computational market model for information services distributed over a network. Our initial focus is on the economic problem of when and where to establish mirror sites for the more popular information services. Competitive agents choose to set up mirrors based on going prices for network bandwidth, computational resources, and the information service. Depending on the experimental setup, we observed a range of qualitative behaviors.

---

Recursive Agent Modeling using Limited Rationality

Jose M. Vidal and Edmund H. Durfee

Back to titles

---

We present an algorithm that an agent can use for determining which of its nested, recursive models of other agents are important to consider when choosing an action. Pruning away less important models allows an agent to take its "best" action in a timely manner, given its knowledge, computational abilities, and time constraints. We describe a theoretical framewwork, based on situations, for talking about recursive agent models and the strategies and expected strategies associated with them. This framework allows us to rigorously define the gain of continuing deliberation versus taking action. The expected gain of computational actionss is used to guide the pruning of the nested model structure. We have implemented our approach on a canonical multi-agent problem, the pursuit task, to illustrate how real-time, mulit-agent decision-making can be based on a principled, combinatorial model. Test results show a marked decrease in deliberation time while maintaining a good performance level. Topics: Algorithms for multi-agent interaction in time-constrained systems, Conceptual and theoretical foundations of multi-agent systems.

---

Unsupervised Surrogate Agents and Search Bias Change in Flexible Distributed Scheduling

Sandip Sen and Edmund H. Durfee

Back to titles

---

Computational infrastructures for cooperative work should contain embedded agents for handling many routine tasks, but as the number of agents increases and the agents become geographically and/or conceptually dispersed, supervision of the agents will become increasingly problematic. We argue that agents should be provided with deep domain knowledge that allos them to make justifiable decisions, rather than shallow models of users to mimic. In this paper, we use the application domain of distributed meeting scheduling to investigate how agents embodying deeper domain knowledge can choose among alternative strategies for searching their calendars in order to create flexible schedules within reasonable cost. Keywords: Distributed search, intelligent negotiating agents

---

Issues in Automated Negotiation and Electronic Commerce: Extending the Contract Net Framework

Tuomas Sandholm and Victor Lesser

Back to titles

---

In this paper we discuss a number of previously unaddressed issues that arise in automated negotiation among self-interested agents whose rationality is bounded by computational complexity. These issues are presented in the context of iterative task allocation negotiations. First, the reasons why such agents need to be able to choose the stage and level of commitment dynamically are identified. A protocol that allows such choices through conditional commitment breaking penalties is presented. Next, the implications of bounded rationality are analyzed. Several tradeoffs between allocated computation and negotiation benefits and risk are enumerated, and the necessity of explicit local deliberation control is substantiated. Techniques for linking negotiation items and multiagent contracts are presented as methods for escaping local optima in the task allocation process. Implementing both methods among self-interested bounded rational agents is discussed. Finally, the problem of message congestion among self-interested agents is described, and alternative remedies are presented. CFP Topics: Negotiation strategies - in both competitive and cooperative situations; Resource allocation in multiagent systems.

---

The DRESUN Testbed for Research in FA/C Distributed Situation Assessment: Extensions to the Model of External Evidence

N. Carver and V. Lesser

Back to titles

---

Keywords: Testbed, FA/C Distributed Problem Solving, distributed situation assessment, modeling agent beliefs. This paper reports on extensions that have been made to the DRESUN testbed for research on distributed situation assessment (DSA). These extensions involve issues that have arisen in modeling the beliefs of other agents when dealing with inter-agent communication of incomplete and conflicting evidence, and evidence at multiple levels of abstraction. The extensions support highly directed exchanges of results among agents because they better represent the uncertainties that occur when DRESUN agents exchange incomplete and conflicting information. This is important in FA/C systems because agents must share results in order to satisfy their local goals as well as the overall system goals. Unless this sharing can be done efficiently, a distributed approach may be inappropriate.

---

Resource contention in multiagent systems

M. Youssefmir and B.A. Huberman

Back to titles

---

The dynamics of resource contention in multiagent systems with imperfect information can be extremely complex. It was shown by Hogg and Huberman that when agents can follow different strategies in a system with resource contention, it is possible to render otherwise unstable and chaotic behavior into equilibrium. In a number of computer experiments we explore this mechanism and find the existence of bursty behavior which sporadically punctuates the existing equilibrium. This phenomenon is shown to arise out of the underlying fluctuations of the multiagent system. This mechanism of equilibria punctuated by bursts of erratic activity appears to be quite general in systems where agents explore strategies in search of local improvements.

---

Synchronizing Multiagent Plans using Temporal Logic Specifications

Froduald Kabanza

Back to titles

---

Plan synchronization is a method of analyzing multiagent plans, in order to introduce ordering constraints between them so that their concurrent execution achieve a desired goal. We describe a plan synchronization method for goals expressed using temporal logic specifications. Our goals can involve both qualitative and quantitative time requirements. The key to our method is a technique for checking goal formulas, incrementally, over models of concurrent executions of plans. Our approach covers more general problems than comparable methods and promises an easy integration with standard AI planning search control and heuristic strategies. Content areas: multiagent planning, coordination

---

Communicative Actions for Artificial Agents

Philip R. Cohen and Hector J. Levesque

Back to titles

---

This paper considers the semantics of the agent communication language KQML. By using this language for communication, agents will be able to request and deliver services to one another. Indeed, numerous projects have shown how the language can profitably support interoperation among distributed agents. However, before becoming a widely-accepted standard, it would be worthwhile to examine the language in detail. This paper explores semantical issues raised by KQML, specifically the use of performatives for interagent communication. Numerous difficulties with the language are identified, and an attempt is made to point to their resolution. The paper illustrates the kind of semantics we believe to be necessary to characterize agent communication languages, and applies it to compose a question from a request and an inform. Finally, the paper discusses possible impacts to be felt on various KQML decisions from the semantical issues raised here. Keywords: Agent Communication Languages, KQML, speech acts

---

Forming Coalitions for Breaking Deadlocks

Katsutoshi Hirayama and Jun'ichi Toyoda

Back to titles

---

When multiple agents solve their own problems while they interact with each other, it is helpful to form a coalition, which is a group of agents working together. Previous approach to coalition formation suggests to define the utility of coalitions and to use a strategy that agents form coalitions for getting higher utility. However, in some problems, the utility of coalitions is not easily obtainable because it might depend on uncertainty of other agents' problem solving. We describe a model of coalition formation where agents form coalitions for breaking deadlocks. In this model, agents solve distributed constraint satisfaction problem with an iterative repair method and form coalitions when they get stuck at local minima. This model is suggested to realize new approach to coalition formation. We also present experimental results on problem solving strategies in coalitions: the selfish and the altruistic.

---

The Emergence of Cooperation in a Society of Autonomous Agents

Akira Ito and Hiroyuki Yano

Back to titles

---

The emergence of cooperation in a society of autonomous agents is investigated. Each agent is made to repetitively engage in a deal equivalent to the ``Prisoner's Dilemma'' game, each time changing the other party of the deal. The conditions of the deal are that the contract histories of all the agents are disclosed to the public. Several deal strategies are evaluated, and their behaviors are investigated by matching them under various conditions. Next the social evolution of deal strategies is investigated using genetic algorithm techniques. Each agent can bear a child according to the profit he gets through the deal. The child inherits the deal strategy of the parent, but the random mutation is introduced to the inheritance of strategies. It is shown that the robust and cooperative strategies emerges through the evolution starting from a simple ``Tit for Tat'' algorithms.

---

Reusing past plans in distributed planning

Toshiharu Sugawara

Back to titles

---

This paper describes plan reuse in multiagent domains. In distributed planning, a plan is created by distributed centers of planner agents that have their own viewpoints. Plan reuse where a past plan result is reused for the new problem was proposed for single-agent planning and can achieve efficient planning. A special issue for applying it to distributed planning is that, even if the local agent thinks that the new problem is identical to a past problem, other agents may have quite different goals. Another issue is to realize efficient distributed planning, like in a single-agent case. This paper shows that the past plan can be reused regardless of other agents' goals under the assumption that the initial state has only ``in-facts.'' A generated plan and related information are stored as a plan template so that an agent can reuse it in future planning. This information includes generated plans, subgoals, non-local effects that may affect or be affected by other agents' plans, and their conflict resolution methods that were actually used. An agent can create a plan efficiently using a template, because it can skip a part of planning actions, detect conflicts in an early stage, and reduce communication costs. First, this paper presents the planning-with-reuse framework. Then how plan templates are created and reused is also illustrated using some block world examples. Finally, we experimentally show that efficient distributed planning can be achieved.

---

Two is not Always Better than One: Experiences in Real-Time Bidirectional Search

Toru Ishida

Back to titles

---

This paper investigates real-time bidirectional search (RTBS) algorithms, where two problem solving agents, starting from the initial and goal states, physically move toward each other. To evaluate the RTBS performance, two kinds of algorithms are proposed and are compared to real-time unidirectional search (RTUS). One is called centralized RTBS where a supervisor always selects the best action from all possible moves of the two problem solvers. The other is called decoupled RTBS where no supervisor exists and the two problem solvers independently select their next moves. Experiments on mazes and n-puzzles show that (1) in clear situations decoupled RTBS performs better, while in uncertain situations, centralized RTBS becomes more efficient, and that (2) RTBS is more efficient than RTUS for 15- and 24-puzzles but not for randomly generated mazes. It will be shown that the selection of the multi-agent organization is the selection of the problem space, which determines the baseline of the organizational efficiency; once a hard problem space is selected, the local coordination among problem solvers cannot overcome the deficit.

---

Reasoning about belief based on common knowledge of observability of actions

Hideki Isozaki

Back to titles

---

Sometimes we notice other people's mental states without direct communication and the guess influences our behavior. One's mental state depends on one's belief. However, reasoning about belief is very difficult because various factors affect belief and they often lead to inconsistency. This paper presents a simple algorithm to calculate multiagent nested belief >from an action sequence. The following three factors are essential in this algorithm: 1) the observability conditions of fluents and actions, 2) the direct\slash indirect effects of each action, and 3) the incompatibility of fluents. The algorithm performs backward reasoning from a query, and is implemented in Prolog. It has been tested by dozens of examples through a graphic interface. Experiments show the system gives plausible answers to various queries. This method will be useful in the construction of plan recognition systems and other advanced systems.

---

Self Organizational Approach for Integration of Distributed Expert Systems

Tatsuaki Itoh, Takashi Watanabe, and Takahira Yamaguchi

Back to titles

---

In development of ES, It is important to acquire knowledge from multiple human experts. Cooperative Distributed ES (CDES) is a framework which can unify multiple expertise to develop a large scaled ES. In CDES, ESs which are under building through acquiring knowledge from human experts as agents and task structure is learned by cooperation among agents based on extented Contract Net. At first, fundamental structure of CDES is provided. An experiment is made to evaluate the algorithm of Bid analyzer on the testbed of CDES. Then, self-reorganizational schemes are provided by changing agent's scope of domain knowledge, that is granularity, by themselves from two viewpoints of decomposing into fine grain and composing into coarse grain. Two experiments are made to learn subtask structure to change weight of cooperation among agents dynamically. Finally, we discuss the scheme which incorporate decomposition and composition of agents.

---

BDI Agents: from theory to practice

Anand Rao and Michael Georgeff

Back to titles

---

The study of agents situated in dynamic environments capable of rational behaviour has received a great deal of attention in recent years. Theoretical formalizations of such agents and their implementations have proceeded in parallel with little or no connection between them. This paper explores a particular type of rational agent, a Belief-Desire-Intention (BDI) agent. The primary aim of this paper is to integrate (a) the theoretical foundations of BDI agents from both a quantitative decision-theoretic perspective and a symbolic reasoning perspective; (b) the implementations of BDI agents >from an ideal theoretical perspective and a more practical perspective; and (c) the building of large-scale applications based on BDI agents. In particular, an air-traffic management application will be analyzed from both a theoretical and an implementation perspective.

---

Introducing Blind Hunger Dilemma

Chisato Numaoka

Back to titles

---

This paper introduce Blind Hunger Dilemma as a cardinal problem in multi-agent domain. This is a problem to investigate an effect of agents' characteristics on the mean performance of a total system when agents involve in exclusively used shared resources. In this paper, we model an agent as one sensitive to some sorts of forces originated >from an energy supply base and some adjacent agents. We characterize agents' nature with two parameters and investigate relationship between these two parameters and some performance measures such as energy supply times.

---

A Metalevel Coordination Strategy for Reactive Cooperative Planning

Ei-Ichi Osawa

Back to titles

---

In this paper, we propose a metalevel coordination strategy to implement an adaptive organization for reactive cooperative planning. The adaptive organization changes its organizational scheme adaptively as a means of coping with the dynamic problem spaces. Preliminary experiments shows that an adaptive organization can be made to the increase efficiency in dynamic problem spaces. The reason for this works is that reducing the degree of freedom in the problem space, while increasing the degree of interaction, demands greater coordination. However, if the number of effective local plans decrease, it would seem likely that if the agents were to have a better metalevel strategy, they would be better able to search this reduced space efficiently. The metalevel coordination incorporates an agent-wide metalevel heuristic function. In designing the metalevel coordination strategy, we take three aspects of reactive cooperative planning into account. These aspects include: the difference in the degree of achievement in successive turns; the certainty of shared information; and the degree of freedom of choice for agent's behavior. The adaptive organization works efficiently in cases where the communication cost is relatively expensive.

---

A Game-Theoretic Account of Cooperation in Communication

Koiti Hasida, Katashi Nagao, and Takashi Miyata

Back to titles

---

Communication inherently tends to be cooperative. Not only the sender of a message intends to communicate, but also the receiver is normally motivated to know the semantic content of the message intended by the sender, even if the receiver doubts the sender's honesty. The present paper accounts for how autonomous agents as selfish utility maximizers naturally cooperate in reaching a common optimal mapping between messages and their contents, raising the robustness of communication. An occasion of communication between two agents can be generally formalized as a non-cooperative n-person game (usually n>2), and the optimal mapping is shown to be obtained as a Nash equilibrium which maximizes the agents' expected utility over all the possible occasions of communication. Some regularities in natural language pragmatics are demonstrated to follow from this account.

---

Motor Schema-based Formation Control for Multiagent Robot Teams

Tucker Balch and Ronald C. Arkin

Back to titles New reactive behaviors that implement formations in multi-robot teams are presented and evaluated. Thes motor schemas, or primitive behaviors, for relative positional maintenance are integrated with existing navigational behaviors to help robots complete navigational tasks while in formation. Four formations, based on existing military doctrine \cite{army86}, and three methods for determining correct vehicle position are investigated. The performance of a group of four simulated robots using this technique is evaluated quantitatively for both turning and for navigation across an obstacle field. These team behaviors will ultimately be fielded on four military vehicles as part of ARPA's UGV Demo II program.

---

---

A Rigorous, Operational Formalization of Recursive Modeling

Piotr J. Gmytrasiewicz and Edmund H. Durfee

Back to titles

---

We present a formalization of the Recursive Modeling Method, which we have previously, somewhat informally, proposed as a method that autonomous artificial agents can use for intelligent coordination and communication with other agents. Our formalism is closely related to models proposed in the area of game theory, but contains new elements that lead to a different solution concept. The advantage of our solution method is that always yields the optimal solution, which is the rational action of the agent in a multi-agent environment, given the agent's state of knowledge and its preferences, and that it works in realistic cases when agents have only a finite amount of information about the agents they interact with. Our framework can be used to investigate the rational communicative behavior. We define the concept of a pragmatic meaning of a speech act, and show how to use it to evaluate the expected utility of performing such a speech act. The expected utility can be used to choose the optimal communicative behavior. Topic Areas: Theoretical foundations, Coordination and communication

---

Designing a Family of Coordination Algorithms

Keith Decker and Victor Lesser

Back to titles

---

Many researchers have shown that there is no single best organization or coordination mechanism for all environments. This paper discusses the design and implementation of an extendable family of coordination mechanisms, called Generalized Partial Global Planning (GPGP). The set of coordination mechanisms described here assists in scheduling activities for teams of cooperative computational agents. The GPGP approach has several unique features. First, it is not tied to a single domain. Each mechanism is defined as a response to certain features in the current task environment. We show that different combinations of mechanisms are appropriate for different task environments. Secondly, the approach works in conjunction with an agent's existing local planner/scheduler. Finally, the initial set of five mechanisms presented here generalizes and extends the Partial Global Planning (PGP) algorithm. In comparison to PGP, GPGP allows more agent heterogeneity, it exchanges less global information, and it communicates at multiple levels of abstraction.

---

Recursive Agent and Agent-Group Tracking in a Real-time Dynamic Environment

Milind Tambe

Back to titles

---

Agent tracking is an important capability that an intelligent automated agent requires for interacting with other agents. It involves monitoring the observable actions of other agents as well as inferring their unobserved actions or high-level plans, goals and behaviors. This paper analyzes the challenges of agent tracking in a "real-world", dynamic, multi-agent environment of air-combat simulation. An intelligent automated pilot in this environment faces the challenge of tracking the highly flexible actions and behaviors of other individuals or groups of pilots, while interacting with them, and dealing with imperfect sensors and real-time pressures. The paper introduces an approach for recursive agent tracking that enables an automated pilot to meet this challenge, and even take advantage of the imperfect sensors to engage in deception. The paper introduces some optimizations to address real-time pressures and presents experimental data >from an actual implementation to illustrate their impact. Agents in other competitive or collaborative dynamic multi-agent environments, such as "virtual reality" environments, could conceivably benefit from this agent tracking approach.

---

Coalition-based cooperation between intelligent agents

Matthias Klusch

Back to titles

---

A novel approach towards the recognition of interdatabase dependencies (IDD) using a federative agent system FCSI is presented. The architecture of the FCSI is designed as a system of cooperative intelligent autonomous agents each of them uniquely assigned to one local database system. The {\em FCSI aims for a cooperative solution for the problem of finding semantically related information while strictly respecting the autonomy requirements of each individual database system.} For this purpose first a {\em descriptive, terminological meta-knowledge and domain information representation {\sf DIT} on top of the local conceptual database schema} is built at each agent by using user-specified {\em intentional scripts}. In addition, a respectively instantiated actual aspect world {\sf W} enables a more flexible representation of {\em schema object aspects}. According to a prior known set of common terminological primitives {\sf cpc} of respective local {\sf DIT}s remote {\em terminological classification} then serves as a basis for the {\em discovery of intentional IDD}s ({\sf i-IDD}) between objects of different schemas with respect to some or all of their sofar related intentional interpretation aspects. Projections on respective associated {\em aspect valuations at schema and state level} {\sf isp}s determine {\em context-based data sharing} and result in restricted proposals for {\em interdatabase schema assertions} ({\sf IDSA}).\\ In order to organize a {\em cooperative recognition process} of {\sf i-IDD}s between the autonomous FCSI agents a method for decentralized {\em utilitaristic coalition formation} is presented. Moreover, each rational FCSI agent can participate in several different coalitions based on different types of coalition utilities. In this paper the current status of ongoing research on the FCSI is reported. Keywords : Interdatabase dependencies, Terminological reasoning, Coalition formation ICMAS-95 topics: Multiagent cooperative reasoning from distributed heterogeneous databases

---

An agent algebra for the formal description and verification of multi-agent systems

Alexander Kick

Back to titles

---

Multi-agent systems (MAS) are usually complicated and therefore error-prone. Especially the fact that there is a lot of interaction between agents can cause serious errors. In this paper we present an agent algebra which allows the formal description of MAS but also the verification of properties (safety and progress properties) of MAS. This can help the designer to become clear about the design and the correctness of the implementation. Our agent algebra can thus aid in making MAS suitable for control of safety critical systems such as flight control. Our agent algebra, whose terms, structured operational semantics and laws are described in this paper, focuses on interaction of agents. Thus, our agent algebra is especially suited for the description of cooperation and conflict (which is a major concern in MAS) among agents.

---

Knowledge and Behavior in Multiagent Systems

Stanislaw Ambroszkiewicz

Back to titles

---

Agent's goal is represented as utility maximization. We consider two kinds of knowledge--based protocols: Bayesian and MaxMin behavior. We argue that the ground knowledge type (on which the k--b protocol is based) should be a small part of the whole knowledge. So that we present a transformation of mutual knowledge onto the ground knowledge. The ground knowledge, mutual knowledge and the transformations constitute together knowledge system. We present a simple representation of common knowledge of these systems that gives fast transformation of this knowledge onto actions. This gives rise to a re--interpretation of Agent Oriented Programming paradigm. We postulate that k--b protocol (commitment statements in AOP terms) should be rational (i.e. maximizing the utility) and fixed, whereas the subject of change should be agent's utility and knowledge. If a programmer wants a MAS to reach a goal, he should give to agents such utilities and knowledge that the joint agents' activities maximizing their utilities will lead to a desired state of MAS. Topics area: Agent architectures, Conceptual and theoretical foundations of multiagent systems.

---

VIENA: A Multiagent Interface to a Virtual Environment

Ipke Wachsmuth, Britta Lenzmann, Yong Cao

Back to titles

---

This paper describes an application of a multiagent system for interaction with a virtual environment carried out in the VIENA project. The VIENA project has the following goals: enable an intelligent communication with a virtual environment, develop a multiagent system as a mediator in human-computer interaction, and explore its usefulness for interactive design and exploration. Instead of using the mouse and menus to manipulate scene details in a virtual environment we communicate with the system by way of natural language. Our aim is to keep the user (designer) free from technical considerations such as planning of geometric details, etc. Taking special responsibilities in mediating verbal instructions, the VIENA agents cooperate with each other and with the user to offer a goal scene meeting the user's wants. We explain the VIENA multiagent system, give an example application in virtual design, and discuss general advantages of multiagent systems in human-computer interaction. Topic areas: application of multiagent techniques in virtual design; intelligent user interfaces.

---

Asynchronous Teams: Autonomous Agents Organizations for Solving Combinatorial Problems

Pedro Sergio de Souza, Sarosh Talukdar

Back to titles

---

This article presents a new type of organization, called Asynchronous Teams, that enable several different agents to cooperate in order to solve a combinatorial problem, in particular, large instances of the Traveling Salesman Problem to the optimal solution. Asynchronous Teams are characterized by having autonomous agents that communicate asynchronously through shared memories in cyclic data flows. Results show that cooperation and consensus among agents are obtained without any coordination, and that Asynchronous Teams are scalle efficient regarding the number of agents: the more distinct agents in the team, the better its performance. Topic Areas: 1- cooperation, coordination and conflicts 2- organizations

---

A Framework for Multi-Agent Inter-Organizational Applications: A Position Paper

Matthew Anderton, Jim Cunningham, Jeremy Pitt

Back to titles

---

The CEC Project GOAL (Esprit 6283) aims to develop generic software tools to support a new project management paradigm, in which projects are collaborative, decentralised and inter-organizational. Our research and development activities have focussed on using multi-agent systems to address the inter-organizational aspects of interaction and communication between partners in such projects. The multi-agent framework we have been investigating and developing, called the Cooperation Services Framework (CSF), is designed to support distributed computer-supported cooperative work in inter-organizational project management. This position paper reviews our developments to date, describes our programme for realising a prototype demonstrator, and discusses some of the issues to be addressed in future investigation and experimentation. In particular, extending the CSF to include `agent brokering' between `rational agents' would enable other applications for inter-organizational interactions to be developed, such as trading systems and on-line information services. TOPIC AREAS: Practical Applications of Multi-Agent Systems, Intelligent Agents in Enterprise Integration Systems

---

Beyond Cooperation-ism and Competition-ism (Exploring Social Phenomena with a Generalized Tit-For-Tat Model)

Elpida S. Tzafestas

Back to titles

---

The modeling of cooperative processes has up to now relied almost exclusively on traditional cognitive approaches, employing explicit representations of goals, beliefs and actions, as seen from an observer's viewpoint, thus underemphasizing the role of internal agent architectures. We propose here a generalized tit-for-tat agent model that is completely reactive and possesses the properties of adaptivity and scalability. We show how this (socio)biological model can be used to account for social behavior, i.e. behavior depending explicitly on the interaction of an agent with other agents in its environment. This is achieved through the defi- nition of "social" objects or properties, which can be abstract or have a material form, and that are perceivable, accessible and manipulable by the agents. Agents have internal, built-in, or else genetic, motivations to regulate these objects/properties to certain limits and act accordingly. The result of those actions are then visible and directly perceivable by all the agents of the community who seek individually to satisfy their internal needs according to this social feedback. To deploy the potential of the approach, we present three examples from different domains and de- monstrate on several instantiations of the same basic model a variety of social phenomena that derive from the differential expression of those matching motivations of individual agents. The power of the approach may be partly attributed to the presence of genetic variations in the agents' parameters which give rise to intricate dynamics. Finally, we give a sketch of the level of complexity that the system may attain and we briefly expose its relation with predictive systems. Topics: Cooperation, sociality.

---

A communication protocol for conflict resolution

Pierre Azema, Francois Vernadat, Jean Luc Albacete

Back to titles

---

This paper deals with communication requirements for cooperating agents. A technical approach is proposed for specifying and analyzing cooperation and conflict resolution protocols among distributed agents. The plan of a single agent, the communication strategy between partners and the actual moves of entities are represented whithin a single framework. The proposed technique relies on modeling agent behaviours and coordinating algorithms by labeled Predicate/Transition Petri nets. Communication primitives are introduced for negotiating shared ressources among distinct partners. In particular, the localization of agents is taken into account for allowing either rendez-vous and simultaneous data exchange, or asynchronous exchanges via message passing. A formal description of distributed agreement protocols allows the verification of general properties such as deadlock avoidance and guarantee of progress. The introduced model leads to consider conflict and cooperation as two dual operations which have to be embedded into a negotiation protocol for conflict solving. Two-partie and multi-partie negotiation protocols are described. Topic areas: Cooperation, coordination, conflict. Communication issues.

---

A Game-Theoretic Approach to Distributed Control of Traffic Signals

A. Bazan

Back to titles

---

Following earlier approaches we use game-theoretic techniques to model the conflict of interest and cooperation among agents. We apply this techniques to the domain of traffic signal control whose usual strategies are modelled in a decentralized fashion. In our architecture traffic elements are modelled as single agents which have diverse knowledge represented by means of information sets. Lack of knowledge is modelled by means of games with incomplete information. Interactions among agents are both cooperative and noncooperative and are based on the rationality of the agents, which pick one of the equilibrium points of the game. Therefore the problem of equilibrium selection for noncooperative games is explored. For cooperative games the bargaining solution is used. Some examples of the traffic signal control domain which map interactions in noncooperative as well as in cooperative situations are presented.

---

An Adaptable Architecture for Environmental Monitoring

Jutta Mueller, Thies Wittig

Back to titles

---

This paper describes the architectural approach for Environmental Monitoring Systems and its application to the area of quality monitoring of river water. It presents the results of the ESPRIT* project EMS**. Based on the needs for water quality monitoring the requirements for an architecture capable to link distributed monitoring stations and laboratory databases are identified. Especially for adaptable and upgradable systems, information sources have to be described on a more abstract level. For this purpose a Logical Sensor Model approach has been adopted allowing the specification of data and control flow on different abstraction levels. Special emphasis is put on the three fusion layers: Sensor Validation, Situation Description, and Situation Assessment. Flexible and adaptable systems must be able to make their own decisions during a fusion process such as selecting specific sensors or applying different fusion techniques. In order to do this, an architecture concept based on Distributed AI principles is proposed. Area: Practical applications of multiagent systems

---

A view on the architecture and design of highly autonomous and situated agents

Masthoff, J., & Van Hoe, R

Back to titles

---

In the first part of this paper, a framework for the definition and classification of agent reseach is proposed. The major implication of this framework is that for systems embedded in a dynamic environment an approach based on highly autonomous and siutated agents is called for. In the main part of the paper, an architecture and a design process of complex agents are proposed. This is illustrated with a coaching application. In our architecture, a complex agent consists of a "society" of agents which are designed in an incremental, bottom-up manner according to what we call a behavioural engineering approach. The agents operate in parallel and have a close coupling between perception and action. Emergent functionality and memory-based learning characterize the adaptive behaviour of the agents. Furture research will focus on additional learning processes for the agents and will explore the concept of plans as a resource for situated action. Topic areas: agent architectures, agent design, multi-agent system application

---

A multi-agent approach to the design of coordination mechanisms

Monica Divitini, Carla Simone, Kjeld Schmidt, Peter Carstensen

Back to titles

---

For the purpose of designing coordination mechanisms for CSCW systems ('computational mechanisms of interaction') that support cooperating actors in managing the complexity of articulating their distributed and yet interdependent activities, a multi-agent architecture is proposed. Based on evidence from empirical studies of uses of artifactually embodied protocols for articulating cooperative activities, a set of constitutive agents and a characterization of their communication needs has been derived. The paper focuses on the primitives devoted to dynamic reconfiguration of computational mechanisms of interaction (C-MOIs), distributed cooperative control of propagation of changes to C-MOIs, and interoperation among multiple C-MOIs. The agents' Communication Language is constituted by primitives representing various modes of relating C-MOIs: reference, awareness, recursiveness, and linking. Topics covered: Cooperation, coordination, and conflict. Organization, organizational knowledge, and organization self-design.

---

Deriving Goals and Intentions

Graca Gaspar, Helder Coelho

Back to titles

---

Lately, defining intentions, as well as relating intentions to other components of the mental state of an agent, has been a topic of active research. However, when we look for foundations on which to base implementations of agencies, we get in real trouble because the formal side is too far from the engineering side. In this paper, we defend a model of goals and intentions, based on deductive structures, and an integrated framework for revising them, that can and has been adopted as a specification for designing and building up artificial agents. The development of our model has guided the parallel development of a workbench, and experimentation with earlier versions of the workbench has in turn provided guidance for the refinement and extension of the conceptual model. We argue that research for theoretical foundations of multiagent systems must open the way for such walks, forth towards implementations and back, in order to lead up to realistic models. Topic Areas: Agent models and architectures; Conceptual and theoretical foundations of multiagent systems

---

Linguistic Support for Agent Migration

R. Bordini, A. Rocha Costa, J. Hubner, R. Viccari

Back to titles

---

In this paper we propose some linguistic features to support the migration of agents between societies that have different communication mechanisms, that is, dealing with the problem of an agent entering any existing society whose communication means are unknown. We think that such features will become increasingly important in the account of complex, heterogeneous, adaptive, evolutionary, continuously running, open systems. We give intuitive ideas concerning the architecture of multi-agent systems where this phenomenon may occur. We propose that agents able to migrate must interpret a universal meta-language that can express in a formal way the syntax and semantics of the languages for protocol description and execution used in the target societies. We also propose that the arriving agents must have access to some minimum meta-protocols allowing them to perform minimal interactions leading to the learning of the protocols used in each society. Some implementation issues and future applications are discussed.

---

Actions with Typical Effects: Epistemic Characterization of Scenarios

Barbara Dunin-Keplicz, Anna Radzikowska

Back to titles

---

In this paper we study a problem of actions with typical, but not certain effects. We show how this kind of actions can be incorporated in a dynamic/ epistemic multi-agent system in which the knowledge, abilities and opportunities of agents are formalized as well as the results of actions they perform. To cope with a complexity of a rational agent behaviour, we consider scenarios composed of traditionally viewed basic actions and atomic actions with typical effects. We concentrate on a specific type of scenarios reflecting a "typical" pattern of an agent's behaviour. Adopting a model-theoretic approach we formalize a nonmonotonic preferential strategy for these scenarios in order to reason about the final results of their realization. Topic areas: Reasoning in Multi-Agent Systems, Reasoning about Actions.

---

RAPIDO: A Rapid Prototyping Toolkit for Developing Multi-Agent Systems

Mike Reddy

Back to titles

---

A range of toolkits are available for building and experimenting upon Multi-Agent Systems (MAS). However, determining the most appropriate paradigm for a particular domain is made more difficult when applications built with such tools are forced to adopt potentially inappropriate representation and implementation styles. This is further complicated by the lack of a general development methodology or a set of agreed metrics for evaluating agent architectures. Recently, Agent-Based Simulations (ABS) and testbeds have been suggested as a method for measuring the success of competing systems. However, without caution this approach may present yet another pitfall, when the performance measures must consider the implemetation of the underlying simulation as well as that of the agents. This paper proposes a tentative set of metrics for evaluating agent archtectures and describes the on-going development of RAPIDO, a paradigm-independent toolkit which goes some way to addressing the needs of multi-agent system developers. Keywords : Evaluation of Multi-Agent Systems, Integrated Testbeds and Development Environments

---

Some Principles in Designing Cooperative Architectures of Autonomous Agents

Lorenzo Sommaruga, Nadia Catenazzi

Back to titles

---

The purpose of this paper is to introduce some principles, in the form of assumptions, which could be useful to consider in developing agents architecture. These principles provide design guidelines concerning agent and group structuring, communication, decision making, and computational aspects for agent cooperation. They generate requirements and constraints for cooperative agents development. These principles have been derived from a long experience in designing and implementing architectural frameworks for agent cooperation, the CooperA project. In particular, basic characteristics of autonomous agents have been formalised in a computational model.

---

Distributed Flow Shop Scheduling Problem: Global versus Local Optimization

T. Daouas, K. Ghedira, J-P. Muller

Back to titles

---

Scheduling is an essential component of the manufacturing process. Because of its combinatorial character, its dynamic nature and its practical interest for industrial applications, the scheduling problem has been widely studied in the literature using exact or heuristic methods. In this paper, we propose a Multi-Agent approach to deal with the flow shop scheduling problem. Two alternatives to optimize the scheduling are proposed and compared in terms of quality and run-time; the first one using a global simulated annealing and the second one a local simulated annealing at the level of each agent.

---

Unifying Control In A Layered Agent Architecture

K. Fischer, J.P.Mueller, M. Pischel

Back to titles

---

A unifying control framework for describing the individual control layers of the InteRRaP architecture for autonomous interacting agents is presented. InteRRaP is a pragmatic approach to designing complex dynamic agent societies, e.g.~for robotics and cooperative scheduling applications. It is based on three general functions describing how the actions an agent commits to are derived from its perception and from its mental model: {\em belief revision and abstraction}, {\em situation recognition and goal activation}, and {\em planning and scheduling}. It is argued that each InteRRaP control layer - the behaviour-based layer, the local planning layer, and the cooperative planning layer - can be described by a combination of different instantiations of these control functions. The basic structure of a control layer is defined. The individual functions and their implementation in the different layers are outlined.

---

Distributed Symbolic-Subsymbolic Agent Architecture for Configuring Power Network Faults

R. Khosla, T. Dillon

Back to titles

---

Firstly, the paper outlines a set of generic tasks and the composition of symbolic and sub-symbolic methods to accomplish these tasks in data intensive domains in general and diagnostic domains in particular. These generic tasks and methods are defined within five phases (preprocessing, decomposition, control, decision, and postprocessing) of a Generic Integrated Information Processing Architecture symbolic and sub-symbolic (connectionist) systems. The information processing architecture has been based on pragmatic issues like real time, conscious and unconscious/automated behavior, learning, reliability, generalization, incorrect/incomplete information and others. Secondly, based on task, method and phase abstraction of the information processing architecture, a distributed heterogenous computational architecture of symbolic and sub-symbolic agents is developed. Issues associated with computational architecture like communication, parallelism, learning, and others are then discussed. The architecture has been applied in building a real time alrm processing system in a power system control centre with encouraging performance results. About 60 rules and 20 artificial neural networks have been used in alarm processing system.

---

An Agent System for Case Adaptation

R. Bhat

Back to titles

---

This article delineates an agent system to solve a particular design problem - conflict-free layout of supply-air systems in buildings. The structuring of this problem leads to a space of design tasks with a default order defined by the problem domain. Any one of these tasks can be the current task of the designer and is subject to influence from a case. The case is decomposed to extract a sequence of tasks to aid the designer in solving the current task, as well as geometric and relational information about the objects which make up the case. Each of these tasks in the case is instantiated into a computational agent, with a behavioral and a domain knowledge component. The behavioral component consists of a set of generic spatial actions, organised in layers. The domain component consists of knowledge needs for the layout of supply-air pipes. A generic control system is defined both for the interaction between the behavioral and domain component of the agent, as well as interaction between groups of agents. An interactive application of the designer, information from the case and agents then drives the problem to an intended solution. A scenario is sketched to give an idea of the case adaptation system in action. Keywords: Agent Systems, Case Adaptation, Active Medium

---

Map Making as a Support for Cooperation

F. Chimura and M. Tokoro

Back to titles

---

We take up a meeting task where agents try to gather into a single location starting from distributed arrangements. An efficient solution is one in which all agents work simultaneously, and in which the meeting location determines adaptively. However, the difficulty with this solution is that the agents, and hence the meeting location, will move unpredictably. We evaluate a dynamic solution that uses the trailblazer search as the search strategy of agents. Considering the tradeoff between reaction time and number of moves, the trailblazer search is an algorithm that dynamically maintains a map of where an agent has already searched through in the problem space (Chimura & Tokoro 94). Through a simple simulation we show the effect of agents maintaining maps, hence show that mapping functions can facilitate cooperation in meeting tasks.

---

The Consensus Scheduling Model: Negotiation among Peers

William B. Day

Back to titles

---

The Consensus Scheduling Model (CSM) is introduced as a way to accommodate negotiation in over-constrained, distributed scheduling problems. The CSM is appropriate for negotiation among a group of peers and is also applicable to a manager that must balance conflicting views of its workers. The distributed scheduling algorithm that is used selects a candidate >from the priority list of resource requests and inserts that candidate into the evolving timetable. Two protocols are required. The minimax protocol assures equitable power among the peers. The bumping protocol allows reactive scheduling by using a request's total worth to dictate when a new request can seize a previously assigned resource. A request's total worth is the sum of its priority value, its ordering value, and any bonus points received by previous negotiations. Three styles of negotiation are examined: unilateral, verbose, and periodic. Results from sample scenarios are also presented.

---

Automated Multiagent preference aggragation using fuzzy quantifiers

Ronald R. Yager

Back to titles

---

This paper concerns itself with the problem of aggregation of preference functions associated with a group of agents for the purpose of making a decision. We suggest a formulation for the overall preference function, the negotiation rule, which makes use of concepts drawn from the fuzzy subset literature. In particular we use the idea of a linguistic quantifier to formulate the overall preference function.

---

Modeling and Studying Social Belief

Gregg Courand and Michael Fehling

Back to titles

---

We present results of our research on organizations and their agents. This work aims to improve upon current understanding of organizational dynamics and to devise new techniques to enhance organizational performance. We rely fundamentally on computational methods for modeling organizational dynamics to rigorously explore interesting hypotheses and assess the potential effects of organizational re-design. We discuss a new theory of social belief; social beliefs are situated relationships among the dispositions toward situated actions of organizational agents. We describe a specific computational representation of this notion, Belief Structures. We outline ACCORD, our computational model of organizational dynamics. This model depicts organizational structure and function as patterns of distributed cognition and action manifested by organizational agents. We also describe a discrete event simulator that implements the full ACCORD model. Finally, we examine the role of Belief Structures within the ACCORD model and discuss an ongoing simulation study that employs these notions.

---

A Microeconomic Approach to Intelligent Resource Sharing in Multiagent Systems

Jaeho Lee and Edmund H. Durfee

Back to titles

---

We have analyzed characteristics of sharable resources and developed techniques for intelligently sharing resources --- specifically, communication channels --- among agents in multiagent systems. Our techniques allow agents to nearly optimize their communication behavior in a self-organizing and distributed fashion, involving the use of a microeconomic pricing system based on economic laws of supply and demand and trading among agents in real-time. Our analyses are based on three measures of performance: fairness of resource allocation, waiting time for resources, and utilization of resources. Our initial analysis indicates that fairness and utilization are conflicting, in that the best utilization with a fair allocation is equivalent to the worst utilization with an unfair resource allocation, assuming the allocation policy is statically defined. To strike a balance in performance, we have developed mechanisms that establish an artificial economy, where agents can dynamically reallocate goods (resource access) using a competitive market pricing mechanism. However, unlike more common market-oriented methods, our approach does not demand convergence to equilibrium, but permits more rapid, heuristic trading, leading to near optimal performance where both buyers and sellers of resources can benefit. Our studies show that agents employing our mechanisms can dramatically improve utilization while still providing ``fair'' access to the resources.

---

Multiagent Coordination in Distributed Interactive Battlefield Simulations

John E. Laird, Randolph M. Jones, and Paul E. Nielsen

Back to titles

---

The fielding of large numbers of autonomous computer-generated forces requires that these forces be able to coordinate their behaviors. TacAir-Soar represents a data point where individual fighter planes must fly together in sections with support from ground, surface, and air-based controllers. In this paper we analyze the types of coordinated behavior required to make TacAir-Soar a realistic model of human behavior, the methods that our agents employ to coordinate their behavior, and finally, the constraints coordination places on the design of computer-generated forces. Topics: Coordination Practical Applications of Multiagent systems

---

Evolving Cooperation Strategies

Thomas Haynes, Roger Wainwright & Sandip Sen

Back to titles

---

The identification, design, and implementation of strategies for cooperation is a central research issue in the field of Distributed Artificial Intelligence (DAI). We propose a novel approach to the construction of cooperation strategies for a group of problem solvers based on the Genetic Programming (GP) paradigm. GP's are a class of adaptive algorithms used to evolve solution structures that optimize a given evaluation criterion. Our approach is based on designing a representation for cooperation strategies that can be manipulated by GPs. We present results from experiments in the predator-prey domain, which has been extensively studied as an easy-to-describe but difficult-to-solve cooperation problem domain. They key aspect of our approach is the minimal reliance on domain knowledge and human intervention in the construction of good cooperation strategies. Promising comparison results with prior systems lend credence to the viability of this approach. Topic areas: evolutionary computation, cooperation strategies

---

The Consensus of Uncertainties in Distributed Expert Systems

Minjie Zhang and Chengqi Zhang

Back to titles

---

This paper deals with the consensus of uncertainties in distributed expert systems (DESs). It claims that the different uncertainties of a solution from different expert systems constitute not only a conflict case, but also non-conflict cases. We will refer both the conflict case and non-conflict cases as synthesis cases. The first objective of this paper is to classify the synthesis {\it cases}, identify the {\it types} of DESs, and recognize the {\it relationships} among the different synthesis cases and the different types of DESs. On the basis of this, a computational synthesis strategy is proposed to obtain a consensus of uncertainties in a conflict case. Within this strategy, the conflict case is further classified into two sub-cases, and two corresponding sub-strategies are proposed, in which both uncertainties and authorities are taken into consideration. A synthesis strategy based on neural networks is also proposed in a conflict case. In this strategy, as long as enough patterns have been obtained from human experts, neural networks can be trained to match all patterns. This strategy can simulate human experts reasonably well. Tests have also shown that a fixed neural network architecture can be used to solve conflict problems, with a variable number of inputs and outputs. That means only a small number of neural networks are required to solve all conflicts, thus the neural network can be used in real DESs. Finally, a computational synthesis strategy is compared to a neural network synthesis strategy. Both strategies have advantage and disadvantage and are adapt to different situations.

---

Self-Organization based on Coordinated Actions of Autonomous Agents

Satoshi Kurihara and Michio Okada

Back to titles

---

This paper shows a study on a mechanism for self-organization. A global order is organized by simple and locally coordinated actions of autonomous agents using only very local information, and not by their complex and globally coordinated actions which would use global message passing and high level strategies. The fundamental factors for establishing the global order by self-organization are ``dissipative structure'' and ``self-catalysis mechanism.'' If an environment where agents exist has a dissipative structure and those agents have some sort of self-catalysis mechanisms within themselves, it is possible to form a global order of agents by their simple and locally coordinated actions. ``The blind-hunger's dilemma'' is used as an example to simulate the self-organiza\-tion and coordinated actions of agents and to show the validity of our approach.

---

Asynchronous Weak-commitment Search for Solving Large-Scale Distributed Constraint Satisfaction Problems

Makoto Yokoo

Back to titles

---

We present a new algorithm for solving distributed constraint satisfaction problems called asynchronous weak-commitment search. This algorithm removes the common drawback of backtracking algorithms, i.e., one bad decision in value selection becomes fatal when solving large-scale problems, while its completeness is guaranteed. The basic ideas of this algorithm are as follows: (i) bad decisions are revised without an exhaustive search by changing the priority order of agents dynamically, (ii) the probability of bad decisions being made is reduced by selecting values cooperatively using the min-conflict heuristic [Minton et al. 92]. Although these ideas are very simple and domain independent, experimental results indicate that this algorithm can solve large-scale problems, which can not be solved efficiently by backtracking algorithms. These results imply that the algorithm's efficiency can actually be improved by adopting intuitively natural notions, i.e., the fair establishment of the priority order, and the cooperative value selection considering the situations of other agents.

---

AgenTalk: Coordination Protocol Description for Multiagent Systems

Kazuhiro Kuwabara, Toru Ishida, Nobuyasu Osato

Back to titles

---

This paper presents a language called AgenTalk for describing coordination protocols for multiagent systems. Many coordination protocols such as the contract net protocol have been proposed, and many application-specific coordination protocols are expected to be required soon as more software agents start to be built. However, no general framework has yet been proposed for defining and implementing such coordination protocols. AgenTalk is designed to solve this problem; it allows coordination protocols to be defined incrementally and to be easily customized to suit application domains by incorporating an inheritance mechanism. This paper describes the design policies of AgenTalk and demonstrates its capability by describing the contract net protocol and the multistage negotiation protocol in AgenTalk utilizing its inheritance mechanism. A comparison is made with KQML (Knowledge Query and Manipulation Language), and the relationships with related research in distributed artificial intelligence are discussed.

---

A quantitative analysis of the Contract Net Protocol

Cheng Gu and Toru Ishida

Back to titles

---

The Contract Net Protocol (CNP) assigns a subtask to agents which are involved in multiagent problem solving. Although the logical aspects of the negotiation protocol have been analyzed, the properties of protocol dynamics remain unclear. This paper introduces our quantitative analysis of protocol dynamics which is essential for constructing continuous realtime applications. In this paper, a simulation independent of any application has been carried out in order to analyze the dynamic properties of the CNP. We have obtained the following results: the contractor utility increases together with the system load while the manager utility decreases; when the number of agents increases, the contractor utility rises while the manager utility does not change; the uniformity of agents causes the concentration of ``bids'' and ``awards,'' and thus decreases the manager and the contractor utility. Furthermore, we apply our simulation results to analyze Enterprise, a famous application of the CNP, and point out the problem which might arise in Enterprise.

---

Hierarchy and Network: A Mathematical Model of Performance for Structural Choice

Toshizumi Ohta, Tadashi Yamamoto, and Kazunari Ishida

Back to titles

---

We propose an organizational performance model with respect to organizational structure. Using the model, we propose a predominant organizational structure which agents should select in order to perform efficiently additional tasks. The hierarchical organization is characterized by uni-directional dependencies between agents, and the network type organization is characterized by uniformly bi-directional dependencies. In this paper, we will assume that an organization consists of three agents. Four typical organizational structures of three agents are identified as Isolated, Hierarchy, Hierarchy with Delegation, and Network. In order to discuss the predominant organizational structure with respect to additional tasks for agents, we will employ factors concerning an amount and a nature of tasks (i.e., routine or non-routine), and a nature of requisite coordination (i.e., planning or feedback). In conclusion, the model formulated in this paper would successfully describe the predominant organizational structure to support the agents who have to select it due to the additional tasks.

---

Organic Programming for Multi-Agents

Hideyuki Nakashima, Itsuki Noda, and Ichiro Ohsawa

Back to titles

---

We are developing a new software methodology for building large, complicated systems out of simple units. The emphasis is on the architecture (called cooperative architecture) which is used to combine the units, rather than on the intelligence of individual units. We named the methodology ``organic programming'' after the flexibility of organic systems such as plants and animals. In this paper, we will describe the application of an organic programming language Gaea to description of multi-agent system. One of the advantages resides in that we can program the system in a subsumptive manner.

---

Rational Balancing of Planning and Communication in the Dynamic Multi-Agents World

Sachiyo Arai

Back to titles

---

This paper presents an agent model that makes a rational decision for balancing cost of planning and communication in a deliberation phase to adapt a dynamic world. The agent's ability for balancing these factors is very important in the multi-agents world as well as that for balancing deliberation and execution cost in the dynamic world. To realize this ability, we introduce two behavioral parameters, namely, the {\em projection level} and the {\em commitment level}. One controls how far the agent should project in his future based on his current state at the beginning of the planning. The other controls how far the agent should adhere to his plan when he detects change in the world. We show that the agent can control his time cost of planning and communication by changing these levels and , as the result of this, he can make a good plan on that occasion as well as adapt to changes in the world.

---

Learning Coordination Plans in Distributed OS Environments

Toshiharu Sugawara, Victor Lesser

Back to titles

---

Coordination is an essential technique in cooperative, distributed multi-agent systems. However, sophisticated coordination strategies are not always cost-effective in all problem-solving situations. This paper presents a learning method to acquire coordination plans for specific problem-solving situations so that the appropriate type of coordination strategy is used. This learning is accomplished by recording and analyzing traces of inferences after problem solving. The analysis results in identification of situations where inappropriate coordination strategies have caused redundant activities or the lack of timely execution of important activities, thus degrading system performance. Based on this identification, situation-specific coordination plans are created which use additional non-local information about activities in the networks to remedy the problem. An example from a real distributed problem-solving application involving diagnosis of a local area network is described.

---

Autonomous Agent Control: A Case for Integrating Models and Behaviors

I. A. Ferguson

Back to titles

---

It is becoming widely accepted that neither purely reactive nor purely deliberative control techniques are capable of producing the range of behaviors required of intelligent computational agents in dynamic, unpredictable, multi-agent worlds. This paper presents an architecture for controlling and coordinating autonomous agents, building on previous work addressing reactive and deliberative control methods. The proposed multi-layered architecture allows a resource-bounded, goal-directed agent to reason predictively about potential conflicts by constructing knowledge level models which explain other agents' observed behaviors and hypothesize their intentions; additionally it enables the agent to operate autonomously, to react promptly to changes in its real-time environment, and to coordinate its actions effectively with other agents. A principal aim of this research is to understand the role different functional capabilities play in constraining an agent's behavior under varying environmental conditions. To this end, an experimental testbed has been constructed in which a variety of agent configurations and behaviors have been investigated. Some experimental findings are reported.

---

Agents as Reasoners, Observers, or Arbitrary Believers

Giunchiglia, Giunchiglia, and Serafini

Back to titles

---

The work described in this paper aims at the definition of a general framework for the formal specification of agents' beliefs in a multiagent environment. This framework formalizes and composes two basic ideas. The first is that of {\it reasoner}, where a reasoner is an extensional representation of an agent's beliefs or of a view of an agent's beliefs. The second is that of {\it observer} i.e. of reasoner having beliefs about another reasoner. Reasoners and observers can be uniformly represented and composed in {\it belief systems} to describe complex multiagent scenarios. Belief systems are naturally presented using {\it Multi context systems}. We show how some of the modal approaches to the formalization of (non) omniscient belief can be captured within our framework.

---

An Agent Model in a Multiagent System Architecture for Automating Distributed Systems

Truszkowski, Odubiyi, and Ruberton

Back to titles

---

In this paper we discuss the conceptual foundation for a Multi-Agent System (MAS) which has been designed to provide easy access to distributed heterogeneous information and processes for a wide variety of users. A basic agent model has been developed and is used to characterize the agents of the MAS. Using this model three classes of agents have been currently identified and incorporated into the MAS testbed. These are: the user interface agent which serves as the main point of interaction between a user and the MAS; an agent manager which is responsible for coordinating the activities of a community of agents within the MAS; and domain agents whose specialized knowledge enable them to accomplish domain-specific tasks. In the context of the MAS testbed we are able to address several research issues such as user modeling, cooperative activity among agents, handling incomplete requests, and inter-agent and human user-to-agent interactions.

---

---

Back to ICMAS page.

---

If you have questions, problems or suggestions send mail to www@icmas.cs.umass.edu

Last Update: 13 April 95