Multi-Agent System

From CasGroup

Jump to: navigation, search

A Multi-Agent System (MAS) is a system composed of several autonomous agents which are able to interact and communicate with each other. In software, MAS are realised as software agents. The field of MAS is related to Distributed Artificial Intelligence (DAI) and also to distributed systems. MAS is also an abbreviation for Mobile Agent System. Normally, Mobile Agent Systems are also Multi-Agent Systems, but generally with less emphasis on intelligence but on mobility.

Contents

Elements

Agents represented by abstract actors or persons

Basic elements of a MAS are (a) the agents themselves (b) their interaction and communication (c) the necessary middleware or environment. Another important but optional element is (d) organization. If the system as a whole should fulfil a function, it needs certainly a kind of organization. The name MAS may be understood as the community of autonomous, interacting agents, which emphasizes the aspect (a), or as the support system together with its agent community, which highlights aspect (c). As Wooldridge says in his MAS book (2002), the idea of a MAS is simple: "An agent is a computer system that is capable of independent action on behalf of its user or owner. In other words, an agent can figure out for itself what it needs to do in order to satisfy its design objectives, rather than having to be told explicitly what to do at any given moment. A multiagent system is one that consists of a number of agents, whicht interact with one another, typically by exchanging messages through some computer network infrastructure."

Autonomous Agents

As the name says, a Multi-Agent System is a system composed of several autonomous agents. Agents are of course the most basic parts and elements of any Multi-Agent System. The agents vary in their number, mobility, intelligence and internal architecture. A MAS can be defined as a collection of autonomous agents that interact to solve problems that are beyond the individual capabilities or knowledge of each agent. Katia P. Sycara enumerates three major characteristics of multiagent systems in her AI Magazine article about "Multiagent systems" (1998): (1) each agent has incomplete information or capabilities for solving the problem and, thus, has a limited viewpoint; (2) there is no system global control; (3) data are decentralized; and (4) computation is asynchronous. This means that the actions and decisions of the individual agents must be based on local information and situations, the agents must interact and cooperate with each other to solve the common goals, and they can communicate with messages which can arrive at any time. In other words, MAS have many properties associated with building traditional concurrent or distributed systems.

Interaction and Communication

Communication is a central property of any distributed system, and it is very important in MAS. A basic from of communication is "physical interaction" through collision or being at the same place. In principle any language could be used, as long as the agents can understand each other. To make agents understand each other they have to speak the same language, and have to share a common knowledge, for example a kind of ontology. An ontology for agents describes what kind of things an agent can deal with and how they are related to each other.

The communication between agents can happen through direct communication with messages and proprietary languages, but also through a special standard Agent Communication Language (ACL) like FIPA ACL, KQML (Knowledge Query and Manipulation Language) or KIF. The usage of a standard agent communication language makes of course only sense if there is a standard middleware or environment for agents, which is not the case at the moment. FIPA ACL and KQML rely on speech act theory developed by Searle 1960 and define a set of performatives and their meaning. FIPA ACL defines a set of four primitive communicative acts: Inform (a proposition), Request (an action), Confirm and Disconfirm (involve uncertain beliefs), and approximately 18 composite communicative act types. The syntax in both languages, FIPA ACL and KQML is based in LISP. An example for FIPA ACL is, see [1]

(inform                                   (request
   :sender agent1                            :sender i
   :receiver hpl-auction-server              :receiver j
   :content                                  :content "buy microsoft stocks immediately"
       (price (bid good02) 150)              :language human)
   :in-reply-to round04         
   :reply-with bid04
   :language sl
   :ontology hpl-auction) 

The first element of a FIPA ACL message is the communicative act which defines the message type (request, refuse, agree, inform,..) while the rest is a sequence of message parameters. "Inform" and "Request" are the two basic performatives in FIPA ACL.

Communication can occur through multiple ways in complex multi-modal environments. It can for example happen through indirect communication by changing the environment. This is the principle used in stigmergy and many ant-based systems, which use or model biochemical substances and evaporating scents like pheromones.

Middleware and Environment

The environment is an essential component in any Multiagent System (MAS). It is a basic part of the perceive-reason-act cycle for agents, or simply "the world" and the "landscape" in which the agents live, act, and interact with each other. Russell and Norvig say in their AI book that "an agent is anything that can be viewed as perceiving its environment through sensors and acting upon the environment through effectors".

Almost no commonly used, multi-purpose computing environment offers direct support for MAS. Therefore, some framework or middleware is required to support the execution of the software agents of a MAS. This middleware may be provided by some tool library which cares for creating and managing agents and their interactions. Because of the importance of the infrastructural support, this infrastructure is sometimes also called a MAS.

The most important property of a MAS is to provide an environment for entities to act as autonomous agents. An optimal environment for adaptive agents is of course very complex. Environments are essential elements of MAS. They are much more than a message transport system. They can store gradient fields, pheromone traces and evaporating marks that guide agents to certain places, they can support the collaboration of agents through constraints, they provide complex information for learning and they determine the fitness in all evolutionary systems (see Danny Wenys et al., Environments for MAS, Springer LNAI 3374, 2005).

Each agent in a MAS has only incomplete local information, which results in decentralized or distributed control, high complexity, asynchronous computation and communication, and dynamic behavior to some extend. Wooldridge and Jennings recently suggested that typical properties of MAS are emergence and self-organization. This is certainly still not affirmative for all current MAS implementations. If the environment for example does not support any form of pheromone, a process like stigmergy (the basic instrument for many forms of Swarm Intelligence) is hardly possible. However, continuing this notion, MAS are the best or probably only candidate to experience, simulate and study these phenomena.

What functions do environments have in MASs ? According to Danny Weyns et al., Environments for MAS, Springer LNAI 3374, 2005,

  • they "structure" MASs through spatial organization
  • they "organize" perception, interaction and communication (only agents within a certain distance can communicate and interact with each other, i.e. the environment determines the range of communication: short-range vs. long-range)
  • they offer basic message transport and transmission systems
  • they can be a shared memory for agents
  • they store the "state" of the system
  • they determine the "context" of agents
  • they are a medium for indirect interaction and coordination (classical blackboard communication, stigmergy, storage for pheromones, gradient fields and evaporating marks which guide agents in their local context,..)

What forms of environments exist ?

  • discrete or continuous environments
  • spatial or geographic environments
  • "simulated environments" (simulated worlds) vs. "simulation environments" (frameworks, middleware,..)

Organization

Many AOSE methodologies use abstractions and concepts from the social sciences related to organizations and organizational patterns or structures: for a single agent terms like role, position, responsibility or permission, for a group of agents social terms like organization, law or norm. This is no accident, because agent-oriented systems resemble in fact natural societies, whereas traditional object-oriented systems are more like physical machines. If the Multi-Agent System as a whole should have a purpose, fulfil a particular function or solve a certain task or problem, it needs a kind of organization. This organization can be a kind of self-organization, Peer-to-Peer architecture, hierarchical structure, or dynamic role based approach. The organizations of the total system corresponds roughly to the architecture of each individual agent, although it can have certainly a more or less rigid structure.

Applications

MAS are often studied for their own sake, because they are fascinating subjects and more or less easy to create with traditional object-oriented programming languages. The obvious drawback in this case is that you don't know what your agents are good for, and you tend to create your own problems. After you have created your own agent system, it is easy to stay busy with security and communication mechanisms, visual editors to edit plans, behaviors and states of agents,... In the end you only revolve around yourself and start to wonder if the agent system has a real function or purpose at all. Contrary to object-oriented systems, which are usually constructed in order to fulfil a certain function, a Multi-Agent System does not need to have a real function or purpose. Of course if it is constructed well it can be used for a purpose. There are mainly three different application types: distributed software applications, simulation of complex systems, and exploration of virtual environents.

Software Applications

Wether agents can be used to build useful or even revolutionary software is still controversial and subject to debates in the field of AOSE. As Wooldridge says in his MAS book (2002), software applications working with agents can be divided into two main groups:

  • Distributed Systems: agents are embedded in a distributed system
  • Personal Software assistants: individual agents play the role of proactive assistants to users

Agents can be used in principle for workflow and business process management, for information retrieval and management, and for electronic commerce (for example auctions). In practice the Internet is a hostile environment for mobile and intelligent agents, which makes it difficult to find useful applications. Mobile agents are not allowed to move to arbitrary computers or to cross organizational boundaries, and intelligent agents can not understand ordinary websites (except a very small machine readable part in form of the semantic web).

Simulation

MAS can be used to simulate many natural and social systems, and complex systems in general. They can store gradient fields, pheromone traces and evaporating marks that guide agents to certain places, they can support the collaboration of agents through constraints, they provide complex information for learning and they determine the fitness in all evolutionary systems (see Danny Weyns et al., Environments for MAS, Springer LNAI 3374, 2005). The simulation of social systems is especially interesting because many abstract social concepts become concrete, observable and measurable phenomena in MASs. They concern the types of social relationships and interaction patterns.

Exploration

According to MIT researcher Pattie Maes "the autonomous agent approach is appropriate for the class of problems that require a system to autonomously fulfill several goals in a dynamic, unpredictable environment" [Maes (1994)]. MAS are useful for the

  • exploration of virtual worlds with mobile agents
  • exploration of real worlds with mobile robots

Since the number of complex virtual worlds is limited up to date, and there is no standard agent middleware or agent-friendly environment in the Internet, they are used mainly for simulation purposes, especially for the simulation of complex systems. An important application in the real world is the development of exploration and control techniques for mobile robots and distributed vehicles.

Challenges

Advantages and Disadvantages

The list of advantages and positive properties usually attributed to MAS is quite impressive:

  • robustness, fault-tolerance
  • scalability, concurrency
  • adaptability, flexibility

Yet they seem to have a price. There are also a lot of disadvantages and drawbacks, compared to traditional software systems:

  • limited predictability, understandability and control
  • accident- and error-prone system
  • restricted reliability for computational purposes

Although a MAS is reliable in the SPOF sense that there is no single or central point of failure, because the processing is distributed among many elements, it is only reliable in a collective sense. The entire system will not fail if a component in the system fails. This means the individual agent does not matter. A single agent is certainly not a reliable service provider (since he is an autonomous element, anyway, which has the right to determine the own reaction and responses), and not suitable for computational purposes.

Problems

Among the many important problems and challenges are for instance the following items:

  • Micro-Macro Link from local to global behavior
  • to solve the central problems of AOSE and ESOA
  • distributed problem solving, task allocation and distribution of tasks
  • architectures for intelligent agents, modeling of smart behavior
  • optimal forms of organization and cooperation
  • coordination and collaboration

Katia P. Sycara lists six challenges of multiagent systems in her AI Magazine article about "Multiagent systems" (1998):

  1. DISTRIBUTED COMPUTATION: how do we formulate, describe, decompose, and allocate problems and synthesize results among a group of intelligent agents?
  2. COMMUNICATION & COORDINATION: how do we enable agents to communicate and interact? What communication languages and protocols do we use? How can heterogeneous agents interoperate? What and when can they communicate? How can we find useful agents in an open environment?
  3. COHERENCE & COOPERATION: how do we ensure that agents act coherently in making decisions or taking action, accommodating the nonlocal effects of local decisions and avoiding harmful interactions? How do we ensure the MAS does not become resource bounded? How do we avoid unstable system behavior?
  4. REPRESENTATION & REASONING: how do we enable individual agents to represent and reason about the actions, plans, and knowledge of other agents to coordinate with them; how do we reason about the state of their coordinated process (for example, initiation and completion)?
  5. CONFLICT RESOLUTION: how do we recognize and reconcile disparate viewpoints and conflicting intentions among a collection of agents trying to coordinate their actions?
  6. ENGINEERING & DESIGN: how do we engineer and constrain practical DAI systems? How do we design technology platforms and development methodologies for MASs?

References and Articles

General:

BDI Architecture:

Languages:

Challenges:

more MAS articles about Agents, Architecture and Multi-agentSystems can be found at CiteSeer.

The Papers from the AAMAS 2003, AAMAS 2004 and the AAMAS 2005 conferences. Other years and versions of the International Conference on Autonomous Agents can be found here

Books

  • Jacques Ferber, Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence, Addison-Wesley, 1999, ISBN 0201360489
  • Gerhard Weiss (Editor), Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, The MIT Press, 2000, ISBN 0262731312
  • Michael Wooldridge, Introduction to MultiAgent Systems, John Wiley & Sons, 2002, ISBN 047149691X
  • Danny Weyns et al., Environments for Multi-Agent Systems, Proceedings of First International Workshop, E4MAS 2004, Springer LNAI 3374 (2005) ISBN 3540245758

Links

Portals:

See also

Personal tools