First International Conference on Multiagent Systems
June 12 - 14, 1995
San Francisco, California
Back to ICMAS page.
Formal Approaches (12)
Game Theoretic Approaches (6)
Formal agent Frameworks (2)
Reasoning about Knowledge and Belief (4)
Agent Societies (8)
Multi-agent, Collaborative Interfaces (3)
Emergent Behaviors (2)
Social Commitment (3)
Building Agents: Tools for Specification and Coordination (10)
Testbeds and Specification Tools (4)
KQML (3)
Applications (8)
General Applications (4)
Robotics (4)
Distributed Algorithms (10)
Multi-Agent Planning (4)
Distributed Search (4)
Distributed Constraint Satisfaction (2)
Market-based Approaches (5)
Market-based Coordination (3)
Resource Contention (2)
Formal Approaches
Game Theoretic Approaches
- Time and the prisoner's dilemma
- Introducing Blind Hunger Dilemma
Chisato Numaoka
- Coordination without Communication: Experimental
Validation of Focal Point Techniques
M. Fenster, S. Kraus, J. S. Rosenchein
- A Game-Theoretic Account of Cooperation in Communication
Koiti Hasida, Katashi Nagao, and Takashi Miyata
- A Rigorous, Operational Formalization of Recursive Modeling
Piotr J. Gmytrasiewicz and Edmund H. Durfee
- Recursive Agent Modeling using Limited Rationality
Jose M. Vidal and Edmund H. Durfee
Formal agent Frameworks
- A Formal Framework for Agency and Autonomy
Michael Luck and Mark d'Inverno
- BDI Agents: from theory to practice
Anand Rao and Michael Georgeff
Reasoning about Knowledge and Belief
- Generalised Proof-theoretic Multi-agent Autoepistemic Reasoning
Yongyuth Aramkulchai and Y.J.Jiang
- Multiagent Reasoning with Belief Contexts II: Elaboration Tolerance
A. Cimatti, L. Serafini
- Towards a Pragmatic Theory of Interactions
A. Haddadi
- Reasoning about belief based on common knowledge of
observability of actions
Hideki Isozaki
Agent Societies
Multi-agent, Collaborative Interfaces
- Multiagent collaboration in directed improvisation
B. Hayes-Roth and L. Brownston
- Communication for conflict resolution in multi-agent collaborative planning
Jennifer Chu-Carroll, Sandra Carberry
- PARAgente: Exploring the Issues in Agent-Based User Interfaces
J. A. Sanchez, F.S. Azevedo, & J.J. Leggett
Emergent Behaviors
- The Emergence of Cooperation in a Society of Autonomous Agents
Akira Ito and Hiroyuki Yano
- Understanding the Emergence of Conventions in Multi-Agent Systems
A. Walker, M.Wooldridge
Social Commitment
- Commitments: from individual intentions to groups and organizations
Cristiano Castelfranchi
- Deciding when to commit to action during observation-based coordination
Marcus J. Huber and Edmund H. Durfee
- Exploiting Social Reasoning to Deal with Agency Level Inconsistency
J. Sichman and Y. Demazeau
Building Agents: Tools for Specification and Coordination
Testbeds and Specification Tools
- Formal Specification of Multi-Agent Systems: a Real-World Case
F. Brazier, B. Dunin-Keplicz, N. Jennings, J. Treur
- How Agents Do It In Stream Logic Programming
Matthew M Huntbach, Nick R Jennings and Graem A Ringwood
- The DRESUN Testbed for Research in FA/C Distributed Situation
Assessment: Extensions to the Model of External Evidence
N. Carver and V. Lesser
- Understanding Cooperation: an Agent's Perspective
Andreas Lux, Donald Steiner
Coordination Tools
- Designing a Family of Coordination Algorithms
Keith Decker and Victor Lesser
- A Tool For Coordinating Autonomous Agents With Conflicting Goals
Love Ekenberg, Magnus Boman, Mats Danielson
- A Cooperation Language
Michael Kolb
KQML
- Communicative Actions for Artificial Agents
Philip R. Cohen and Hector J. Levesque
- COOL: A Language for Describing Coordination in Multiagent Systems
Mihai Barbuceanu and Mark S. Fox
- On using KQML for Matchmaking
Daniel Kuokka and Larry Harada
Applications
General Applications
- A Multi-Agent Intelligent Design System Integrating
Manufacturing and Shop-Floor Control
Sivaram Balasubramanian and Douglas H. Norrie
- A Model For Cooperative Transportation Scheduling
K. Fischer, J.P.Mueller, M. Pischel
- A Multiagent System for Controlling Building Environments
B. A. Huberman and S. H. Clearwater
- DIDE: A Multi-Agent Environment for Engineering Design
Weiming Shen, Jean-Paul Barthes
Robotics
- Motor Schema-based Formation Control for Multiagent Robot Teams
Tucker Balch and Ronald C. Arkin
- Unsupervised Multi-Agent Exploration Of Structured Environments
Dario Maio, Stefano Rizzi
- Recursive Agent and Agent-Group Tracking in a Real-time Dynamic Environment
Milind Tambe
- Hierarchical and Lateral Coordination in MAS : An analysis of
Message Traffic Flow
Alois Knoll, J. Meinkoehn
Distributed Algorithms
Multi-Agent Planning
- A Tractable Heuristic That Maximizes Global Utility Through Local Plan
Combination
Eithan Ephrati, Martha Pollack, and Jeffrey S. Rosenschein
- Synchronizing Multiagent Plans using Temporal Logic Specifications
Froduald Kabanza
- A Metalevel Coordination Strategy for Reactive
Cooperative Planning
Ei-Ichi Osawa
- Reusing past plans in distributed planning
Toshiharu Sugawara
Distributed Search
- Knowledge-Based Distributed Search Using Teamwork
Joerg Denzinger
- Two is not Always Better than
One: Experiences in Real-Time Bidirectional Search
Toru Ishida
- Unsupervised Surrogate Agents and Search Bias Change in Flexible
Distributed Scheduling
Sandip Sen and Edmund H. Durfee
- Distributed Scheduling of Multiagent Communication
Y. Xiang
Distributed Constraint Satisfaction
- Forming Coalitions for Breaking Deadlocks
Katsutoshi Hirayama and Jun'ichi Toyoda
- Exploiting Problem Structure for Distributed Constaint Optimization
JyiShane Liu and Katia Sycara
Market-based Approaches
Market-based Coordination
- A Simple Computational Market for Network Information Services
T. Mullen and M. P. Wellman
- Issues in Automated Negotiation and Electronic Commerce:
Extending the Contract Net Framework
Tuomas Sandholm and Victor Lesser
- Self Organizational Approach for Integration of Distributed
Expert Systems
Tatsuaki Itoh, Takashi Watanabe, and Takahira Yamaguchi
Resource Contention
- Dilemmas in computational societies
N.S. Glance and T. Hogg
- Resource contention in multiagent systems
M. Youssefmir and B.A. Huberman
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 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.
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.
Back to ICMAS page.
If you have questions, problems or suggestions send mail to
www@icmas.cs.umass.edu
Last Update: 13 April 95