Intelligent Systems Laboratory
This project aims to develop methods to decentrally coordinating the
actions of agents. Coordination is broadly the process of
deciding when a task should be performed and which resources that should
be used. Coordination is necessary in domains where resources are shared
between agents, when the resources are limited and when using a resource
can inhibit another agent from fulfilling its goals.
Coordination can be performed centrally by a global planner or
in a decentralized fashion. Global planning is the process
of collecting information from all agents involved and using that to design
a (unique) time plan for each agent. The agent may not deviate from
this plan during execution. Decentralized planning means that the
decisions of which actions to take are delegated to the agents. It
almost always also implies that each agent makes its decision based on
only a subset of the information used by the global planner. This
has the advantage of allowing the agents to make faster decision and to
make partial changes in their plans if their goals or environment changes.
An algorithm that only uses a subset of the total information may be
unable to find the optimal solution of a coordination problem, something
which may or may not be acceptable depending on the domain. Therefore,
many decentralized algorithms are search heuristics approaching good solutions
rather than a computation delivering the optimal global behavior.
Decentralized coordination is therefore useful for problems where no global
planner can deliver a solution within reasonable time.
Another (and perhaps more interesting) area where decentralized coordination
may prove useful is in domains where the first priority of a participating
agent is to maximize its own performance rather than the global
performance. Competing organizations/companies as well as individuals
can be represented by such agents. For companies, a decentralized
coordination framework will allow sharing and trading of resources as long
as it is beneficent for the individual companies. Individuals will program
their personal assistants to prioritize the interest of its client user
over that of other agents (such as advertisers or sales agents).
We call the domain open when it intends to support the existence
of self-interested agents. Domains that do not assume that agents
are self-interested will have to control and limit which agents that may
interact with the system, i.e. the system will in generally be closed.
Compared to other research in this area where agents can negotiate and
commit, a market based approach has "simpler" interactions (only bidding),
and can therefore be expected to be faster. But if we only allow
bidding on the resources, agents have no way to construct more complex
plans without large risks or inefficiency. Therefore, we will introduce
derivatives into the market, and design agents that generate plans by bidding
on options and/or futures. This may allow agents to produce complex
plans, indirectly taking into use the capabilities of several other agents.
In a market (without external events), resources are iteratively interchanged
towards a more stable state of allocation. When events occur, such
as adding new resources to the system or failure of participating components,
the prices of the resources change as a result of the event. This
will cause the agents to take on trading again, but considering the new
state of affairs. In this sense, a market based system can be considered
to be self-coordinating and adaptive.
The result of the inability to design complex systems is a comparatively
low level of interaction among systems. Even highly computerized organizations
often use separate systems with no or little inter-connection. But
this is under a strong pressure of change from business re-engineering
processes that necessitate an a potentially very profitable integration
of systems and information.
Coordinating the work of several independently working individuals can
enable several new services. For example, software agent technology
can create digital markets (market spaces) where companies can establish
business contacts and help them to put together their middle-ware products
into complete products. The simple interactions of offering and buying
products can be transformed into a complex system of product refinement,
without the need of a large organization directing production towards the
goal. Not all systems support such a transformation process.
This study will provide insight into ways of designing systems that support
integration.
Our goal is to develop methods and mechanisms that enable us to construct
robust open systems of highly interacting parts.
We will investigate how to design systems with decentralized coordination
by creating the necessary tools and communication protocols to allow systems
to delegate tasks and coordinate their actions and resource usage.
We will investigate how vulnerable the proposed protocols are to manipulation
and misbehavior, both deliberate and unintended. Computer models
and simulations will be made, as well as the integration of the results
into existing agent-frameworks currently under development at SICS.
Self-coordinating systems are robust in the sense that they can reconfigure
and adapt to a dynamic environment. The robustness should be on two levels:
Agent-oriented coordination of tasks is often done in a decentralized
fashion, where agents distribute tasks among themselves through negotiations,
rather than by using a central planner. Agents use facilitators to
locate possible agents that they can cooperate with, and requests the other
agent to perform the task at hand. Market-oriented programming further
reduces the negotiation process to a Contract Net like protocol [12]
of bidding and awards.
The most interesting question to investigate to see to what extent it
is possible to express more complex behavior as commitments and delegations
in terms of actions using financial instruments. For instance, can
an agent delegate its intention to achieve a task to another agent by buying
a certain portfolio of futures or options? This would have two large
advantages, namely the speed of interaction and to translate utility to
economic terms.
Speed would increase since the agent would simply announce intentions
to buy or sell financial instruments. It would not have to locate
potential interested agents itself, nor would anyone have to figure out
a way to partition the tasks among several agents.
The network market consists initially of a commodities exchange where
agents announce bandwidth that they have bought from the routers.
Other agents represent consumers with certain needs for bandwidth.
Consumer agents will buy traffic at the market for prices that determined
by the current traffic and congestion levels in the network.
We will extend this model to a market of distributed commodity
exchanges. It is desirable to have several exchanges, since it
reduces the bottle neck that a single exchange would become.
This however generates a whole new set of problems. Agents have
to decide on which markets they should announce their bids, if they
should announce the same resource on several markets, etc. Live
loops may occur in the bidding, which has to be avoided.
With complex financial instruments such as options or futures, it may
be possible to create behavior similar to coalition formation or shared
plans. Compared to other research in this area where agents can negotiate
and commit, a market based approach has "simpler" interactions (only bidding),
and can therefore be expected to be faster. But if we only allow
bidding on the resources, agents have no way to construct more complex
plans without large risks or inefficiency. Without the ability to
ask others for help, agents have to buy resources speculatively, not knowing
if they will eventually obtain all the required resources.
A market with derivatives may allow agents to produce complex plans,
indirectly taking into use the capabilities of several other agents.
An agent that needs a particular resource in the future may need to plan
that it has the resource. Agents may reduce the risk they take when
they plan, by buying an option to obtain the resource at a later time.
The interesting thing about this is that it reduces coordination through
negotiation to a risk decision problem, which may be faster to compute.
Cooperative behavior as an emergent property of complex systems is a
very active area also in distributed artificial intelligence. For
example, the Santa Fe Institute in New Mexico is devoted to the study of
complex systems, including medicine, genetics, A-Life and more.
Copyright © 2001
SICS AB, All Rights Reserved.Coordination Methods for Open Distributed Systems
This project aims to develop methods to decentrally coordinating
the actions of agents by using market-based models of
interaction. We are interested in how to construct complex plans
and resource allocations, and applying the results in a "band-width
market". The new idea is to use derivatives to express more complex
resource demands while maintaining the volatility of the resources in
the market.
Contents
Global vs. decentralized
planning
Complex technical systems need to be able to coordinate their behavior
by themselves when they get interconnected. Integrating information
systems often greatly increases the usefulness of the combined systems,
but when two systems initially designed to work alone get interconnected,
the combined behavior may become undesirable. For instance, connecting
two computer systems that handle resources at a company may generate dead-locks
and failure to allocate resources properly. A way to design systems
in a way that the behave desirably or "gracefully" even when they are interconnected
is needed. Designing systems for decentralized coordination is one
way to tackle some of the potential problems that may arise.
Factories, communication networks and company work flow are all examples
of domains where coordination is necessary.
Market-oriented coordination
The project will in particular investigate market-oriented approaches to
coordination. A key idea for this approach is to represent the systems
and resources that need to be coordinated by agents that broker their resources
on an exchange. Other agents are responsible for obtaining the resources
needed to fulfill the goals of the users. Coordination of the resources
amounts to exchanging resources and finding market prices such that all
agents are satisfied. Note that satisfied means that the agent has
no intention to trade, which can be the case if the resources are too expensive.
Project motivation and objective
Many large distributed systems of today are very vulnerable to change and
misuse. The fact that they are not open systems and that it is a
single organization that controls what is added to the system has somewhat
limited the potential danger. For example, the telephone network
would be vulnerable if anyone could connect their own switch to it, not
to speak of adding their own software. One is often even reluctant
to introduce improvements or even bug fixes, as it is difficult to foresee
the consequences of changes to a system in which all components are critically
dependent on each other .
Research topics
Market oriented programming
The market oriented programming paradigm [1, 3,
13] deals with allocating resources among agents [10].
Consumers of shared resources in a system are modeled as agents that buy,
sell, produce or consume resources.
Topics
The topics we start out to investigate are among others
Our research hypothesis is that market-oriented programming will generally
be a lot faster negotiation mechanism than the more complex conversations,
but that the framework for coordination will have to support both kinds
of coordination.
In previous work we were concerned with the possibility to manipulate
agents into performing actions that were potentially harmful for their
clients. By translating the utility of actions into economic terms,
an agent will have a better opportunity to compute the real benefit and
risk that is associated with its decision.
A network market
In the first year we will create a simulation environment for routing
of telephone and Internet traffic in a computer network
environment. The problem specification comes from a related
cooperation project at SICS with Telia. The Swedish telephone
backbone consists today of about ten thousand routers that route the
traffic between towns. The configuration (topology) of the
network is constrained by several factors that depend on the
particular routers that exist, such as maximum through-put, number of
virtual channels, etc. The goal of the network market is to
create a routing behavior that is flexible, can reorganize traffic in
case of partial failure, incorporate new routers and even to allow
other telecom providers to connect their networks to the system.
Planning
"Options trading is the trading in rights and obligations. You pay for
the rights and you get paid for the obligations.'' -- OM
Related work
Some related international
research
For a fuller account of related research, please refer to the bibliographic
study Decentralized coordination of open distributed systems [7].
Software agent systems
Software agent systems consist of computer programs that autonomously contact
different service providers, trying to obtain a goal that matches
a request from its client. One popular example is a travel agent
that puts together a complete itinerary for a long trip, matching plain
schedules with buses, taxis etc. and orders the tickets. The
client just specifies when and where she want to go, and the agent knows
about personal preferences such as window/aisle seat etc., from earlier
missions.
Research with great commercial interest is being carried out in the
software agent area. The majority of this is in the United States,
but also Japan and many other European countries show considerable interest.
For a survey of current activities in this area, see http://www.sics.se/isl/abc/survey.html.
Coordination
The research area of coordination as applied to general complex systems
is relatively new, although some roots (organization theory, market economy
dynamics) can be traced back several decades. It has gained a lot
of scientific interest, especially due to the explosive growth of interconnected
computer systems.
Economic approaches
Research in economic approaches for organizing complex systems is made
by [7] and [6] and others. Non-manipulable
communication protocols for collaboration formation are investigated by
[9] and [2]. The use of ecological
models to investigate computational aspects of complex systems is promoted
by [3] and [5].
One system that uses market oriented programming techniques is the
TRACONET system by Tuomas Sandholm at the University of Michigan [11].
TRACONET is a system of transportation agents that collaborate to find
an efficient way to transport goods, sharing the work among them.
Sandholm has investigated several of the issues of security in market oriented
programming, such as safe exchange of goods, etc.
The market that we will investigate under the first year will partly
resemble the transportation economy of Sandholm or that of Wellman [13,
14], but our focus will be on plan generation and on
how to express more complex relationships between the agents than has been
possible in the earlier work. For instance how to design a bid such
that it resembles an offer for a set of other agents to take part in a
plan.
References
http://ccs.mit.edu/1994wp.html.
http://www.acm.org/pubs/articles/journals/surveys/1994-26-1/p87-malone/p87-malone.pdf
http://www.agorics.com/agorpapers.html
http://www.agorics.com/agorpapers.html
http://www.sics.se/~lra/exjobb/simsoccontr/simsoccontr.html
ftp://ftp.cs.umass.edu/pub/lesser/sandholm-aaai93-traconet.ps
http://ic-www.arc.nasa.gov/ic/jair-www/volume1/wellman93a.ps
ftp://ftp.eecs.umich.edu/people/wellman/aaai94ext.ps.Z
Maintained by Lars Rasmusson, 1998-04-29
For more information on the SICS Intelligent Systems Laboratory
please email sverker@sics.se.