Design and Analysis Methods for
Multi-Agent Systems
California State University , Los Angeles
Dr. Jiang Guo
Fall 2010
Presented by :
Behin Behdinian
Sanaz Bonakdar
Kate Dehbashi
Monali Bhavsar
Amee Joshi
Background of Multi Agent System
Multi Agent System
Current Projects and Future Works
AOSE Methodologies:
 Gaia
Agent UML
 Available Tools
 VAStudio
 Mdeployer
 Technical Issues on MAS
 Development process of MAS
 key issues where the current state-of-the-art is lacking
 Agent oriented methodologies weaknesses
 The lack of attraction for methodology user to use the agent-oriented
 The lack of attraction for methodology user to use
existing agent-oriented methodologies
 Solutions
 Solutions of three key issues where the current state-of-the-art is lacking
 Agent oriented methodologies Solutions
 Solution to agent-oriented paradigm
 Solution to existing agent-oriented methodologies
Agent OPEN method
Feature-based method
 A multi-agent system (MAS) is a system
composed of multiple interacting intelligent
 Multi-agent systems can be used to solve
problems which are difficult or impossible for an
individual agent or monolithic system to solve.
 The idea of agent-based modeling was
developed as a relatively simple concept in the
late 1940s.
 Since it requires computation-intensive
procedures, it did not become widespread until
the 1990s
 Von Neumann machine
 Cellular Automata
 Game of Life
 Thomas Schelling’s segregation model(1971)
 Prisoner’s Dilemma (early 1980)
 Flocking models (late 1980)
 John Holland & John H. Miller (1991)
 StarLogo (1990)
 SWARM and Netlogo (mid 1990)
 Repast (2000)
 Samuelson(2000, 2005)
 Bonabeau(2002)
 Samuelson and Macal(2006)
The study of multi-agent
Agent-oriented software engineering
Beliefs, Desires, and Intentions (BDI)
Cooperation and Coordination
Distribution problem solving
Multi-agent learning
Scientific communities
Dependability and fault-tolerance
What is an Agent
an agent is a computer system capable of
autonomous action in some environment, in
order to achieve its delegated goals.
Agent characteristic in a multiagent system
 Autonomy: the agents are at least partially
 Local views: no agent has a full global view of
the system
 Decentralization: there is no designated
controlling agent
Type of Agent
 1956–present: Symbolic Reasoning Agents
Its purest expression, proposes that agents use
explicit logical reasoning in order to decide what to
 1985–present: Reactive Agents
Problems with symbolic reasoning led to a reaction
against this — led to the reactive agents
 1990-present: Hybrid Agents
Hybrid architectures attempt to combine the best of
symbolic and reactive architectures.
Simple reflex agent
Learning agent
Multi-agent systems
 Typically multi-agent research refers to software
 However, the agents in a multi-agent system
could be
 robots
 humans
 human teams
 combined human-agent teams.
Overview Multi-agent
 Multi-agent systems can manifest self-
organization and complex behaviors even when
the individual strategies of all their agents are
 Agents can share knowledge using any agreed
language, within the constraints of the system's
communication protocol.
 Knowledge Query Manipulation Language (KQML)
 FIPA’s Agent Communication Language (ACL).
MAS Properties
 MAS is "self-organized systems” and tend to find
the best solution for their problems "without
 Physical phenomena, such as energy minimizing,
where physical objects tend to reach the lowest
energy possible, within the physical constrained
MAS Main feature
 Flexibility
multi-agent system can be
 Added to,
 Modified
 Reconstructed
 Do not need to rewrite
detailed of the
 These systems also tend
to be rapidly
 Self-recovering
 Failure proof
 Self managed features
Applications of Multi-Agent
aircraft maintenance
electronic book buying coalitions
military demining
wireless collaboration and communications
military logistics planning
supply-chain management
joint mission planning
financial portolio management
Advantages of a Multi-Agent
 MAS distributes computational resources and
capabilities across a network of interconnected
agents. Whereas a centralized system may be
plagued by resource limitations, performance
bottlenecks, or critical failures
 MAS is decentralized and thus does not suffer
from the "single point of failure" problem
associated with centralized systems.
Advantages of a Multi-Agent
 MAS efficiently retrieves, filters, and globally
coordinates information from sources that are
spatially distributed.
 MAS provides solutions in situations where
expertise is spatially and temporally distributed.
 MAS enhances overall system performance,
specifically along the dimensions of computational
efficiency, reliability, extensibility, robustness,
maintainability, responsiveness, flexibility, and
Current Projects & Future Works
 AOSE: Agent Oriented Software Engineering
 AOSE Methodologies:
 Gaia: The Gaia Methodology for Agent-Oriented Analysis and
 AAII: Formal models and decision procedures for multi-agent
 Agent UML: A formalism for specifying multi-agent software
 DPMAS: A Design Method for Multi-agent System using Agent UML
AOSE: Agent Oriented Software
 The agent-oriented (AO) :the ability to construct flexible systems
with complex behavior by combining highly modular
 Agent-oriented development toolkits mostly use in industry
 Agent-orientation is a paradigm for analysis, design and system
 AOSE is a new field, methodologies far less established than
object-oriented software engineering methods
 AOSE Methodologies:
 Gaia
Knowledge Level
 Agent-oriented modeling borrows from the study of
human organizations and societies in describing the way
in which agents in a Multi-Agent System work together
 And from artificial intelligence (AI) to describe the agents
 These additional concepts can be defined in terms of
object-oriented ones which deal with ideas and structures
at a higher level:” the knowledge level”
 Knowledge Level Categories :
 ConcreteEntity, Activity, and MentalStateEntity.
Concrete Entity Types
 Agent: An atomic autonomous entity that is capable of
performing some useful function.
 Organization: An Organization is a group of Agents
working together to a common purpose.
 Role: A Role describes the external characteristics of an
 Resource: Resource is used to represent non-autonomous
entities such as databases or external programs
Activity Types
 Task: A Task is a knowledge-level unit of activity with a
single prime performer
 Interaction Protocol: Defines a pattern of Message
exchange associated with an Interaction
Mental State Entity Type
 Goal: A Goal associates an Agent with a Situation.
 Two other simple but important concepts used in
AOSE using MESSAGE/UML are: Information Entity and
 A Message is an object communicated between Agents
 Information Entity is a content of the Message
Figure 1 gives an informal agent-centric overview of
how these concepts are interrelated, showing their
relationship to the agent concept
AOSE Methodologies
AOSE: Methodologies
 Analysis and Design methodologies
 Set of model and guidelines that aid in
understanding the system
 Two approaches:
 Adoption & Extensions of OO approach
 Adoption of other techniques
 Gaia
 Inspired by OO concepts
 Also provides agent-specific set of concepts
 Concepts
 Abstract: used during conceptualization
 Roles, Permissions, responsibilities,…
 Concrete: direct counterparts in implementation
 Agent types, Services,…
 Analyst moves from abstract to concrete
 Agent-based system: artificial society
Gaia: Abstract Concepts
Gaia: Analysis
 Role Schema
 Identifies key roles in the system
 Interaction model
 Represents links between roles
 Set of protocol definitions consisting of
 Purpose
 Initiator
 Responder
 Inputs/outputs
 processing
Gaia: Role Schema
Gaia: Role Schema example
Gaia Interaction model example
Gaia: Design
 Create an agent model
 Documents variant agent types and instances of
each agent
 Aggregates roles into agent types
 Develop a service model
 Specifies functions of an agent
 Develop an acquaintance model
 Document lines of communication between the
 Purpose: identify communication bottlenecks
 Nodes: agents
 Arrows: communication pathway
Gaia: acquaintance model
Gaia Usage
 Appropriate for large-scale real-world
applications in which
 Agents are coarse-grained computational systems
 Agents are heterogeneous
 System organization structure is static
 Ability of agents and services are static
 System contains small number of agent types
 Extension of OO methods based on experience
of Australian AI institute with BDI-like systems
 Example: air-traffic management system
 Internal models: internal detail of agents
 Agents have mental attitudes:
 beliefs (informative)
 desire (Objective to be accomplished)
 intention (deliberative component)
 External models
 Concerns with interactions not internals of agents
AAII: Analysis and Design
 Identify roles and develop agent class hierarchy
 Identify responsibilities, services and goals
 Determine plans that can be used to achieve
each goal
 Determine information requirements necessary
to represent and process plans and turn them
into appropriate belief structure for the agents
AAII: Decision Tree
 AAII uses decision tree to model the behavior of
the system
 Choice nodes
 Chance nodes
Agent UML
Agent UML: Why Created?
 At the beginning, AOSE was not completely
accepted in the industry
 FIPA and OMG cooperated to increase the
acceptance of AOSE in industry (1999-2000). How?
 Relating to OO software development standard
 Supporting the development environment for the
software lifecycle
 First result of the cooperation
 Agent UML
Agent UML : What is it?
 An extension to the UML
 Agent: Active Object that can say “go” and “no”
 More sophisticated capabilities:
 Mobility
 Reasoning about knowledge
 Promotes standard representations of UML to support
agent software
 Example: Protocol diagrams
 “Protocol diagrams” To show multi agent
Agent UML: Protocol Diagram
 UML extension for the specification of “Agent
Interaction Protocol”
 Describes a communication pattern, with
 Allowed sequence of messages between
 Constraints on the content of the message
 Example: Ticket market
 Uses FIPA English-Auction Protocol
Protocol Diagrams: Elements
 Agents/Roles:
 Lifeline/Interactions
 May split up to show decisions
Protocol Diagrams: Elements (Cont.)
 Nested/Interleaved Protocols
Protocol Diagrams: Elements (Cont.)
 Asynchronous /Synchronous / Mobile messages
 Massage Label
 Communicative Act
 Arguments for additional information
DPMAS: A Design Method for
Multi-agent System using Agent UML
 DPMAS uses agent UML, an extension of the UML in Object Oriented
domain, as its modeling language
 DPMAS tells designers how to design a multi-agent system step by step,
specially using agent unique concepts
 It provides a group of graphs to help designers in modeling multi-agent
 DPMAS suggests a design process that covers requirement
specification, task specification, agent specification and deployment
 DPMAS is a design method closer to real software development.
 A tool called AUMP has been developed to aid designers in drawing
graphs used in DPMAS
 AUMP is the design platform of the well known MAGE agent
DPMAS Concepts
 An agent is an instance of an agent class.
 Agent class is the software implementation of an autonomy entity
and the basic unit of source codes organization.
 An agent achieves its goal through decision, action and interaction.
 An agent goal is relevant to a system task.
 A task is an item of work that users may require the system to do.
Usually, a task is performed by a sequence of actions.
 A task needs the cooperation of several roles.
 Each role can be played by an agent. An agent can play multiple
roles because it can participate in multiple tasks and play different
roles in different tasks.
DPMAS Process
 Domain description: describes the system functions using Uses case graph.
 Agent finding: determines how many agents the system need, what types
they are, and the interactive relationships between them.
 Task specification: describes how the system functions are fulfilled.
 Activity task :
needs more actions than interaction
activity graph is used to describe the actions firstly, and then protocol graph may be
used to describe the interactions between involved roles
Interaction task :
needs more interactions than actions
Interaction graph is used to describe protocol firstly and followed with activity graph.
 Ontology specification: defines the knowledge representation in the system.
The knowledge representation is used when an agent needs to make decisions and
explain the messages of other agents.
DPMAS Process
 Agent specification: gives the detail definition of every agent
 Code generation: is performed automatically
 Deployment: shows the runtime configuration of the system using
deployment graph, including the physical position, the possible
clone and move of every agent.
DPMAS Process Figure
Future Works
 Future works will be focused on model reuse and code
 A model template library and a code template library
are under development.
 With these libraries, designers will be able to select an
existing model template if it suits the functional
requirement well.
 This will save a lot of design time , many models don’t
need be design from very beginning
Available Tools
Multi-Agent Platforms
 AgentBuilder is an integrated tool suite for constructing
intelligent software agents
 Jack is an environment for building, running and
integrating commercial JAVA-based multi-agent systems
using a component-based approach
 Zeus is an integrated environment for the rapid building of
collaborative agents applications
 MAGE ( Multi-AGent Environment ) is an agent oriented
programming environment
MAGE: An Agent-Oriented Software
Engineering Environment
 It provides complete tools to support agent-oriented
requirement analysis, design, development and
 The idea is to create a relatively general purpose and
customizable toolkit that could be used by software users
Modeling tool AUMP
 Step1: Use Case Model to describe system functions
 Step 2: behavior modeling which is used to resolve how
to achieve the Use Cases .There are six types of agent
behavior model :
 Activity Model, State Chart Model, Interaction Protocol
Model, Plan Model, Inference Model and Reactive Rule
 Step 3: agent modeling which is used to demonstrate the
agent system structure
 Step 4: system deployment modeling: describes how
agents are distributed and how the system runs
AUMP : A DPMAS Tools Support
Development tool VAStudio
 A visual and integrated development environment for
developing MAS
 Agent-based programming environment
 Friendly and easy-to-use interface
 It directly loads the result of design process of AUMP and
generate the corresponding agent or MAS
 It provides plenty of agent templates
 It provides plenty of behavior components which can be
used to buildup agents.
Deployment tool MDeployer
 It provides powerful functions for users to use:
Start New Agent, Kill Agent, Send Message
 It provides a tool through which users can deploy and
manage the whole system through web
Future Works
 MAGE is a powerful development environment for
autonomous computing
 Future works will be focused on autonomic computing
and agent-based grid
Application : e-Business
Technical Issues on Multi Agent
Development process of MAS
We consider the state-of-the-art development process
to be as follows:
 Designing organization and individual agents using
an AOSE methodology
 Taking the resulting design and (manually) coding the
agents in some AOPL, based on the design
 Debugging the system using message tracing and
agent inspectors
 Possibly using model checking on agent code
Key Issues
There are three key issues where the current state-of-the-art is lacking, :
 The implementation is developed completely manually from the
 This creates the possibility for the design and implementation to
diverge, which tends to make the design less useful for further
work in maintenance and comprehension of the system.
 Code and design are completely different beasts.
 Current state-of-art is lacking in linking design and code.
 So, we need to remove inconsistencies between design and
code. i.e. eliminate the ‘gap’ between them.
 Integrating code and design we need the common language.
And for that we need the many AOPL’s. Having to develop link
between each possible design tool and each possible language,
need of single methodology and single AOPL.
 More practical approach is to standardize interchange formats
and API’s to remain diverse so it will require more efforts and
collaboration within the AOSE and ProMAS communities.
 Although present AOPLs provide powerful features for
specifying the internals of a single agent, they mostly only
provide messages as the mechanism for agent interaction.
AOPLs are weak in allowing the developer to model the
environment within which the agents will execute.
 AOPL’s focus on internals of agents but neglect the social
and organizational aspects.
 Reason for neglecting these issues is the lack of clear and
computational semantics.
 Work on those areas does not focus on designing agent
programming languages.
 Current implementation of AOPLs at message level gives
‘brittle’ interactions also, designing and implementing at
this level makes it very hard to verify /debug & modify
interaction between agents.
 In most of the practical approaches for verification of multi-
agent systems, verification is done on code. More work is
required in verification of agent design artifacts.
 As verification & validation done on code, MAS are hard to
debug also be difficult to detect or produce the exact
circumstances that cause problem.
 Large number of agents makes things more difficult to
consider the consequences of changes for participating
agents. Because each agent has complex structure which
not only inspected but need to be understood. So typically
a large number of messages analyzed in conjunction with
 In fact, all the work on model checking for multi-agent
systems is still in early stages so not really suitable for use on
large and realistic systems.
Agent oriented methodologies
 Agent-oriented methodologies weaknesses can
be considered in two different aspects:
 The lack of attraction for methodology user to use
the agent-oriented paradigm
 The lack of attraction for methodology user to use
existing agent-oriented methodologies
The lack of attraction for methodology user to use
the agent-oriented paradigm
 Lack of agent-oriented programming languages:
 Although programming languages are only part of
the development story, industry is reticent to adopt a
new paradigm at the conceptual level if it is
impossible to implement these ideas in a currently
acceptable, commercially viable programming
 Lack of explicit statement of agent-orientation
 The benefits of agent technology must be declared
by introducing the cases where AOSE paradigm
succeeds and other existing paradigms fail
 Relative difficulty of learning concept related to agent
oriented paradigm (AI):
 As an example the usage of Gaia agent-oriented
methodology requires learning logic, which decreases
the adoption of this methodology, since usually
methodology users are not familiar with logic and do not
tend to learn it.
 High cost of AO acquisition:
 The acquisition of this paradigm by software
development organizations requires a high cost for
training the development team.
The lack of attraction for methodology user to use
existing agent-oriented methodologies
 Relative immaturity:
 The AO paradigm immaturity, which is a relative matter
compared to other paradigms, is clearly because of it
 Marketing of multiple AO methodologies:
 As long as the availability and marketing of multiple
agent-oriented methodologies are in competitive
manner, this feature is an obstacle to their widespread
industrial adoption, since it leads to confusion of
methodology users
 Lack of confrontation with wrong expectation of one
size- fits-all methodology:
 No unique specific methodology can be general
enough to be useful to every project without some level
of personalization.
 Users usually think a unique methodology has general
usage and ignore the fact that each methodology is
designed for some specific goals . Thus when a specific
methodology does not fit their requirements and leads
to project failure they conceive the problem from the
side of methodology whereas the problem is with the
wrong methodology selection . Agent-oriented
paradigm should support its user with the awareness and
facilities to find the proper methodology for his project
from existing methodologies or to change the existing
instances in order to fit the project.
 Lack of confrontation with user willingness to
setup an owned project-specific methodology:
 The high number of existing AO methodologies
can be seen as a proof that methodology users,
often prefer to setup an owned methodology
specially tailored for their needs instead of reusing
existing ones. AO paradigm should support its user
with the awareness and facilities to avoid setting
up his methodology from the scratch, but to
change the existing instances in order to fit the
Solutions of Technical issues
on Multi Agent Systems
Solutions of three key issues
where the current state-of-theart is lacking
 Working on developing techniques and tools that
allow for designs and code to be strongly
integrated with consistency checking and
change propagation.
 Developing better integrated designs and code
would be facilitated by AOPLs being closer to the
design in terms of covered concepts.
 Develop
better techniques
debugging and verification.
Agent oriented
methodologies Solutions
 Agent-oriented methodologies solutions can be
considered in two different aspects:
 Solution to agent-oriented paradigm
 Solution to existing agent-oriented methodologies
Solution to agent-oriented
 Software development organizations use an evaluation
framework for agent-oriented methodologies.
 This approach would:
(i) help to improve existing methodologies by identifying their
(ii) make the availability of multiple methodologies an advantage
(having wide range of method fragment options),
(iii) do away with the wrong expectation on one-size-fits-all
methodology, and
(iv) answer to user willingness to setup an owned project-specific
In CMM organizational maturity
framework 5 maturity levels are
Solution to existing agentoriented methodologies
 Agent OPEN method:
which stands for
Environment and Notation.
 OPEN Process Framework (OPF) consists of:
(i) a process metamodel of framework from which can be
generated an organizationally specific process
(ii) a repository and
(iii) a set of construction guidelines.
 The major elements in OPF metamodel are Work Units
(Activities, Tasks and Techniques), Work Products, Producers
and two auxiliary ones (Stages and Languages)
 Feature-based method:
 proposed a modular approach enabling developers to
build customized project-specific methodologies from AOSE
 Differing from Agent OPEN approach, this method does not
regard it necessary to rely on the formal metamodel of
method fragments.
 This method identifies and standardizes the common
elements of the existing methodologies.
 The common elements could form a generic agent
model on which specialized features might be based.
 The remaining parts of the methodologies would
represent added-value that the methodologies bring
to the common elements, and should be
componentized into modular features.
 The small granularity of features allows them to be
combined into the common models in a flexible
manner. By conforming to the generic agent model in
the common elements, it is expected that the
semantics of the optional features remain consistent.
Zhikun ZHAO, Yinglei XU , "DPMAS: A Design Method for Multi-agent System using
Agent UML", 2010 Third International Conference on Information and Computing
Bernhard Bauer, J¨org P. M¨uller, and James Odell, “Agent UML: A formalism for
specifying multi agent software systems”, In P. Ciancarini and M. Wooldridge, editors,
Agent-Oriented Software Engineering — Proceedings of the First International
Workshop(AOSE-2000). Springer-Verlag: Berlin, Germany, 2000.
Giovanni Caire et al, “Agent Oriented Analysis using MESSAGE/UML”, Second
International Workshop, AOSE 2001,Montreal, Canada, May 29, 2001.
Carole Bernon, Massimo Cossentino, Juan Pavón “An Overview of Current Trends in
European AOSE Research” June 31, 2005
Wei Huang , Elia El-Darzi and Li JinSchool of Computer Science, University of
Westminster Watford Road, London HA1 3TP, United Kingdom, “Extending the Gaia
Methodology forthe Design and Development of Agent-based Software Systems”
Wooldridge, M., Jennings, N.R., and Kinny, D, “The Gaia Methodology for AgentOriented Analysis and Design”, Journal of Autonomous Agents and Multi-Agent
Systems. 3,3 (2000), 285-312.
Zhongzhi Shi, Haijun Zhang, Yong Cheng, Yuncheng Jiang, QiujianSheng, Zhikung
Zhao, “MAGE: an agent-oriented software engineering environment”, Proceedings of
the Third IEEE International Conference on Cognitive Informatics, 2004, pp:250-257.
Rafael H. Bordini, Mehdi Dastani, and Michael Winikoff, Current Issues in Multi-Agent
Systems Development(Invited Paper).
O. Zohreh Akbari, A survey of agent-oriented software engineering paradigm:
Towards its industrial acceptance, January 13, 2010.

Design and Analysis Methods for Multi