A SO F T W A R E F R A M E W O R K F O R S IM U L A T IO N S T U D IE S O F
IN T E R A C T IO N M O D E L S IN A G E N T T E A M W O R K

by

O M ID A L E M I
B.Sc. C om puter (Software) Engineering
A rak University, Arak, Iran.

THESIS SUBM ITTED IN PARTIAL FULFILM ENT O F
TH E REQUIREM ENTS FO R TH E D EG R EE OF
M ASTER OF SCIENCE
IN
MATHEMATICAL, CO M PU TER , AND PHYSICAL SCIENCES
(C O M PU TER SCIENCE)

UNIVERSITY O F NORTHERN BRITISH COLUMBIA
2012

© Omid Alemi, 2012

1+1

Library and Archives
Canada

Bibliotheque et
Archives Canada

Published Heritage
Branch

Direction du
Patrimoine de I'edition

395 Wellington Street
Ottawa ON K1A0N4
Canada

395, rue Wellington
Ottawa ON K1A 0N4
Canada
Your file Votre reference
ISBN:

978-0-494-94103-4

Our file Notre reference
ISBN:

978-0-494-94103-4

NOTICE:

AVIS:

The author has granted a non­
exclusive license allowing Library and
Archives Canada to reproduce,
publish, archive, preserve, conserve,
communicate to the public by
telecommunication or on the Internet,
loan, distrbute and sell theses
worldwide, for commercial or non­
commercial purposes, in microform,
paper, electronic and/or any other
formats.

L'auteur a accorde une licence non exclusive
permettant a la Bibliotheque et Archives
Canada de reproduire, publier, archiver,
sauvegarder, conserver, transmettre au public
par telecommunication ou par I'lnternet, preter,
distribuer et vendre des theses partout dans le
monde, a des fins commerciales ou autres, sur
support microforme, papier, electronique et/ou
autres formats.

The author retains copyright
ownership and moral rights in this
thesis. Neither the thesis nor
substantial extracts from it may be
printed or otherwise reproduced
without the author's permission.

L'auteur conserve la propriete du droit d'auteur
et des droits moraux qui protege cette these. Ni
la these ni des extraits substantiels de celle-ci
ne doivent etre imprimes ou autrement
reproduits sans son autorisation.

In compliance with the Canadian
Privacy Act some supporting forms
may have been removed from this
thesis.

Conform em ent a la loi canadienne sur la
protection de la vie privee, quelques
formulaires secondaires ont ete enleves de
cette these.

W hile these forms may be included
in the document page count, their
removal does not represent any loss
of content from the thesis.

Bien que ces formulaires aient inclus dans
la pagination, il n'y aura aucun contenu
manquant.

Canada

A bstract
This thesis proposes a new software framework th a t facilitates the study of agent
interaction models in early development stages from a designer’s perspective. Its pur­
pose is to help reduce the design decision space through simulation experim ents th a t
provide early feedback on com parative performance of alternative solutions. This is
achieved through interactive concurrent sim ulation of m ultiple teams in a representa­
tive microworld context. The generic sim ulator’s architecture accommodates an open
class of different microworlds and perm its multiple communication mechanisms. It
also supports interoperability w ith other software tools, distributed sim ulation, and
various extensions. The framework was validated in the context of two different re­
search projects on helpful behavior in agent teams: the M utual Assistance Protocol,
based on rational criteria for help, and the Em pathic Help Model, based on a concept
of em pathy for artificial agents. T he results show th a t the framework m eets its design
objectives and provides the flexibility needed for research experimentation.

C ontents

A b stract

i

List o f F igures

v

A ck now ledgem en ts

v iii

1

In tro d u ctio n

1

2

B ackground and R ela ted W ork

8

2.1

M ultiagent S y ste m s .............................................................................................

8

2.2

Agent Interactions and Interaction P r o to c o ls ..............................................

9

2.3

Agent T e a m w o r k .....................................................................................................12

2.4

Engineering of Agent Interaction P r o to c o ls ......................................................14

2.5

3

2.4.1

Formal M eth o d s............................................................................................14

2.4.2

M ultiagent Languages and P la tf o r m s ................................................... 16

Simulation of Agent Interactions

.......................................................................17

A N e w Fram ework for S tu d ies o f A g en t In te ra ctio n M o d els

22

3.1

The Challenges in Studying Agent In tera ctio n s...............................................23

3.2

The Rationale for a New F r a m e w o r k ................................................................27

ii

4

3.3

The Design Principles

..........................................................................................31

3.4

The Approach in This Thesis

............................................................................ 33

T h e G eneric Sim u lator A rch itec tu re
4.1

4.2

35

The System R e q u ire m e n ts ................................................................................... 36
4.1.1

Functional R eq u irem en ts............................................................................36

4.1.2

Non-functional R e q u ir e m e n ts ................................................................. 44

4.1.3

Domain-specific R eq u ire m e n ts..................................................................45

The System Structure

..........................................................................................48

4.2.1

The Simulation E n g in e ...............................................................................49

4.2.2

Service Components

4.2.3

The Front E n d ............................................................................................ 53

.................................................................................. 51

4.2.4 The MAS M o d e ls ......................................................................................... 55
4.2.5
4.3

D istributed S im u la tio n ............................................................................... 68

The System B e h a v io r............................................................................................. 70
4.3.1

The Simulation E n g in e ............................................................................... 70

4.3.2 The Front E n d .............................................................................................74
4.3.3 The MAS M o d e ls ......................................................................................... 79
4.3.4 D istributed S im u la tio n ............................................................................... 80
4.4

5

Instantiation of the Generic Simulator

M o d elin g for S im u lation
5.1

............................................................ 83

85

Modeling of Interaction P r o to c o ls ....................................................................... 85
5.1.1 Representing P r o to c o ls ............................................................................... 86
5.1.2 M ulti-Protocol Interaction M o d els.............................................................87

5.2

A Model of a M ultiagent System
5.2.1 Environment

...................................................................... 88

................................................................................................ 88

iii

5.3

5.4

5.2.2

T a s k .............................................................................................................. 89

5.2.3

R e s o u r c e s .....................................................................................................90

5.2.4

Agent T e a m ................................................................................................. 90

Example: The M utual Assistance Protocol (M A P )..........................................91
5.3.1

The Microworld C o n fig u ratio n ................................................................ 91

5.3.2

Modeling P r o to c o ls ....................................................................................95

Example: The Em pathic Help M o d e l ................................................................. 97
5.4.1

6

The Microworld C o n fig u ratio n ................................................................98

T h e S im u lation P ro cess
6.1

6.2

100

Example: The M utual Assistance Protocol ( M A P )........................................101
6.1.1

The Experim ent S e t u p ........................................................................... 101

6.1.2

The Im pact of C om putation and Communication C o s t s ............... 102

6.1.3

The Im pact of M utual Awareness and Disturbance

...................... 103

Example: The Em pathic Help M o d e l ............................................................... 105
6.2.1

Optimizing the Performance of th e Em pathic M odel...................... 106

6.2.2

The Experiment S e t u p ........................................................................... 109

6.2.3

The Validation of Em pathy as a Help T r i g g e r ................................110

6.2.4

A Comparison of Em pathic and R ational H e l p ................................I l l

7

A n alysis and E valu ation

113

8

C onclu sion s and F u tu re W ork

121

B ib liograp h y

126

IV

List o f F igures

3.1

Building customized simulators using th e fram ew o rk ......................................33

4.1 The use case diagram of the sim ulator as a stand-alone s y s te m ...................37
4.2 Simulator as a client of an external s y s t e m ....................................................... 39
4.3 Simulator as a server of an external s y s te m ....................................................... 40
4.4 Simulator in a bilateral client-server relation w ith an external system

. 42

4.5

The high-level structure of the simulator and its external relations . . .

48

4.6

The simulation engine

4.7

The Front-end c o m p o n e n t.....................................................................................53

4.8

The interoperability of th e sim ulator w ith external systems through its

........................................................................................... 50

front e n d ...................................................................................................................... 55
4.9

A MAS model within th e s im u la to r .................................................................... 56

4.10 The agent architecture of th e s im u la to r ............................................................. 57
4.11 Using an adaptor to connect to external reasoning e n g i n e s .........................59
4.12 The message s t r u c t u r e ........................................................................................... 61
4.13 The architecture of a blackboard for the s im u la to r.........................................62
4.14 The structure of m ic ro w o rld ................................................................................. 64
4.15 The board architecture for parallel MAS models, each representing a
different t e a m ............................................................................................................ 66

v

4.16 Parallel MAS models using a grid-based e n v iro n m e n t.................................. 68
4.17 Multiple MAS models and the shared m ic r o w o r ld ......................................... 69
4.18 The distributed simulation a rc h ite c tu re ............................................................. 69
4.19 The mechanics of the e x p e r i m e n t....................................................................... 71
4.20 The mechanics of the run

....................................................................................72

4.21 The mechanics of the m a t c h ................................................................................ 73
4.22 The mechanics of the round w ith message passing c y c l e s ..............................74
4.23 How agents are handled in different stages of each r o u n d .............................. 75
4.24 The main window of the sim ulator’s G U I .......................................................... 76
4.25 The control to o lb o x .................................................................................................. 76
4.26 The console to o lb o x .................................................................................................. 77
4.27 A chart created in the visualization toolbox

................................................... 77

4.28 The param eter editor in th e experiment setup to o lb o x .................................. 78
4.29 Handling multiple MAS models in parallel in each match............................... 80
4.30 The three steps of distributed sim ulation.............................................................82
5.1

The alternating sending (S) and receiving (R) states of an A IP ’s FSM . 86

5.2

The augmented FSM th a t combines several AIPs

5.3

The board of the g a m e ............................................................................................88

5.4

The Action M A P ..................................................................................................... 95

5.5

The FSM model of Action M A P ...........................................................................96

5.6

Example: P art of state definitions for the Action MAP FSM........................ 97

5.7

Modeling agent’s experience carried over multiple g a m e s ............................ 98

6.1

Team scores vs com putation and communication (unicast) costs

6.2

Team scores vs m utual awareness and environm ental disturbance . . . . 104

6.3

Interfacing the sim ulator w ith MATLAB’s Global Optim ization (GO)

......................................... 87

. . . . 102

to o lb o x ........................................................................................................................107

6.4

The genetic algorithm optim ization of four em pathic parameters pro­
duced by M A T L A B ................................................................................................ 109

6.5

The performance of em pathic team versus ra n d o m -h e lp ............................. 110

6.6

The performance of em pathic team versus Action M A P ............................. 112

7.1

The duration of the distributed simulation for 24000 runs, based on the
size of the c l u s t e r ................................................................................................... 118

7.2

The speed-up of the distributed sim ulator for an experiment w ith 24,000
runs.............................................................................................................................. 119

vii

A ck n ow ledgem ents
Above all, I would like to sincerely express my gratitude to my supervisor, Dr. Jernej
Polajnar for his support during my study. This thesis would not have been possible
w ithout his experience, knowledge, advice, and patience.
I am thankful to my committee member, Dr. Desanka Polajnar for her invaluable
advice on my thesis from a software engineering perspective.
Special thanks to Dr. M atthew Reid for his interest and time in serving in my
supervisory committee.
I would like to thank my colleagues Narek Nalbandyan and Behrooz Dalvandi for
their input and feedback on using th e software developed as a part of this research.

C hapter 1

In trod u ction

One of the m ost im portant characteristics of the m ultiagent paradigm is th e ability of
agents to autonomously and intelligently interact w ith each other. Interactions enable
agents to coordinate their activities, cooperate, collaborate in teams, and negotiate in
a social environment. According to Wooldridge [2009], many researchers believe th a t,
in the future, com putation should be understood mainly as “a process of interactions” .
W ith the increasing dominance of networks and distributed systems, th e focus of agent
studies has shifted from single agents towards their social abilities and organizational
structures, bringing agent interaction models into the forefront of agent research.
The development of agent interaction models is a challenging area in m ultiagent
systems (MAS) research. The designer of an agent interaction model typically faces a
large number of decisions with many possible outcomes, whose impact upon th e system
properties and performance is often difficult to predict. Simulation experim ents have
been a key m ethod in the evaluation of possible designs since the earliest studies of
the agent interaction models (e.g., the C ontract Net Protocol introduced by Sm ith
1

[1980]). However, despite th e growing research interest in agent interactions, universal
simulation tools for such studies have not yet appeared.
In this thesis I propose a new software framework for building sim ulators th a t
facilitate the design of a particular class of agent interaction models. T he purpose
of such a simulator is to help the designer of an agent interaction model to study
the properties, and in particular the im pact upon overall system perform ance, of
the model in situations of practical interest. In general, an agent interaction model
denotes a specific p attern of interaction th a t agents use in order to achieve a certain
objective.
The prim ary application scope of the current framework version, as described
in this thesis, is the study of interaction models for helpful behavior in team w ork of
artificial agents. This topic is an active segment of th e MAS research scene. Teamwork
of artificial agents has become a m ainstream research area in MAS [Aldewereld et al.,
2004, Sycara and Sukthankar, 2006, Dunin-Keplicz and Verbrugge, 2011]. Following
the research on human teamwork (e.g., [Lepine et al., 2000]) which suggests th a t the
capability and willingness of team members to provide direct assistance to each other
are im portant factors of team success, there has been an increasing interest in the
study of helpful behavior in agent teamwork [Yen et al., 2004, Fan et al., 2005, K am ar
et al., 2009, Polajnar et al., 2011, 2012]. The current framework is a design tool th a t
is specifically tailored for agent interaction models for helpful behavior and facilitates
their design and development.
The framework supports interactive experim entation th a t allows th e user to in­
teract with the simulation model and dynamically change its properties, as well as
other param eters of the experiment. In order to make the interactive experim entation
efficient, the framework’s design includes mechanisms for early feedback th a t allow
2

the user to immediately access the results of an experim ent in progress and observe
how agents’ behavior reacts to th e dynam ic changes. These mechanisms help the
designer to eliminate the undesirable features of th e agent interaction models, as well
as unproductive experimental setups, in the early stages of th e experim entation cycle.
An essential feature of the framework th a t facilitates early feedback is th e con­
current simulation of multiple teams which employ different agent interaction models
th a t the designer wishes to compare. This feature enables the experimenter to ob­
serve the behavior and performance of m ultiple team s at th e same time. T he designer
can simulate multiple team s th a t use different agent interaction models b u t follow
the same experiment scenario in identical task and environment configurations. The
concurrency enables the designer to perform a com parative analysis during the sim­
ulation and draw conclusions as the experiment progresses. One can also sim ulate
multiple instances of the same agent interaction model with slight differences in order
to optimize the agent interaction model param eter settings. Another possibility is to
compare a team th a t employs an agent interaction model to address a specific problem
with teams th a t use substantially different mechanisms to address th e same problem
in identical circumstances.
The proposed framework uses a distributable architecture that allows th e simula­
tion to run on a network of com putation nodes. One of th e factors th a t increases the
com putational complexity of the sim ulation process is th a t each experiment requires
a large number of runs in order to provide statistically significant results. T he concur­
rent experimentation with multiple team s increases the com putational requirem ents
and the time needed to complete a simulation run. In order to overcome those limi­
tations, the framework can spread th e experiments over multiple com putation nodes
in order to generate the results faster.

3

Simulation of multiagent systems requires modeling of th e environment in which
agents are going to be situated in a way th a t is suitable for studying them . How­
ever, real-world problems have details th a t obscure the core elements th a t need to be
studied. The world model must be free of such details in order to efficiently support
simulation-based design-oriented comparisons between alternative agent interaction
models. An approach th a t has proven to be useful in many areas of artificial intelli­
gence is the construction of a suitable microworld, th a t only represents th e essential
elements of the problem and provides a highly simplified abstract model th a t serves
as a vehicle for studying it. Examples of successful microworlds include th e Blocks
World, used in research on planning in classical Al [Russell an d Norvig, 1995], and the
Colored Trails [Gal et al., 2010], used in the study of human-agent decision making.
In this thesis, we have developed a microworld th a t is inspired by Colored Trails but
is designed to represent th e concepts needed in the research of helpful behavior in
agent teamwork.
The current im plem entation of th e framework supports the study of agent in­
teraction protocols (AIPs) for collaboration among the members of th e same agent
team. In general, AIPs define th e legal sequences, and content types, of th e messages
th a t the agents are allowed to send and receive in prescribed scenarios [Paurobally
and Cunningham, 2002, Dunn-Davies et al., 2005]. AIPs can be standardized and
included in libraries th a t can be used in different MAS platforms. T here have been a
variety of AIPs developed such as th e C ontract Net Protocol, different auction proto­
cols (English Auction, Dutch Auction), and negotiation protocols [Wooldridge, 2009].
Agent interaction protocols rely on a shared message passing infrastructure which al­
lows them to send messages directly to each other. In this research, a message passing
mechanism is developed and validated in the framework.

4

The framework’s design strikes a balance between specialization and extendibility.
On the one hand, in order to keep this research w ithin the limits of a M aster’s the­
sis, its current version is restricted to mainly support th e study of agent interaction
protocols for helpful behavior in the context of team s consisting purely of artificial
agents. On the other hand, the framework has an open architecture th a t allows its
functionality and application areas to be extended in a num ber of different directions.
By connecting the framework to external systems, such as MATLAB, various tasks
can be autom ated and different functionalities can be added to the overall use of the
framework w ithout the need for modifying its core structure. In addition, th e frame­
work’s open architecture supports implementing different communication mechanisms
and MAS models which could be used for other types of MAS research. T he current
restrictions do not exclude the possibility th a t some of th e solutions developed in this
thesis may have a wider scope and be applicable, for instance, to selfish agents or to
individual interactions w ithout an im m ediate group context.
Interoperability is another im portant aspect of the framework. It can be achieved
in different ways. First, external systems can create and run experiments and access
the simulation results; this eliminates th e need for th e framework to include different
functionalities th a t already exist in other systems. An instance of such interoperability
has been dem onstrated in our research projects by connecting a sim ulator built in
our framework to the MATLAB’s Global O ptim ization Toolbox. Such a connection
allows the interaction model designers to use optim ization algorithms in order to
determine th e optimal configuration for their model. Second, th e framework allows its
MAS model to employ external agent reasoning engines to provide complex reasoning
capabilities for its agents.
The design of the framework remains open to a number of extensions to support

5

a wider scope of research on agent interaction models. First, in addition to message
passing, two other communication mechanisms are also included as options in the
general architecture model: indirect com munication through environment and com­
munication through shared storage. Second, different MAS models, th a t represent
different sets of problems in the real world, can be incorporated into th e framework.
Those extensions do not require m odification of th e framework’s architectural struc­
ture.
The insights concerning th e absence of suitably flexible simulation tools for AIP
design in the domain of agent teamwork, and the need to develop a new software
framework for th a t purpose, have developed gradually in th e course of our studies
of interaction protocols for helpful behavior in agent teamwork at th e University of
Northern British Columbia (UNBC) [Polajnar et al., 2011, Nalbandyan, 2011, Dal­
vandi, 2012, Polajnar et al., 2012]. D uring my participation in th e ongoing MAS
research a t UNBC, I have examined and evaluated th e development of A IPs for agent
teamwork, and have identified the requirem ents for developing a design tool to facili­
ta te their design and study.
The design of the framework proposed in this thesis has been incrementally refined
in interaction with the AIP research projects th a t employed its successive versions in
their simulation experiments. One of the projects has been the study of th e m utual
assistance protocol (MAP) [Nalbandyan, 2011, P olajnar et al., 2012], which uses a
bilateral approach for deciding w hether an agent should perform an action to help a
team m ate. Another project has investigated how incorporating em pathy into team ­
work of artificial agents, as a mechanism for triggering help, can improve th e team w ork
performance [Polajnar et al., 2011, Dalvandi, 2012]. Two other agent interaction pro­
tocols th a t use unilateral help approaches have also been modeled for com parative

6

studies of the MAP. The ability of the framework to model different types of A IPs
has thus been validated through application in ongoing AIP research. T h e interoper­
ability of the framework with the MATLAB Global Optimization Toolbox has been
successfully used to perform the optim ization of the em pathic help model. A dynam ic
teamwork environment has been modeled in a microworld and used for various ex­
periments. Finally, the framework’s distributable architecture has been tested and
validated for its performance.
T he rest of the thesis is organized as follows. C hapter 2 covers th e necessary
background and related work. C hapter 3 describes the research problem addressed in
this thesis and specifies my motivation and objectives for designing a new framework
for studies of agent interaction protocols. The next three chapters describe different
aspects of the framework.

First, I explain the architecture of a generic sim ulator

th a t can be built using the framework in C hapter 4. In Chapter 5, I present the
approach to the modeling of AIPs, and describe a common general world model for
agent teamwork as well as two different specializations of th e world m odel th a t lead to
two separate simulators, each designed for a different class of helpful behavior AIPs.
Finally, C hapter 6 describes the use of those simulators in conducting experim ents
with the two groups of AIPs. C hapter 7 presents an evaluation of the framework, and
Chapter 8 the conclusions and future work.

7

C hapter 2

B ackground and R ela ted W ork

This chapter presents the necessary background inform ation and an overview of the
previous work in m ultiagent systems, agent interactions and interaction protocols,
agent teamwork, engineering of agent interactions, and simulation of agent interac­
tions.

2.1

M u ltia g en t S y ste m s

There is no widely accepted definition of an agent or a multiagent system. According
to Wooldridge [2009], a multiagent system consists of multiple agents th a t interact
with each other. From another perspective, Shoham and Leyton-Brown [2008] define
multiagent systems as “...systems th a t include multiple autonomous entities w ith
either diverging information or diverging interests or both” .

8

Wooldridge and Jennings [1995] define an agent as a computer system th a t ex­
hibits autonomous behavior, is situated in an environment, an d pursues its objectives.
Wooldridge [2009] also specifies the capabilities th a t an intelligent agent is expected
to have: reactivity, th e ability of th e agent to perceive th e environment th a t it is
situated in and respond to perceived changes; proactiveness, the ability of th e agent
to perform goal-directed behavior by taking the initiative; and social ability, th a t lets
the agent meaningfully interact w ith other agents an d /o r humans.
Applications of MAS vary from space applications [Sierhuis et al., 2003] and m anu­
facturing [Monostori et al., 2006] to electronic commerce [Luck et al., 2003] and social
sciences [Sun, 2006].

2.2

A g en t In tera ctio n s an d In tera ctio n P r o to c o ls

Agent interaction is one of the central aspects of m ultiagent systems and agentoriented design. Agents can interact in different ways to achieve complex tasks by
coordinating their activities and behavior [Weiss, 2000]. T he nature of such inter­
actions varies from being com petitive to being cooperative. Furthermore, agent in­
teractions can be implemented using different com munication mechanisms.

Three

different communication mechanisms th a t are discussed in this thesis are: message
passing, shared-storage communication, and implicit communication through th e en­
vironment.
Message passing is the most commonly used com munication mechanism in MAS.
In message passing, a sender agent sends a message to the receiver directly by know­
ing its address [Uhrmacher and Weyns, 2009]. In order to achieve complex tasks

9

using message passing, often a num ber of messages need to be sent back and forth
between agents in some meaningful sequence. Although each message participates in
the interaction, the final outcome of the interaction is the result of all messages being
exchanged together. To ensure the successful outcome of such interactions, certain
constraints and rules need to be used to manage them efficiently. These constrains
and rules th a t are imposed to the messages are defined by an agent interaction proto­
col (AIP) [Chen and Sadaoui, 2003, Paurobally and Cunningham, 2002, Dunn-Davies
et al., 2005]. AIPs define the legal sequences, and content types, of th e messages th a t
the agents are allowed to send and receive in prescribed scenarios. There have been
a variety of AIPs developed, such as the well-known C ontract Net Protocol [Smith,
1980], different auction protocols (English Auction, D utch Auction), negotiation pro­
tocols, and protocols for helpful behavior.
In a shared-storage communication, agents interact through a shared m emory to
store and retrieve inform ation [Fortino and Russo, 2005] in order to solve a given prob­
lem. An im portant class of artificial intelligence (Al) systems for distributed problem
solving th a t rely on shared-storage communication are th e blackboard systems.
The blackboard concept is best described by Corkill [1991] as an approach similar
to a group of human experts working on a problem:

Imagine a group of hum an specialists seated next to a large blackboard.
The specialists are working cooperatively to solve a problem, using the
blackboard as the workplace for developing the solution.
Problem solving begins when the problem and initial data are w ritten
onto the blackboard. The specialists watch th e blackboard, looking for an
opportunity to apply their expertise to the developing solution. W hen a

10

specialist finds sufficient inform ation to make a contribution, she records
the contribution on the blackboard, hopefully enabling other specialists to
apply their expertise. This process of adding contributions to th e black­
board continues until the problem has been solved.

Blackboard systems generally consist of three m ain components: knowledge sources
(agents), a shared storage, and a control component.

T he knowledge sources are

software agents th a t contain th e knowledge and expertise needed to solve a specific
sub-problem. The agents in this model do not necessarily need to be aware of other
agents and their special expertise in th e system and are responsible to contribute to
solving the main problem whenever they can solve the sub-problems regarding their
specialty. Therefore, each agent can have its own internal architecture, program m ing
paradigm, and knowledge representation which suit its own expertise. T he blackboard
is the global memory th a t may contain different d a ta structures such as in p u t data,
partial solutions, and other d a ta needed in different stages of the problem solving as
well as providing a medium for communication and interaction between agents. The
control component is responsible for execution of th e system and the problem solving
by notifying each agent whenever they can contribute to solve the problem. The main
structure and th e role of the control com ponent differ in each system.
Implicit communication through environment is a form of indirect com m unication
th a t is based on concepts taken from biology and ethology where animals perform col­
lective behavior by using signals left in their environm ent as a means of com m unication
[Uhrmacher and Weyns, 2009]. Keil and Goldin [2006] define indirect interaction as an
interaction through making changes in a persistent environment so th a t th e recipient
agent can observe the changes. T he environm ent needs to be persistent in the sense
th a t it has a memory of interactions. As indirect interaction is a form of low-overhead
11

interaction which can be used by agents w ithout sophisticated com putational power
[Holland, 1996], one of its main application areas is the kind of m ultiagent system s
in which there could be no explicit task assignment or reasoning capabilities. In this
class of MAS, agents could be simple entities w ithout much com putational power
and they simply react to the signals they perceive in their environment in order to
coordinate their activities.
Uhrmacher and Weyns [2009] specify two forms of signals for MAS: m arks and
fields. Marks are signs th a t agents drop on their way on th e environm ent (which
could be in th e form of pheromones, tracks, objects, etc) so that other agents, by
perceiving these signs, can interpret their meaning or purpose. Fields are signals th a t
are spread in the environment and their intensity can reflect the distance between
a source and a location in th e environment. They are mostly useful for avoiding
obstacles or finding desirable objects in the environment.

2.3

A g en t T eam w ork

Teamwork is th e collaboration of agents in order to achieve a common task. According
to Cohen and Levesque [1991], teamwork is more th an ju st the collection of simul­
taneous and coordinated tasks being done by a group. W h at mainly distinguishes
teamwork from other group activities is th a t team members share a m utual m ental
state. For example, agents typically have some common beliefs and jo in t goals. This
m utual mental state affects, and is affected by, th e mental states of team members.
The collective activity is performed by individuals th a t share this m ental state.
The motivation for th e research on agent teamwork comes from the fact th a t in

12

most real-world applications, th e agents are situated in an uncertain, highly dynam ic
environment. Such environments are constantly changing. Therefore, any a ttem p t to
build the team baaed on a fixed, predefined algorithm for coordination among team
members will result in failures in th e system [Tambe, 1997]. T he research on teamwork
in multiagent systems can be divided into two groups: team s of pure agents and team s
of human-agent. In my research I will be mainly concerned w ith the team w ork among
artificial agents.
A team, in order to act coherently and address th e problems raised by uncertainties
of the environment, must have the following characteristics: provide flexible commu­
nication among the agents, enable agents to m onitor their team m ates’ progress, and
allow reorganization and reallocation of resources to all th e team m em bers [Tambe,
1997],
In order to increase the teamwork performance, agents can perform helpful behav­
ior by assisting their team m ates through performing tasks, providing relevant infor­
mation, or giving away their resources. Helpful behavior is becoming an active area of
research [Yen et al., 2004, Fan et al., 2005, K am ar et al., 2009, Polajnar et al., 2011,
2012 ],

A certain class of agent teams, called expert teams, are those in which each m em ­
ber may have a unique set of skills and knowledge th a t distinguishes it from other
team members. This set of skills and knowledge defines the member’s expertise which
is not easily transferable to other members. Different research approaches have been
taken on this class of agent team s in MAS [Singh, 1991, Polajnar et al., 2011]. T he au­
tonomy and distinct expertise of team members influence th e design of th e interaction
mechanisms for such systems.

13

Teamwork models have shown their effectiveness in real-world applications in
which agents work together to jointly accomplish a particular task [Nair et al., 2003].
Examples include robotic soccer [Kitano et al., 1997, Palam ara et al., 2009], simula­
tions of urban search and rescue [Kitano et al., 1999, Kruijff et al., 2012], battlefield
simulations [Tambe, 1997, Li et al., 2010], and personal assistant agents [Tambe et al.,
2002, Yorke-Smith et al., 2012].
An observation from reviewing the work on agent teamwork and helpful behavior
indicates th a t agent interaction plays a central role in effective teamwork. In order to
successfully implement and incorporate teamwork and helpful behavior models into
real-world multiagent systems, one needs to design and employ sophisticated and
flexible interactions.

2.4

E n gin eerin g o f A g en t In te ra ctio n P r o to c o ls

2.4.1

Formal M eth od s

Formal approaches can be used to develop and verify agent interaction protocols.
These approaches are often used to specify protocols and verify and validate their
properties and are usually extensions to the methods used to develop protocols in
distributed systems. In MAS literature, in order to capture, represent, and specify
AIPs, different formal approaches have been introduced. These approaches are mostly
based on Extended Finite State Machines [Lind, 2002], Extended UML [Lind, 2002],
and Petri Nets [Cost et al., 1999]. In the following, a short overview of some of these
works is presented.

14

In [Odell et al., 2001], the authors argue th a t while the current Unified Modeling
Language (UML) framework provides a number of different properties th a t can be
applied to AIPs, there are some extensions specific to MAS. In particular, th ey propose
Agent UML, an extension of UML th a t is adopted for m ultiagent systems. AUML uses
a layered approach for modeling AIPs in which different AUML notations, including
statecharts, are used to represent different aspects of AIPs.
In [Mazouzi et al., 2002], the authors propose a generic formal approach for proto­
col engineering th a t translates semi-formal specification using Agent UML into Col­
ored P etri Nets and introduces the Recursive Colored P etri Nets formalism.
Chen and Sadaoui [2003] introduce a generic formal framework to develop and
verify AIPs based on a formal specification language called Lotos which is widely
used in distributed systems. Their approach handles concurrency and synchronization,
provides the correctness of AIPs in term s of safety, liveness, and fairness and uses a
number of different tools to formally analyze and verify A IP specifications.
M okhati et al. [2007] propose a formal framework th a t can be used to formally
specify the behavior of MAS interactions and verify and validate them.
Dunn-Davies et al. [2005] introduce th e propositional statechart formalism to rep­
resent AIPs. Their approach is based on the statechart formalism, a popular m ethod
included in the UML standard, and supports protocol verification and validation.

15

2.4.2

M ultiagent Languages and P latform s

T he growing interest in research on m ultiagent systems has resulted in th e develop­
ment of different programming languages and tools th a t could be used to im plem ent
such systems. Using agent-oriented languages rather th an conventional program m ing
languages enables the programmers to model problems from a MAS perspective and
implement them in term s of cognitive and social concepts of MAS such as beliefs,
goals, plans, roles, and norms. Agent-oriented program m ing languages th a t are cur­
rently in the m ultiagent systems literature vary from being completely declarative, to
being completely imperative. There are also several hybrid approaches as well. Our
discussion of agent-oriented languages below is based on a survey by Bordini et al.
[2006].
For most of the agent programm ing languages, there are platforms th a t im ple­
ment their semantics (e.g., Jason platform implements the AgentSpeak(L) semantics).
There are also agent platform s th a t are not based on any specific program m ing lan­
guage. These platforms instead focus on the underlying infrastructures for agents to
coexist with each other and be able to find each other and communicate (e.g., Jade).
Most of the cognitive aspects of the agents are declarative by n atu re and thus,
there have been more declarative languages proposed. Such languages often follow
a strong formal logic-based approach. Examples are FLUX [Thielscher, 2005], MIN­
ERVA [Leite et al., 2002], KABUL and EVOLP [Alferes et al., 2002], DALI [Costantini
and Tocchio, 2002], and ReSpecT [Omicini and Denti, 2001].
There are a few purely im perative agent-oriented programming languages as it is
often not convenient to implement agent-oriented abstractions using an im perative
programming language. One of the examples of such a programming language is the
16

commercial JACK Agent Language (JAL) [Evertsz et al., 2004] which extends the
Java programming language instead of using a logic-based approach.
Many of the well-known agent languages provide both declarative and im perative
features. While one can model agent’s cognitive aspects in a declarative m anner,
these languages allow the use of some im perative code implemented in an external
language through some special constructs. Examples of such hybrid languages are
3APL (An A bstract Agent Program m ing Language “triple-a-p-1”) [Hindriks et al.,
1999], AgentSpeak(L) [Rao, 1996], IM PACT [Subrahmanian, 2000], GO! [Clark and
McCabe, 2004], and AF-APL (Agent Factory Agent Programming Language) [Collier,
2002 ],

Among different agent platform s and frameworks, it is w orth to m ention TuCSoN
(Tuple Centre Spread over th e Network), a framework for multiagent coordination
[Omicini and Zambonelli, 1999]; JAD E (Java Agent DEvelopment framework) [Bellifemine et al., 2005], a Java framework for th e development of distributed m ultiagent
applications; Jadex [Pokahr et al., 2005], a framework for the creation of belief-desireintention (BDI) agents; and Jason [Bordini et al., 2008], an interpreter and framework
for implementing agents using AgentSpeak(L).

2.5

S im u lation o f A g en t In te ra ctio n s

Simulation is an experimental com putational m ethod for designing, testing, and study­
ing theories or real systems [Uhrmacher and Weyns, 2009]. I t is mostly used in sit­
uations where conducting experiments w ith a real-world system is either impossible
or expensive. Furtherm ore, often real systems are not fully controllable and therefore

17

it is not easy to design the desired experim ental settings [Smith, 1980]. According to
Shannon [1975], simulation can be defined as:

The process of designing a model of a real system and conducting
experiments with this model for th e purpose either of understanding the
behavior of the system a n d /o r of evaluating various strategies (w ithin th e
limits imposed by a criterion or a set of criteria) for th e operation of the
system.

Based on Uhrmacher and Weyns’s [2009] point of view, the relationship of MAS
and simulation is twofold: from one perspective, simulation techniques can be used
to design, study, and run a MAS; from another perspective, MAS can be used as
a modeling paradigm to study and understand real-world complex system s th a t are
composed of many interacting entities. Different MAS platforms th a t are developed
to support building multiagent systems such as JA D E [Bellifemine et al., 2005] and
Jason [Bordini et al., 2008] belong to th e first category. T he second category includes
a variety of tools th a t are developed for modeling various application areas such as
studying the behavior of agents in the stock m arket, network security, and under­
standing the consumers purchasing behavior. More examples of such tools can be
found in [Nikolai and Madey, 2009]. In this thesis I am concerned ab o u t th e first
category.
Simulation experiments have been a key m ethod in th e evaluation of possible
designs since the earliest studies of the agent interaction models. T he C ontract Net
Protocol introduced by Smith [1980] is developed and evaluated through a specially de­
signed simulator called CN ET th a t sim ulated a real-world environment of d istributed
sensors and processors. Using th a t sim ulator, Sm ith was able to conduct experim ents,
18

evaluate his protocol, and introduce th e necessary refinements, which may not have
been possible which may not have been possible w ithout th e simulator.
In research on agent interactions, and in particular AIPs, researchers often develop
their own simulators because of the lack of a general sim ulation environment. As such
simulators are built to specifically support certain interaction models, they often lack
the flexibility th a t is needed in order to allow other researchers to experim ent w ith
other classes of interaction models. Examples of such work can be found in [Findler
and Elder, 1995, W anyama and Homayoun Far, 2007]. In each case, th e authors have
developed their own sim ulator which is specifically built to support their own work.
These type of simulators often rem ain specific and are not used by oth er researchers
or for other classes of interaction models.
In order to conduct simulation experiments w ith an agent interaction model, it
can be implemented w ithin m ultiagent platforms (as described in Section 2.4) along
with a MAS which can be used for experiments. These platforms often provide em­
bedded reasoning engines, communication infrastructure and management services,
and support for ontologies. Some of the research projects which require sim ulation of
agent interaction models have been done using these MAS platforms. For example,
[Pasquier et al., 2011] uses 3APL or [Cheng et al., 2010] uses Jadex.
For the purpose of using simulation experiments in designing agent interaction
models, MAS platforms have some limitations. F irst, a MAS platform does not pro­
vide the user with mechanisms for experim entation and analysis of the results. Second,
a MAS platform usually does not provide the means by which the experim enter could
isolate the im pact of agent interactions from the im pact of other aspects of agent
behavior.

19

As an example of a wide-scope sim ulator, Kotenko [2009] introduces a domainindependent simulator for agent team s’ collaboration and competition. His proposed
simulation framework is based on three m ain components: models of agent teams;
models of team interactions; and interaction environment model. It supports domain
specific ontologies through a subject dom ain library.
Simulation of multiagent systems requires modeling th e environment which agents
are going to be situated in. Often even a simple real-world problem can result in
a relatively complex simulation model. Such a complex model is full of details th a t
can limit the study of th e effects of different factors on th e model’s behavior and
performance. A successful approach th a t has been proven to be useful in artificial
intelligence is to model the world using th e microworld approach. In a microworld
model, only the essential elements of a system th a t reflect th e essence of th e system are
included in the model. Thus, th e result is a very simplified model which can be used
as a means to study th e real system w ithout th e need to deal with unnecessary details.
The best known example of a microworld approach is the Blocks World [Russell and
Norvig, 1995] used in research on planning in classical Al. It basically consists of a
set of solid blocks th a t are on a tabletop, and a robot arm that is able to pick one
of them at a time and place it on top of another block or on the table. Given an
initial state, the goal is to build one or more block stacks according th e th e specified
planning structure. This simple yet effective model allows researchers to investigate
different planning mechanisms.
In the realm of agent interactions, the Colored Trails (C T) game [Gal e t al., 2010]
introduces another well-known microworld th a t abstracts multiagent task dom ains in
which players negotiate and exchange resources in order to achieve their individual or
group goals. It is mainly designed to study and investigate different decision-making

20

models in open mixed networks. CT has been used in MAS research and specifically
in helpful behavior [Kamar et al., 2009]. However, with respect to its possible use in
the design of the interaction models, C T has two main limitations. F irst, it does not
support explicit representation of interaction models. Second, CT does n o t provide
the basic tools for experim entation w ith th e model being simulated.

21

C hapter 3

A N ew Fram ew ork for S tu d ies o f
A gent In teraction M od els

The purpose of this chapter is to explain th e reasons th a t m otivated th e research ad­
dressed in this thesis, describe the research problem, and present the solution strategy.
In Section 3 .1 ,1 explore th e challenges in th e design and quantitative analysis of agent
interaction models th a t need to be addressed. In Section 3.2, I present the rationale
for a new software framework th a t will serve as a design tool for the development of
certain types of interaction models in agent teamwork. In Section 3.3, I form ulate and
explain some of the design principles th a t I will use in th e construction of th e new
framework in order to ensure its effectiveness in its im m ediate application domain,
and in order to keep it open for different application domains. Finally, my approach
for presenting th e framework in this thesis is briefly explained in Section 3.4.

22

3.1

T h e C h allen ges in S tu d y in g A g en t In te ra ctio n s

Agent interaction is one of the fundam ental aspects of multiagent systems and agentoriented design. It allows agents to coordinate their activities, cooperate, collaborate,
and negotiate while trying to achieve their individual or collective goals. T he study
of agent interaction models has long been an active area of research in MAS; in recent
years its practical significance has been on th e rise, as many developing areas of MAS
application require concrete engineering solutions (Section 2.2). The present section
outlines some of the challenges encountered in such research and explains how they
motivate the topic of this thesis.
We use the term interaction model to denote a specific pattern of interaction th a t
agents use in order to achieve a certain objective; for instance, an auction mechanism
can be used to allocate a resource on a com petitive basis. An interaction model is
described in term s of communication acts by which th e participating agents exchange
information. M ultiagent systems use several types of communication mechanisms.
Some of the common ones are: message passing, where agents send messages th a t
are explicitly addressed to other agents; shared-storage communication, where agents
post information in a storage area th a t is accessible to other agents; and implicit
communication through th e environment, where agents simply act upon the environ­
m ent and modify its state in a way th a t is perceived by other agents (Section 2.2).
Interaction models based on message passing are called agent interaction protocols
(AIP). They specify the structure and sequencing of the messages involved in the
interaction, as well as the behavior of th e agents th a t exchange them. T he techniques
by which agent interaction protocols can be specified and analyzed are derived in p art
from the techniques developed for protocols in networking and distributed com puting
(Section 2.4).
23

The development of an agent interaction model to the point th a t it can be effec­
tively applied in practical system engineering is a challenging process. T he model
designer typically faces a large number of decisions with many possible outcomes,
whose impact upon the properties and performance of a multiagent system as a whole
is often difficult to predict. Once an agent interaction model has been conceived, and
before it has been fully specified in detail, its designer needs to quantitatively ana­
lyze its impact on the system behavior and performance, determining its properties,
advantages, and disadvantages in a specific context. In such studies, th e perform ance
of the multiagent system depends not only on the choice of th e interaction model and
its param eter values, but also on many other factors, such as: the characteristics of
the environment in which agents are situated and perform th eir tasks; th e task struc­
ture and complexity, including subtask assignment and resource allocation strategies;
and the overall system organization. In order to evaluate an interaction model in
context, one needs to study a m ultiagent system as a whole in a number of different
configurations and situations.
In evaluating the early design of an interaction model, there is a wide variety
of questions th a t the researcher needs to answer. Does th e model design have the
necessary formal properties, such as the absence of deadlock? When should an agent
decide to initiate an interaction? W hen should an agent engage in an interaction
initiated by another? How well does a MAS th a t uses the interaction model perform
in different situations and scenarios? Given a specific MAS context, how does the
interaction model compare with alternative models w ith respect to th e desired system
performance? Which param eter settings for the interaction model result in a b etter
(or optimal) performance of th e MAS? The answers to these and other questions are
needed in order to better understand and evaluate the properties of a model in relation
to its use in real-world environments. T he feedback from th e evaluation studies leads

24

to iterative refinements of the original design of the interaction model, enabling the
researcher to draw conclusions regarding its suitability for a specific purpose, and to
adapt it to a specific set of requirements.
While some of the questions outlined above can be addressed through formal spec­
ification of interaction models and their m athem atical studies, simulation has proven
to be the most widely applicable and effective m ethod for conducting such evaluations.
Simulation has been a key m ethod in the evaluation of possible designs since th e ear­
liest studies of agent interaction models (e.g., th e Contract Net Protocol introduced
by Smith [1980]). It is a powerful and flexible tool in studying the properties and
predicting the behavior of a complex system such as a MAS in situations of practical
interest (Section 2.4).
Despite the growing research interest in agent interaction models, to th e best of
our knowledge, universal or wide-scope simulation tools th a t would effectively support
all the necessary aspects of their quantitative studies in MAS context have n o t yet
appeared (Section 2.5). This situation gives rise to three kinds of research challenges.
First, when embarking on a study of a relatively novel class of interaction models,
one needs specialized simulation tools, based on a suitable set of abstractions arising
from an analysis of the nature of th e model, and a suitable set of facilities arising
from an analysis of the experim enter’s practical needs in mastering th e design deci­
sion complexity. Typically, different researchers or research teams develop their own
simulators for the particular types of interaction models th a t they study and the types
of questions th a t they intend to pursue (Section 2.5). Such tools are th en gradually
perfected through ongoing research on interaction models within th e selected class.
T he research on agent interactions is still in an early stage and various new models
are expected to appear. For the tim e being, those new models are likely to require
25

the development of new specialized simulation tools.
Second, a m ajor challenge in simulation studies of agent interaction models comes
from th e complexity of the world in which the agents are situated. Even an apparently
simple real-world situation can result in a fairly complex simulation model.

This

slows down the simulation and limits the entire research process. T he m ultitude of
factors represented in the complex model also makes it difficult to infer th e im pact
of individual factors on different aspects of the m odel’s behavior and performance.
This difficulty has long been recognized in the studies of artificial intelligence.

A

successful m ethod of overcoming it has been the construction of a microworld, an
abstract world model th a t represents the key aspects of th e problem being studied
in a highly simplified and yet relevant m anner (Section 2.5). For each problem class,
finding the right abstractions th a t achieve both simplicity and relevance requires a
deep understanding of the problem and represents a m ajor research challenge.
Third, there is the challenge of widening the application scope of th e sim ulation
tools. While developing support for specialized interaction models, one can try to keep
the adopted solutions general, flexible, and extendible, and thus contribute towards
a better understanding of what a more general sim ulation environment for a wider
variety of interaction models would need to support and how it could be constructed.
An im portant aspect of such generality is th e openness tow ards different microworlds.
This type of research may pave the way for th e eventual construction of more general
simulation frameworks for the study of agent interaction models.
The purpose of this thesis is to address all three challenges, in th e specific scope
outlined in the next two sections.

26

3.2

T h e R a tio n a le for a N e w Fram ew ork

In this thesis, I propose a new software framework for early simulation studies dur­
ing the design stage of agent interaction protocols for helpful behavior in team s of
artificial agents. The framework design addresses th e research challenges identified in
the previous section by providing specialized support within its restricted application
domain, by providing a core microworld open to variation, as well as by favoring archi­
tectural solutions th a t are open to generalization and extension beyond th is restricted
domain.
The motivation for the new sim ulator has developed gradually through my p artic­
ipation, as a member of th e MAS research group a t UNBC, in simulation studies of
interaction protocols for helpful behavior in agent teamwork. The subject m a tter of
those studies has been a new family of protocols, introduced in [Polajnar et al., 2011,
2012, Nalbandyan, 2011, Dalvandi, 2012], and further expanded in ongoing research.
The simulation experiments have mainly aimed a t the testing of key design ideas in
the early stages of protocol development. The emphasis has been on investigating the
im pact of protocol design decisions upon the performance of an agent team th a t em­
ploys the protocol. One common experim ent scenario involves comparisons between
several agent team s th a t address identical tasks in identical environments, and have
identical designs except th a t they employ different versions of the interaction proto­
col. In another common experim ent scenario, one seeks to evaluate th e protocol under
study by comparing the performance of a team th a t employs it and th e team s th a t
employ alternative solutions (of a different nature) for the same purpose under the
same circumstances. As the work progressed, it became apparent th a t th e existing
tools were not well-suited to th e research tasks. A new specialized sim ulation tool
needed to be developed, and the ideas shaping its design gradually becam e clear.
27

The proposed software framework is intended to serve as a design tool for in­
teraction models in agent teamwork and differs from other kinds of sim ulators th a t
one might use for agent teamwork. For example, in an operating search and rescue
system in which robots interact with people, one may employ a sim ulator to train
the human personnel in a realistic virtual environm ent th a t mimics th e real-world
experiences. T h at kind of simulator requires comprehensive modeling of th e MAS in
a real-world environment. In contrast, th e framework introduced in this thesis is built
for an entirely different purpose, nam ely for facilitating th e design of agent interac­
tions, which favors simple and abstract MAS models. In th e rest of this section, I
identify some of the key requirements arising from this particular orientation of the
proposed framework.
The process of designing an agent interaction model typically involves series of
incremental refinements.

Each step includes a set of simulation experim ents th a t

provide an information basis for a specific design choice over a potentially large de­
cision space. In order to properly guide th e design evolution, the experim entation
must be interactive and provide early feedback th a t allows fast elimination of unde­
sirable model features, adjustm ents of th e relevant model param eters, and avoidance
of unproductive experiment setups. These and other core requirements need to be
addressed a t the level of the basic architecture of the software framework, as well as
at the levels of its detailed design and implem entation.
In order to have statistically significant results, one needs to rep eat th e same
experiment a large number of times. On th e one hand, while experim enting with
a lower number of runs provides the results faster, such results cannot be used to
draw reliable quantitative conclusions, although they may sometimes help roughly
identify the qualitative trends. On th e other hand, simulation may be com putationally

28

expensive, and a high number of runs may require substantial com putational power,
or a long com putation time, in order to produce th e simulation results w ith th e desired
statistical significance. An experimenter in an early stage of the design process, who
seeks to quickly move away from unproductive options, can greatly benefit from fast
identification of unfavorable qualitative trends, despite their low level of statistical
accuracy, while the assessments of near-satisfactory candidate solutions m ay require
a high degree of statistical confidence. In order to be used effectively in a design
process, the simulation framework needs to provide the experimenter w ith interactive
dynamic control over repetitive runs based on th e observation of th e interm ediate
results. The user also needs to be able to dynam ically modify different param eters of
the MAS model under study, and to observe their effect on th e system behavior and
performance.
The proposed specialized simulation framework should n o t aspire to incorporate
the functionality th a t is already well supported by available software packages, such
as m athem atical optimization or statistical analysis. Moreover, the complex function­
ality th a t will be required in the anticipated deployment of th e model, such as specific
reasoning engines or knowledge bases, should preferably not be im ported and inte­
grated into the framework. In both cases it is generally more appropriate to enable the
framework to interact with external systems th a t provide th e required functionality.
Such interactions may involve scenarios in which the framework employs services of
other systems, as well as scenarios in which it provides simulation services to other
systems.
The proposed software framework should be adaptable and extendible so th a t
one can easily widen its scope as a simulation tool. At a minimum, one should be
able to modify the world model in order to experiment w ith different phenom ena

29

and environments, and allow extensions th a t support other types of com munication
mechanisms and interaction models.
The framework also needs to provide the means for transition tow ards further
stages of interaction model development, namely the prototyping of th e model in
concrete multiagent platforms and languages. This is required in order to allow the
designer to make sure th a t the experim ental results can be reproduced and applied in
more realistic settings.
M any MAS applications in engineering and other fields involve agent team s w ith
specialized individual roles th a t rely on different knowledge bases, similar to m ultidis­
ciplinary human teams. In an expert team (as discussed in Section 2.3) each member
has a unique set of skills and knowledge th a t distinguishes it from other team mem­
bers and th a t may not be easily transferable to other members. In our studies of
helpful behavior among team members, th e m ultiagent system model involves agents
th a t have their own expertise, which makes the cost of an action dependent on who
performs it.
Teamwork of artificial agents has become a m ainstream research area in MAS;
within it, the study of helpful behavior increasingly attracts th e interest of researchers
(Section 2.3), but adequate simulation tools for th e design of necessary A IPs are not
readily available (Section 2.5).

Having identified the resulting challenges and the

requirements for overcoming them , we can now address th e design principles for the
proposed new software framework.

30

3.3

T h e D esig n P rin cip les

The previous section has highlighted a num ber of characteristics th at th e new frame­
work needs to have in order to fulfill its purpose. Those characteristics shape my
approach to the design of the framework, from its high-level architectural definition
to its detailed design and implementation. In the present section, I identify and ex­
plain the principles th a t will guide my design decisions presented in th e next two
chapters.

In te ra c tiv e E x p erim en t C ontrol. The experimenter should be able to directly
m anipulate the models during simulation experiments. In support of this type of inter­
activity, the system should be able to display the sim ulation results as th e experim ent
progresses, providing the feedback necessary for further decisions. By following this
principle, the framework helps to reduce the decision space by allowing th e designer
of an interaction model to detect and elim inate undesirable features of th e model.

C on cu rren t S im u la tio n o f an E x p e rim e n t S cen a rio in M u ltip le A g en t
Teams.

In order to address the challenges in com parative studies of interaction

models, multiple agent teams can be sim ulated concurrently. As each team employs its
own interaction model, using this approach the experim enter can study and compare
multiple interaction models, or different variations of th e same model, at th e same
tim e in identical environments and scenarios, and m onitor all the results a t once as
the experimentation progresses.

In tera ctive V isu a liza tio n D u rin g S im u la tio n . The results of th e simulation,
as well as the state of the world, can be visualized and provided to th e experim enter
as they are being generated and updated. This visualization should be supported by
a graphical user interface (GUI) provided by the framework.
31

In te ra c tiv e C on trol O ver G radual R efin e m e n t o f A ccuracy. T he statistical
accuracy of the simulation results for a series of experiments can be refined gradually
as the simulation process continues. In order to have statistically significant results,
experiments need to be repeated a large num ber of times, causing th e sim ulation
process to take longer. This design principle seeks to balance the generation speed
and the statistical accuracy of the results as a particular stage of th e design process
may require. For instance, the simulation m ight sta rt w ith a relatively low num ber
of runs for each experiment (which can be done in a reasonable tim e). This produces
the initial results which represent the preview of the trend of the results in a tim ely
manner but with a low statistical accuracy. Next, the simulator repeats th e same
experiments and consequently the accuracy of th e results improves w ith tim e.

M icrow orld-based M A S M odeling. In order to provide a simple yet representa­
tive world model, the framework should employ a MAS model th at is based on the
microworld approach. This principle reduces the need to incorporate complex domain
knowledge, and lets the agent reasoning focus on th e essentials.

Low C oupling B etw een the S im u la tio n E n v iro n m e n t and the M A S M odel.
The framework should support modifying and replacing th e MAS model through
localized programming w ithout th e need to modify the rest of the framework. This
is essential as supporting different MAS models makes the framework suitable for
studying interaction models in a wider range of contexts.

In teroperability w ith o th er S y ste m s. T he framework should support interactions
with other systems both as a client and as a server. This is required in order to use the
functionalities th a t are already provided by such external systems b u t needed by the
experimenter. In turn, th e framework should allow external systems to define and run
experiments and access the simulation results. T he framework should also support
32

the employment of external reasoning engines or knowledge bases by its agents.
D is tr ib u ta b le A r c h ite c tu r e a n d I m p le m e n ta t io n . T he framework should have
a distributable architecture th a t allows the sim ulation to be either executed on a single
computer or distributed across multiple nodes in a network. The main objective is to
overcome the com putational complexity and produce the simulation results faster. In
particular, this implies th a t early feedback is delivered much faster to th e interactive
user, accelerating the design process.

3.4

T h e A pp roach in T h is T h esis

The framework proposed in this thesis can be used to build customized sim ulators for
agent interaction models. Such simulators are tailored to simulate a specific group
of agent interaction models in a desired context chosen by their designer. For th a t

Fram ework

C ustom MAS
M odel

+

MAS M odel i

Custom Sim ulator

C ustom MAS
Model

Figure 3.1: Building customized sim ulators using th e framework

purpose, the framework includes a simulation environm ent th at supports different

MAS models. By incorporating a specific MAS model to th e framework, one builds a
customized simulator (Figure 3.1).
In the next chapters, th e framework is presented by elaborating its generic sim­
ulator architecture and th e approaches used for building a simulation model. The
MAS model presented in this thesis is specifically designed to support our studies of
helpful behavior in agent teamwork. In order to elaborate the framework in more
concrete terms, as well as to evaluate it, two different simulators th a t are b u ilt using
the framework are introduced and explained.

34

C hapter 4

T h e G eneric Sim ulator
A rch itectu re

This chapter presents the generic sim ulator’s architecture of the framework. This
architecture can be used to build sim ulators th a t are customized for different inter­
action models. The chapter begins by identifying th e system requirements in term s
of functional, non-functional, and domain-specific requirem ents in Section 4.1. The
system structure and its high-level decomposition are explained in Section 4.2. In
Section 4.3, th e behavioral view of different components of the generic sim ulator is
elaborated. Finally, in Section 4.4 th e role of this generic architecture in creating
customized simulation tools is explained.

35

4.1

T h e S y ste m R eq u irem en ts

In order to specify the requirements of th e proposed system, I have used th e ap­
proach suggested in [Sommerville, 2004] and have divided th e requirements in three
categories: functional requirements, non-functional requirements, and domain-specific
requirements. In the rest of this section, different elements of each group are explained.

4.1.1

Functional R equirem ents

The generic functions of the sim ulator are captured in the use cases represented in
Figure 4.1. It illustrates the functionality of the simulator without including its in­
teroperability features. Each use case is explained in more detail in th e following
paragraphs.

1. Set up and Run Experiment: The experimenter can set up an experim ent and
run it. This functionality is further decomposed into other use cases as follows:
(a) Load Experiment: The experim enter can load a previously saved experi­
ment setup from a file.
(b) Configure Experiment: The experim enter can configure different aspects of
an experiment.
i. Configure Team: The experim enter can configure the param eters re­
garding the team(s) he/she wishes to study. This includes selecting the
participating interaction model(s) and configuring them . In addition,
other properties of a team can be configured in this use case (e.g. th e
team composition).
36

S im u lato r

Load
Experiment

Configure
Experiment

Configure
Team

Configure
Interaction
_ Model _
Configure
Team Size,
Composition, etc.

Configure
Environment

S et up and R u n V " ! * ^
Experiment )
S ave
Experiment

Configure
Simulator

Start
Experiment

Run
Experiment

Step
Experiment

E x p e rim e n t

Stop
Experiment
Display MAS
Model(s)

Display
Experiment

D is p la y "
Experiment
.R e s u lt s

Debug
Experiment

Figure 4.1: The use case diagram of the simulator as a stand-alone system
ii. Configure Environment: The experimenter can configure th e proper­
ties of the environment in which th e team(s) would be situated.
iii. Configure Simulator: The experimenter can configure different param ­
eters of the simulator.
(c) Save Experiment: T he experimenter can save the current experim ent setup
into a file.

37

(d) R un Experiment: The experimenter can control th e execution of th e simu­
lation. experimenter can sta rt and stop an experiment. In addition, he/she
can execute the simulation step-by-step.
2. Display Experiment: The Display Experiment use case includes the following
three use cases:
(a) Display M A S Model(s): Upon experim enter’s request, the system displays
the MAS model(s) being simulated in a graphical representation to th e ex­
perimenter. This includes the environm ent state, agents, and team related
information.
(b) Display Experiment Results: Upon experim enter’s request, th e system pro­
vides the experiment results to th e experim enter. Results can be either
visualized in graphs or displayed in a numerical format.
(c) Debug Experiment: The experimenter can access and study th e logs gen­
erated by the interaction model(s) and th e environment he/sh e studies.

S im u la to r as a C lie n t o f a n E x te r n a l S y s te m .

T h e simulator can use the

services provided by an external system. For example, the experimenter can request
an external statistical software to process th e sim ulator’s results or use an external
visualization package to draw customized charts based on th e simulation results. This
type of interoperability of the sim ulator is presented by th e use case diagram in
Figure 4.2 and explained below:

1. T h e S im u lator
(a) Configure External System Interface: T he experimenter can configure the
interface th a t is required to interact w ith the external system and use its
services.
38

S im ulator

External System

Configure External
System Interface

Configure Simulator
Interface

R equest External
System Service

Accept & P ro cess
the Request

Receive and
Display R esults

S end Results

Experim enter

Figure 4.2: Simulator as a client of an external system
(b) Request External System Service: The experim enter can request a service
from the external system.
(c) Receive and Display Results: T he experimenter can ask sim ulator to receive
and display the results generated by th e external system.
2. T h e E x tern a l S y stem
(a) Configure Simulator Interface: The experimenter can configure th e simu­
lator interface to the external system through Configure External System
Interface.
(b) Accept & Process the Request: The experimenter can ask th e external sys­
tem to accept and process th e request through Request External System
Service.
(c) Send Results: The experim enter can ask the external system to send the
results to the simulator through Receive and Display Results interface.

39

S im ulator

External S ystem

Configure External
System Interface

Configure Sim ulator
Interface

S e t up and Run
Experiment

R equest Simulation
Experim ent

E xperim enter

R e q u est &
P ro cess R esults

Display
Experiment

Figure 4.3: Simulator as a server of an external system
S im u la to r a s a S e r v e r o f a n E x te r n a l S y s te m . T he simulator can act as a
server to an external system. The external system can invoke the sim ulator to run an
experiment with a specified setup. The use cases for this form of interoperability are
presented in Figure 4.3 and explained below.

1. T h e E xtern al S y stem
(a) Configure Simulator Interface: The experim enter can configure the ex­
ternal system to comply w ith the required interface to interact with the
simulator.
(b) Request Simulation Experiment: The experim enter can request an experi­
ment from the simulator by providing the required properties of th e exper­
iment.
(c) Request & Process Results: The experimenter can request th e results of the
experiment from the simulator, and have them processed by th e external
40

system.
2. T h e S im u lator
(a) Configure External System Interface: T he experimenter can configure ex­
ternal system interface to the sim ulator through Configure Sim ulator In ­
terface.
(b) Set up and Run Experiment: The experimenter can ask th e sim ulator to
run an experiment based on the given experim ent setup through Request
Simulation Experiment.
(c) Display Experiment: The experimenter can ask the simulator to display
the results for further processing in th e external system through Request
& Process Results.

S im u la to r in a B ila tera l C lie n t-S e rv e r R ela tio n w ith an E x tern a l S y ste m .
The sim ulator can interact with an external system in a bilateral client-server m an­
ner. The experimenter can request a service from the external system through the
simulator. In return, the external system, upon th e experim enter’s activation through
the simulator, can specify and request an experiment to be done by th e simulator.
Once the simulation results are ready, the external system can further process them.
At the end, the simulator can receive and display the external system ’s service re­
sults to the experimenter. For example, the experimenter can ask an external system
to optimize a number of param eters of th e model he wishes to study. T he external
system can create a number of different experiments, request th at they be performed
by the simulator, and use their results in order to find th e optimal values of those
param eters using its services. The use cases in Figure 4.4 represent this relationship
and are explained in the following:

41

Sim ulator

External System

Configure External
System Interface

Configure Simulator
Interface

Request External
System Service

Accept & Process
the Request
« in c lu d e »

R equest Simulation
Experiment

Set up and Run
Experiment

« in c u d e »

Experimenter

Display
Experiment

Receive
Experiment R esults

Receive and
Display Results

Send Results

Figure 4.4: Simulator in a bilateral client-server relation w ith an external system
1. T h e S im u la to r
(a) Configure External System Interface: T he experimenter can configure the
interface th a t is required in order to interact w ith th e external system and
use its services.
(b) Request External System Service: The experim enter can request a service
from the external system.
(c) Set up and Run Experiment: T he experimenter, through Request External
System Service and Accept & Process the Request, asks the external system
to create an experiment setup and pass it to the simulator to run it through
Request Simulation Experiment.
42

(d) Display Experiment: The experim enter can ask the simulator to display its
results through Request External System Service functionality of th e sim­
ulator and Accept & Process the Request and Receive Experim ent Results
functionalities of the external system.
(e) Receive and Display Results: The sim ulator can receive th e results of the
external system ’s service and display it to the experimenter.
2. T h e E x tern a l S y stem
(a) Configure Simulator Interface: The experimenter can configure sim ulator
interface to the external system through Configure External System In ter­
face.
(b) Accept & Process the Request: The experim enter can ask th e external sys­
tem to accept and process the request through Request External System
Service. This includes two other use cases:
i. Request Simulation Experiment: Upon the experim enter’s request through
Request External System Service and Accept & Process the Request,
the external system can create an experim ent setup and request the
simulator to run it.
ii. Receive Experiment Results: Upon th e experimenter’s request through
Request External System Service and Accept & Process the Request, the
external system can receive the experim ent results from the sim ulator.
(c) Send Results: T he experimenter can request the external system to send
the results to the sim ulator through Receive and Display Results.

43

4.1.2

N on-functional R equirem ents

The non-functional requirements of the sim ulator define th e constraints on th e func­
tionalities th a t the simulator provides [Sommerville, 2004]. I t is necessary to satisfy
these requirements in order to make the system usable and reliable. These require­
ments are summarized below.

1. The simulator shall support modifications in the microworld, including its re­
placement w ith a different microworld, w ithout th e need to change th e simula­
to r’s architecture.
2. The simulator has to provide message-passing mechanisms for direct communi­
cation between agents. In addition, its architecture shall allow the extensions
for supporting implicit communication through environment and shared storage
communication.
3. The simulator shall support a distributable architecture. In principle, the ar­
chitecture should allow the sim ulation to be distributed on a cluster. One of
the benefits of a distributable architecture is th a t one can increase th e simula­
tion speed through parallel execution. This increases th e overall usability of the
simulator.
4. The sim ulator’s architecture shall support interoperability w ith external pro­
grams th a t provide various m athem atical, statistical, optimization, and visual­
ization techniques (e.g. Octave, M atlab, etc.). This is needed in order to provide
the support for the processing and analysis of sim ulation results. It shall also be
possible for such external systems to invoke the sim ulator’s functionalities and
run simulation experiments as a p art of their processing or analysis tasks.

44

5. The simulator shall provide user interfaces th a t comply with the functional
requirements of the simulator. At a minimum, this includes a graphical user
interface (GUI) th a t allows interactive experim entation and a com mand-line
interface th a t allows batch-mode experim entation.
6. The simulator shall support interoperability with multiagent platform s and
agent reasoning engines. This can be used to allow the users of th e sim ulator to
use actual agent code and reasoning, rather th an its simulated representation,
whenever it is required. The purpose of this requirement is to allow a more
realistic behavior of agents as well as to ease th e transition tow ards an A IP
prototype im plem entation on a full m ultiagent software platform.
7. The sim ulator shall use an AIP representation technique that makes th e protocol
descriptions intuitively understandable, easy to implement, and am enable to
formal studies.

4.1.3

D om ain-specific R equirem ents

The domain-specific requirements specify w hat is needed w ith respect to th e appli­
cation domain th a t the simulator is intended for. These requirements explain the
constraints th a t reflect the fundam ental MAS and agent teamwork concepts and have
to be considered in the design and im plem entation of the simulator. In our case, as
we are interested in studies of helpful behavior in agent teamwork, the models of mul­
tiagent systems presented here are tailored to ease such studies. As th e sim ulator is
intended to be used as a design tool for agent interaction models, the focus on design­
ing the simulator shall be on agents interactions. In order to decrease th e influence of
other agent’s components on the evaluation of agent interaction models, assum ptions

45

and requirements on agent’s deliberation, reasoning, and any domain knowledge have
to be kept as minimum.

1. The simulator shall support a model of a m ultiagent system th a t includes rep­
resentation of agents, environment, and task structure.
2. The MAS model shall present a team of agents. For our purpose, we make no
assumptions about the team organization, subtasks assignment, and resource
allocation.
3. The MAS model shall represent individual agents. Such agents need to have
th e ability to perform actions, interact w ith other agents, and m aintain both
local beliefs, formed through perception, and context beliefs, formed through
communication with team members. In addition, for th e purpose of studying
helpful behavior, each agent shall have its distinct set of skills w ith respect to
the set of possible actions in the environm ent, creating diversity in the team
regarding the members’ specializations.
4. The environment itself shall provide communication facilities to agents as well
as a microworld model th a t can be used for studies of helpful behavior.
5. In order to use the environment for performance analysis of an interaction model,
the communication facilities shall allow modeling communication costs.
6. The microworld should follow simple rules th a t do not require any particular
domain knowledge or complex reasoning. T his makes it suitable for studies of
agent interactions and the required decision makings without th e need to deal
w ith any specific domain ontologies and agent programming.
7. The microworld shall define a set of possible actions, sets of rules for actions
and perceptions, and a source of dynam ism. Agents can perform actions on
46

th e environment according to the provided rules. Each action may require a
specific skill from agents. In addition, the environm ent should su p p o rt actions
th a t agents perform specifically to help another team member. T he environm ent
shall represent the dynamism th a t exists in real-world situations in a way th a t it
affects agents’ plans and actions. Different sources can be defined th a t generate
such dynamics in th e environment.
8. The microworld shall define a scoring metric th a t can be used for quantitative
evaluations of the system performance.
9. Different elements of the microworld shall be parameterized so th a t th e com­
plexity of the environment or the level of its dynamism can be modified during
experim entation by the system experimenter.
10. For our purposes, a team task structure shall be modeled. This task can be
decomposed into subtasks. Once the task is assigned to the team , each agent
in the team is assigned a particular subtask and has to complete it through
performing atomic actions on the environment. These actions are determ ined
through agent’s autonomous planning abilities and th e characteristics of the
environment. This brings about the need to allow an agent to perform its own
planning and possibly change its plan at any time.
11. The team shall be given a specific am ount of resources initially which can be dis­
tributed among agents. Agents spend their resources in exchange for perform ing
actions on the environment.

47

4.2

T h e S y ste m S tru ctu re

This section describes the high-level structural design of th e simulator th a t provides
the basis for its detailed design and implem entation.

E x tern al S y ste m

F ro n t e n d

R ea so n in g

S im u latio n
E ngine

MAS M o d el

E ngine

P a r a m e te r s M a n a g e r y
L ogger

Simulator

Figure 4.5: The high-level structure of the sim ulator and its external relations

At the top-level the simulator is decomposed into three main components: the
simulation engine, the M A S model(s), and the front end (Figure 4.5). T he sim ulation
engine controls the execution of the MAS model(s) and is responsible for coordinating
the course of simulation. A MAS model represents a model of a m ultiagent system
th a t would be used for simulation studies. The front end allows the user to control
the simulation process and the presentation of th e results. I t is also responsible for
48

allowing the user to access all of th e system functions specified by the use cases. Two
other components of the sim ulator are responsible for managing system param eters
and systems logs. These components are used by other components of the system.
The simulator provides the interoperability w ith other systems in two directions.
First, the simulator can be invoked by external systems. For example, another pro­
gram can control the simulator to autom ate creation and execution of a series of
experiments. In another case, the simulator can be em bedded within a system. Sec­
ond, the simulator can use external reasoning engines to allow agents to use more
sophisticated agent reasoning. T he details of such interoperabilities are discussed
throughout this chapter.
The sim ulator’s architecture is designed to provide loosely coupled components.
The benefit of this design is th a t it allows independent development of different com­
ponents and simplifies its maintenance. In particular, different MAS and microworld
models can be implemented w ithin th e simulator; as long as their designs comply
w ith some general assumptions, there is no need to modify th e other com ponent of
the simulator (e.g. the simulation engine). In the rest of this section, we describe the
internal structure of the top-level com ponents and outline th e interfacing assum ptions
on which their designs are based.

4.2.1

The Sim ulation Engine

The simulation engine is the central component of the simulator. It is designed to
control the execution of th e model and to coordinate the operations of different com­
ponents of the simulator. Its design is based on th e assum ption th a t th e activity of
each agent team can be viewed as a cooperative game th a t proceeds in discrete syn49

S im u latio n E ngine

Average
Team Score

E x p e rim en t H a n d ler

Team Score

Run H a n d ler

Game
Score

M atch H a n d ler

R ound H a n d ler

Figure 4.6: The simulation engine
chronous rounds, is guaranteed to end after a finite num ber of rounds, and a t th e end
produces a final team score th a t indicates th e level of th e te am ’s success in pursuing
its task. The team ’s task involves a number of variable parameters whose values can
be randomly generated or specifically set by th e experimenter. An instance of the
game, with a particular selection of task param eter values, is called a match.
The simulation engine executes simulation experiments. An experiment may in­
volve a number of agent team s th a t play their matches concurrently. An experim ent
run consists of the concurrent execution of a fixed number of matches, w ith varying
task param eters, by each agent team and the averaging of each te a m ’s scores. An
experiment consists of a number of runs. T h at number m ust be sufficiently large so
as to guarantee the desired level of statistical significance of th e averaged team scores.
The experiment handler is responsible for managing the execution of an exper­
50

iment. This includes dealing with param eters, activating runs, and calculating the
final team score. This module is activated by th e front-end of the sim ulator and at
the end produces the average team score over multiple runs.
The run handler manages the param eters and th e execution of each run of an ex­
periment. Once activated by the experim ent handler, it generates a new com bination
of the environment settings and starts the simulation process. For each run, there
is a score associated with the team which is passed to the experiment handler. The
run handler activates the m atch handler for a fixed number of times defined by the
experiment setup.
The match handler is responsible for the concurrent execution of th e games played
by individual teams. At the beginning, it initializes each team and th e environm ent
for a new game. At the end of th e game, it reports the team score of each team for
th a t game to the run handler. T he game is played in discrete steps until it is over.
For every team, each step is controlled by th e team ’s round handler explained next.
The round handler executes the MAS model for one step in the game. In each step,
this handler activates different handlers to cause agents to perceive, send, receive, and
act. This module ensures proper synchronization between these activities.

4.2.2

Service C om ponents

P aram eter M an agem en t

The simulator uses a central param eter repository to store and manage all th e ex­
perim ent configurations and param eters of the simulation. Each com ponent of the
51

simulator can use this repository to define, set, and read parameters. For each exper­
iment, the user can set these param eters through this component. This includes all
the param eters of the simulation engine, th e environment, agents, interaction models,
etc. Different entities can access their required param eters through this interface.
For easier identification, disambiguation, and safety, param eters are defined using
a namespace convention. The entity th a t th e param eter belongs to can be specified
as prefix in the name of th e param eter. For example, the cost of a unicast message
th a t is used by th e communication module can be prefixed by comm and be defined
as “comm.unicastcost” .
One of the main advantages of this com ponent is to allow better interactive ex­
perim entation. Changes to any param eter shall be done through this com ponent and
whenever, at runtime, any component needs to access the value of a param eter it is
done through this component. The front end can perform changes to th e model a t
runtim e w ithout the need to restart the simulation.

L ogger

The logger component collects and manages all the logs th a t other com ponents of
the simulator generate. Such logs can show the progress of simulation, or they can
represent the internal state of an agent in its decision making process. Logs can be
helpful for debugging agent interaction models and further analysis of th e simulation.
They can be set to be recorded in a file or be redirected to the GUI for user access.
Also, logs can be classified into different levels, which can be individually set by the
user to be recorded or displayed.

52

4.2.3

T he Front End

The front end is responsible for providing th e experim enter’s access to th e sim ulator.
On the one hand, the user may directly interact w ith th e simulator to design and
perform experiments and access the results. On th e other hand, external program s
may use the simulator to perform experiments and process th e simulation results.

E xperim ent

F ront e n d

Setup

Configuration M o d u le s

P aram e ters
M anager

Q
CLI

GUI

U se r/
External
System

U ser

S im u latio n
Engine

MAS M odel

Logger

Figure 4.7: The Front-end com ponent
The internal structure of the front end is presented in Figure 4.7. It consists of a
configuration module, a graphical user interface (GUI), and a command line interface
(CLI). The configuration module enables th e experim enter to create th e experim ent
setup required for simulation. The graphical user interface provides a graphical and
interactive interface of the functionalities of th e sim ulator to its users. T he CLI allows
the simulator to be invoked from the com mand line.
The configuration module sets the param eter values for th e simulation. This in53

eludes simulator param eters, interaction model param eters, and the microworld pa­
rameters. O ther components of th e front end use this component to set up experi­
ments.
The GUI provides an interface for interactive user access to the simulator. T he user
can create and m anipulate experiment setups interactively and use th e visualizations
provided by the GUI to get feedback from the simulation model.
The CLI provides a non-interactive access to th e simulator. Using CLI, th e simu­
lator can be invoked from command line and the experim ent setup and the sim ulation
results can be set to be read from or saved to files. The GUI is suitable for interactive
experimentation by researchers while the com mand line front end is suitable for batch
mode operations in text-based environments or where interactive experim entation is
not required.

S im u la to r’s In tero p era b ility w ith E x tern a l S y ste m s

The simulator is designed to allow interactions w ith external systems. T he interaction
can be done in situations where the sim ulator is a client of an external system, the
simulator is a server for an external system, or the simulator interacts bilaterally w ith
an external system. This can be used to autom ate experiments and further analyze
the results by other systems and increase the overall functionality of bo th systems.
The general structure of invoking the simulator from external systems, and vice versa,
is represented in Figure 4.8 and is described as follows.
In order to work with each external system, based on its structure and require­
ments, an adaptor can be developed to provide th e interface between th e sim ulator

54

E x p e rim en t
S e tu p

Sim ulator's
F ront e n d

<1

S im ulation
R esults

k-

A d ap to r

r

t

External System

C o n tro l

►

D ata

►

Figure 4.8: The interoperability of the sim ulator with external systems through its
front end
and th a t system. The adaptor is responsible for th e requirements of b o th systems and
translates their interactions and data. Such an adaptor can interact w ith th e simula­
tor through its front end. Experim ent setup can be stored in a file by th e ad ap to r for
sim ulator’s use. Also, the simulation results can be stored in a file so th a t they can
be processed by the adaptor and translated to th e external system’s input format.

4.2.4

T he M A S M odels

The MAS model component represents a m ultiagent system. This model is used for
simulation and includes representations of the agents, the team context, th e commu­
nication module, and the microworld (Figure 4.9). In addition, the sim ulator supports
simulating multiple MAS models concurrently. First, the structure of a single MAS

55

Front en d

MAS M odel
Team Context

41
*5b
LcLl
c
o
C : .

4-A
c
<u
bO
<

O O O
'

■■

4-»
c
QJ
bo
<

■".A ~

%A

"■ST:
_re
3

'E n v iro n m e n t

E
«75

Communication Module
Microworld

Figure 4.9: A MAS model within the simulator
model and its components, including agent, team context, th e communication m od­
ule, and the microworld, th a t represents a single team is described. Later, concurrent
architecture of the simulation of multiple MAS model based on the presented single
MAS model is explained.

A gent

The simulator employs a simple agent architecture which is built to su p p o rt the
execution of agent interaction models (Figure 4.10). The agent is activated by the
simulation engine and is connected to the microworld and the communication module
within the MAS model. The agent architecture consists of a belief base, a belief

56

A gent
P e rc e p ts

Belief U p d a te r

R easoning

(U

o
o
o€

03

oO
3',
3
:

In te ra c tio n M o d u le

c. •
3

oQJ
r-¥
o

AlP's
FSM

FSM
E x e c u to r

. 3 -/

O
Q_

S e n d MSG

o’
m
3
OQ.

■; 3

3*

R ec e iv e MSG

K —

c_
Q
J
rf

ro

M e s s a g e H andler

—

A ctio n

A c tu a to r

C o n tro l

►
D ata

►

Figure 4.10: The agent architecture of th e simulator
updater, a reasoning component, an interaction module, and an actuator com ponent.
The belief base maintains all the beliefs of the agent. A gent’s beliefs can be divided
in two groups: local beliefs th a t are generated based on agent’s percepts, and context
beliefs th a t result from the agent’s interactions w ith the rest of the team . T he belief
updater component receives th e percepts from the microworld and updates th e belief
base and forms local beliefs. The interaction module also updates th e belief base and
57

forms context beliefs based on the incoming messages.
The reasoning component allows the agent to deliberate about its current situation
and make decisions. The agent uses its reasoning abilities for a number of different
purposes. First, once a subtask is assigned to an agent, th e agent can use its reasoning
component to create a plan in order to achieve th e subtask. Second, in each round
of the game, th e agent can reason whether to initiate an interaction model. Also, the
agent can decide whether to engage in interactions initiated by other agents. Third,
during executing interaction models, the agent can use its reasoning abilities to decide
about its course of action in the protocol decision points. Finally, if th e agent can
choose dynamically which interaction model to use, the reasoning com ponent will
perform the deliberation.
The interaction module is a key component of our agent architecture. It contains
a specification of an AIP, where th e AIP is defined as a finite state machine (FSM); an
FSM executor, which can execute the A IP ’s FSM; and a message handler, which allows
the agent to create, send, and receive messages using the communication m odule of
the MAS model.
The actuator component performs th e chosen action, which is specified as a result
of agent’s reasoning and interactions, using the interface provided by th e microworld
(explained later in this section).
The reasoning component of the agent architecture supports reasoning th a t can
be specified using regular im perative program m ing languages. However, it does not
provide built-in support for agent-oriented programming languages and reasoning.
The design cases considered in this thesis th a t use the framework need simple rea­
soning th a t is implemented using an im perative programming language. However,

58

some research may require the use of an agent-oriented language to perform more
realistic reasoning. The agent architecture supports th e use of external agent reason­
ing engines in order to enable agents to execute complex reasoning im plem ented in
an agent-oriented programming language. This feature is built as an option in the
simulator so th a t one can enable it when it is needed for a particular research problem.

MAS Platform
{Reasoning Engine)

S im ulator's A gent

A g e n t Code

Figure 4.11: Using an adaptor to connect to external reasoning engines

The sim ulator’s agent architecture can connect to an external reasoning engine
(found in MAS platforms) using an adaptor (Figure 4.11). The purpose of using an
adaptor is to translate the interactions between sim ulator’s agent architecture and the
reasoning engine. As long as such adaptor complies w ith th e interface th e sim ulator’s
agent needs, one does not need to modify the sim ulator’s architecture in order to
develop a new adaptor for a reasoning engine. This allows using different reasoning
engines w ithout being restricted to a particular one and a t the same tim e providing
the same interface to the agent architecture of th e simulator. As a result, one can
implement a specific adaptor for a reasoning engine he wishes to use w ithout modifying
the simulator.

59

T eam C o n te x t

The team context module represents an agent team in a MAS. Agents in the same
team are situated in the same environment and are able to interact w ith each other.
The team context module conceptually holds th e agents together by m aintaining
team -related information such as team ’s task structure, resources, and perform ance
metrics.

T h e C om m u n ication M o d u le

The communication module provides th e facilities th a t are needed for agent com­
munication. The current version of th e sim ulator provides an im plem entation for a
message passing system to support AIPs. In addition, the architectural su p p o rt for
a shared storage module (th at can be used to implement a blackboard system ) and
communication through the environment is discussed here.
The message passing module consists of a message stru ctu re and a direct commu­
nication network between agents. In order to support AIPs, agents shall be able to
create and recognize different types of messages. In addition, they shall be able to
send messages directly to other agents or broadcast a message to all team members.
In the following, the details of the message stru ctu re and the communication network
is described.
A message is defined by the structure represented in Figure 4.12. Each message is
built based on a set of fields in the form of < key, value > . T he first th ree fields are
m andatory as they identify its sender, receiver, and the message type. The sender and
receiver fields contain the identification of agents involved in th e message passing. T he

60

M essage
Sender
Receiver
MSG_Type
k ey

va lu e

k ey

va lu e

k ey

va lu e

Figure 4.12: The message structure
message type specifies the type of th e message among all possible types of messages
th a t a protocol includes. This can be specified by the A IP designer. The rest of the
fields can be used as they are needed based on th e message type constraints. In order
to have the least assumptions on th e ontology and language, the contents of th e key
and value can be anything th a t can be encoded in a string.
Agents in the same team can exchange messages through a complete synchronous
network with single-message unidirectional channels (as described in [Lynch, 1996]).
In order to send a message from agent A to agent B , A has to put the message on the
channel th a t exists between A and B . Afterwards, B can access the message once it
needs it. In a similar manner, an agent can broadcast a message by p u ttin g it to all
the channels connecting it to other agents.
A typical blackboard system consists of three m ain components: a group of knowl­
edge base, the control unit, and th e shared storage (blackboard). Applied to a MAS,
each agent acts as a knowledge base, carrying special expertise to solve the given prob­
lem. Agents have to be able to post directly to th e shared storage and to retrieve any

61

Blackboard
AgO

Shared

A gl

Storage

Control
Agn

Figure 4.13: The architecture of a blackboard for the simulator
desired information from it. In addition, they may also receive notifications from the
blackboard’s control system. This overall architecture is represented in Figure 4.13.
The current architecture of the simulator supports incorporating th e blackboard
design described above. Agents can directly send messages to the blackboard, con­
tributing to the common knowledge in the shared storage in the same m anner as
they exchange message to each other. Notifications from th e blackboard can be sent
through messages as well. Information retrieval can also be implemented through a
pair of messages being sent and received.
The support for environment mediated communication shall come from b o th the
environment and the agent model. A proposed design for supporting such commu­
nication by the simulator is represented as follows. Implicit communication can be
done thorough changing the environment. Agents can create and use cues in th e en­
vironment in order to implicitly communicate with each other and coordinate their
activities. The environment should support creation of such cues. T he sim ulator de­
sign supports such environment characteristics. In a finite gird-based environm ent,

62

each field (cell) can hold a number of different cues. Each cue would be implem ented
by an object and might have different attrib u tes associated with it.
In this model., one agent’s modifications in the environment becomes another
agent’s cue. An agent must be able to (1) perceive the cues on th e environment,
and (2) make modification in the environment (create cues) through perform ing ac­
tions. In the sim ulator’s design, agents are allowed to perceive th eir environm ent,
this includes the properties of individual cells which can include a list of all possi­
ble cues. Also, specific actions can be defined which make such modifications in the
environment by creating cue objects.

T h e M ic ro w o rld

The microworld, in this version of the simulator, models a cooperative game, played
in discrete steps. The game is played on a rectangular board of colored cells. It is
inspired by th e Colored Trails (CT) game [Gal et al., 2010], designed and im plem ented
independently. It models a dynamic environm ent which is designed to be used for
studies of helpful behavior.
The microworld component contains a num ber of different modules as demon­
strated in Figure 4.14.

These modules interact with each other and provide the

required functionality of the microworld. T he microworld provides interfaces to the
MAS model and the simulation engine to access and control these modules. The
microworld modules are described as follows:

B o a rd The board is a rectangular grid of colored squares and is where agents are
situated. It allows agents to perform their actions using its act interface.
63

Percept ^

A

Team Score

M ic ro w o rld

Percept
G enerator

visibility
Rules

rf

Act

!K-

Board

Metrics

Dynamism
G enerator

P e rfo rm a n c e
F u n c tio n s

D ynam ic
M o d els

GUI

B oard S ta te

♦

*

Fire Event

GUI

C ontrol
D ata

Figure 4.14: The structure of microworld
P e r c e p t G e n e r a to r The microworld generates percepts per each agent.

D uring

the perception stage, a set of percepts generated by this module is passed to
each agent. These percepts are generated based on th e visibility rules of the
microworld allowing the modeling of scenarios with partially observable envi­
ronment.
G U I The microworld can supply an im plem entation of a graphical com ponent th a t
can be displayed in the GUI front end.

This component provides a graphi­

cal representation of the microworld including environment, agents, and task
structure.
M e tric s The microworld provides metrics for team s regarding their perform ance and
other qualitative measures. These rules for measuring team perform ance are
specified separately.

D y n a m ism G e n e r a to r T he microworld models a dynam ic environment. Therefore,
the state of the environment, in particular the board, is subject to stochastic
changes. These changes are generated based on a model of dynam ism supplied
by the user. In addition, th e microworld allows the simulation engine to control
the generation of these changes by firing events.

C o n c u r r e n t S im u la tio n o f M u ltip le T e a m s

In order to simulate multiple team s concurrently, the sim ulator needs to conduct the
exact same experiments on different MAS models. Each MAS model m ight use a
different interaction model or th e same interaction model w ith different param eters.
Constructing the same experiments for each MAS model is necessary in order to ensure
the fairness of the comparisons and validity of the studies. It also helps in getting early
feedback from experiments by allowing th e user to access th e simulation results from
each simulation step for all MAS models or observing the behavior of different MAS
models on the same phenom ena a t the same time. T he dynam ic environment requires
special support from the MAS models in order to replicate th e same experim ent.
The dynamic characteristic of th e environm ent brings a challenge in replicating
experiments. While the initial conditions of each MAS m odel’s environment should be
the same, the dynamic patterns of th e environm ent over tim e should also be exactly
reflected in each MAS model’s copy of environment. There are two types of sources of
the environment dynamics: the ones th a t are beyond th e control of agents (external)
and the ones th a t are direct or indirect result of agents actions (internal). Based on
this distinction, an architecture is designed to support constructing th e sam e dynam ic
patterns in each MAS model’s environm ent as follows.

65

MAS
Model A
( Team A)

MAS
M odelB
(T e a m B)

MAS
M odel X
(TeamX I

A ugm ented
E n v iro n m e n t

A ugm ented
E n v ir o n m e n t

A ug m ented
E n v iro n m e n t
• ••

Local
E n v iro n m e n t

Local
E n v ir o n m e n t

Local
E n v iro n m e n t

Global E n v ir o n m e n t

Figure 4.15: The board architecture for parallel MAS models, each representing a
different team . The global environment is perceivable by agents from all MAS models.
Each MAS model has a distinct layer which m aintains the MAS specific information.
Agents have access to both layers through an augm ented board which is a virtual
layer combining two other layers.
Conceptually, th e environment and its features are broken into three layers. A
global environment layer, a local environment layer, and an augmented environm ent
layer (Figure 4.15). The global environment consists of all th e common features of the
environment which can be shared among the MAS models. T his includes any external
events th a t might occur in the environment th a t are beyond th e control of agents and
independent of their actions. No m atter how agents behave in the environm ent, these
events have their own effects. As a result, each MAS will face the sam e p attern of
events regardless of the interaction model they employ.
Each MAS model is given a local environment which is specific to th a t MAS. This
layer of environment handles all the features th a t belong to the MAS model. For
instance, the outcomes of agents’ actions are handled in this layer of the environment.
66

However, agents do not have access to th e local environm ents that belong to other
MAS models.

By combining the first two layers, a th ird layer is created th a t is

called the augmented environment layer. T he environment represented by this layer
contains the information from both the global environment and the MAS m odel’s local
environment, and it is w hat the agents perceive. While the augmented environm ent
contains the perceptions propagated from bo th other layers and is used for agents’
perceptions, the outcomes of agents’ actions are only reflected on their own MAS
model’s local environment. In this way, each MAS model has an identical yet isolated
environment which is subject to the same external change patterns.

An example

of applying this architecture to a grid-based environment in which agents perform
implicit communication through environm ent is illustrated in Figure 4.16.
The concurrent simulation of multiple team s is supported by the sim ulator’s MAS
model architecture as follows. For each team , there is a separate MAS model providing
team, agents, and communication module representations. In addition, each MAS
model includes a microworld. However, in order to replicate the same experim ents,
and the same environments, for each team , th e microworld of each MAS model need
to share parts of their state. This belongs to the state of th e board in which agents
would be situated. Thus, the board module of th e microworld is broken into two
layers: a global board in which the common properties of th e board th a t are going
to be shared among multiple MAS models are represented; and a local copy of the
board for each MAS model, excluding th e common properties and only m aintaining
team-specific properties (Figure 4.17).

67

percept"

Augmented Environments

E vents

Events

Local Environments

Events

Global Environment

Figure 4.16: Parallel MAS models using a grid-based environment. T he global board
consists of colored cells. An event in such a board could be a change in the cell colors.
Each local board maintains the position of agents and other results of agents’ actions.
In general, any property of th e environment th a t is th e result of agent’s actions, or can
be affected by agents’ actions is represented in the local environment and any other
properties th a t are not affected by agents are represented in the global environm ent.
The augmented environment provides a unified view of both layers.

4.2.5

D istributed Sim ulation

The proposed simulator uses a distributed simulation architecture (as shown in Fig­
ure 4.18). In this architecture, the distribution is based on executing different runs of
the same experiment on different nodes of th e network. In other words, as for each
68

MAS Model n

C om m unication M odule

Communication Module

Simulation Engine

Simulation Engine

MAS Model 1

n
ooo

lo cal Board 1

-

;

lo c a l Board n

Global Board

Microworld

Z J 'h z
Figure 4.17: M ultiple MAS models and the shared microworld

Workstation
M ain. Front-end

Cl

Network

A.

JZL

j 5_
Dist. Front-end

a

Dist. Front-end

Dist. F ront-end

a

$

I

ooo
a

Sim ulation Engine

•

O

Sim ulation Engine

a

Sim ulation Engine

Figure 4.18: The distributed simulation architecture
experiment there are a large number of runs needed, these runs are distributed to
different instances of th e simulator on different nodes of a network. T he rationale

behind this distribution scheme is th a t these runs are independent from one another.
Therefore, there is no need for synchronization and communication between instances
of the simulator. As a result, this scheme provides a simple and effective distribution
architecture for the simulator.

4.3

T h e S y stem B eh a v io r

In this section, the behavioral aspects of different com ponents of th e system are ex­
plained. However, this only includes th e com ponents whose behavioral aspects play
im portant roles in the simulation process.

4.3.1

The Sim ulation E ngine

The simulation engine design is based on sim ulating time as discrete values. Accord­
ingly, the simulation model is represented as a discrete system whose sta te transitions
occur at discrete tim e steps. The sim ulation model supported by this framework is a
cooperative game which can be played in discrete steps by different m em bers of the
same agent team. The course of th e game, from its beginning to its end, is performed
in a match. T he game starts by assigning a task to the team and is played in multiple
rounds. In every round, each agent can perform one action on the environm ent. These
rounds are repeated until, based on the rules of th e game, th e game is considered as
finished. The framework also supports modeling a long-term memory for th e agents
involved in th e game through allowing each run to consist of multiple matches and
allowing the agents to retain some state inform ation from completed m atches within
the same run. The behavior of the simulation engine is explained below.
70

E xperim ent

\k
^ n itia liz e E x p e rim en t^

\/
<
\

!

"D
o>
*o
o

8

1
o>
o

N
s
<?

£

[No m o re rur s a r e n e ed e d ]

\/
^ G e t A verage T eam ScorfT)

Figure 4.19: T he mechanics of the experiment
At the beginning of an experiment, the Experim ent Handler initializes the simu­
lation engine and the model by using th e configuration specified in th e experim ent
setup. Next, based on the specified number of runs for th e experiment, it activates
the run handler. At the end of an experiment, it calculates the average score of the
team over all runs (Figure 4.19).
After its invocation by Experim ent Handler, th e Run Handler first initializes the
microworld and the agents for a new experim ent run. Next, it activates th e M atch
Handler for executing a new game. After th e game is over, it checks w hether more
matches are required. If yes, it will reactivate the M atch Handler. Otherwise, it will
calculate the average team score for all games the team played in the ru n (Figure 4.20).

71

Run

M atch

[No m ore m atches are needed]

G et Average Team Score

Figure 4.20: The mechanics of the run
The M atch Handler starts each match by initializing th e param eters of different
parts of the model for a match. Next, it starts executing each round by first firing the
global events of the environment (defined in the microworld component). A t the end
of each round, the Match Handler checks for each of the concurrently executing team s
whether, based on the rules of the game, the game is over or not. If the game is not over
yet, it will execute another round of the game, otherwise it will term inate th e game
and calculate the team ’s score for th a t game through th e microworld (Figure 4.21).
T he invocation of the Match Handler term inates when th e matches of all team s are
completed.
The game is played in synchronous cycles called rounds.

As dem onstrated in

Figure 4.22, each cycle starts with agents perceiving their environment. T he percepts
are generated by the microworld per each agent and are passed to them individually.

72

M a tc h

Globa! Environment Events

^Round^^

[Game IS finished]

Calc Team Score

Figure 4.21: The mechanics of the match
Following the perception, agents enter into a number of communication cycles where
they can interact with each other through message passing. A communication cycle
starts by a send phase and ends with a receive phase. T he alternating send-receive
cycles repeat until agents decide, as dictated by the protocol they are employing,
th a t there is no more communication required. Finally, each round ends w ith agents
performing actions (if any). Each stage occurs for all the agents within th e sam e team
concurrently. The synchronization of agents’ activities is represented in Figure 4.23.

73

Round
^

Perceive ^

^

Receive ^

[No m ore com m unication is need ed ]

Action

Figure 4.22: The mechanics of the round w ith message passing cycles

4.3.2

T he Front End

GUI

The Graphical User Interface (GUI) front end allows an intuitive access to th e simula­
tor and provides various unique features th a t facilitate the stu d y of interaction models
through the simulator. T he main window of the GUI is represented in Figure 4.24.
In response to the functional requirem ents of the system, th e fundamental goals of
designing the GUI are summarized in providing the following functionalities:

• Experiments setup

74

Direct Communication Cycle

t
AgO: S e n d Q

\
\

AgO: R ec eiv e Q ^

A g 1 :S e n d ( )

\

Mieroworfd:
\
GenPercepts(AgO) /

Microwatt:
\
GenPerce pts(Ag1) ?

M icrowatt:
\
GertPercepts(Agn) /

AgO: Perceivef) ^

Ag1: PerceiveQ ^

Ago: Perceive() ^

AgO: ActQ

A g1: ActQ

A go: ActQ

A go: S e n d Q

'

'

A g l: R e ceiv eQ \

Agn: R e ce iv e Q

<§>

Figure 4.23: How agents are handled in different stages of each round
• Experiments control
• Online simulation
• Dynamic experim entation
• Visualization
• Statistical analysis

The GUI consists of toolboxes th a t support different aspects of th e sim ulation,
namely: the control box, the console, the visualization box, and the experim ent setup
box. The functionality of each of these components is explained below.
T he control toolbox (Figure 4.25) allows the user to control the sim ulation. It
provides basic s ta rt/sto p functionalities as well as settings for running th e sim ulation
75

S im ple S im u la to r
Experim ent S etu p

Visual In sp e c to r

P a r a m e te r s ; Experim ent S ettin g s

C h art | C am e;

D isturbance Level Variations
{P aram eter

V alue

-env.gridsizeX
env.gridsizeY
a g e n t.h e lp o v e rh e a d
-en v .d istu rb an ce
Iteam .unicastC ost
im ap .req u estT h res
[te am .h elp o v erH ead

10
10
5
0.0
5
300
5

85,000

so,ooo
75,000
70,000
55,000 ■
60,000
55,000 ■
£j 50,000 ■

env.disturbance:
!
i "

i

35,000 •
30,000
25,000

90
............... r T " \
......... - ...........
NK
i
i i i i i
i i \ i

(■ sto p ) ®

-

20,000
15,000 •

C o n t r o l .......................................................................
jS > S ta rt) 1W t S tep

-

J j 45,000 ■
E 40,000

10,000
5,000

Loop

0
1

C l Logs on

2

3

4

5

6

7

Experiment#
S ta te : {Working.,.

[

nqhelp |

C onsole
| Results Logs ’ Errors I
182246...
7 ? 501
i?c77o
i 73355
7 ! 103
169578
|68289
67118

Figure 4.24: The main window of th e sim ulator’s GUI
, C o n tro l

-........................................................................

P > S ta r t i

S te p I | H

S to p | m

L oop

[ j L ogs on
S ta te : [W orking...

Figure 4.25: The control toolbox
in an infinite loop.

76

8

9

10

Console
R e s u lts

L o g s E rro rs

•0 .00, 86 9 2 2 ,8 5 3 1 6 ,8 5 5 4 0
;0 -05, 8 3 6 1 7, 801 0 8 ,8 1 7 9 5
.0 .10, 81 0 8 2 , 7 5 9 4 1 ,7 9 0 4 8
-0 .15, 7 9 1 8 9 , 72541,76921
"<3.2 0 ,77 4 7 7 , 5 9 3 9 1 ,7 4 9 7 9
:0 .25,? 6 2 7 5 ,569 4 7 ,7 3 5 5 4

Figure 4.26: T he console toolbox
The console toolbox (Figure 4.26) provides the means to access th e raw results,
agents’ logs, and the errors.
Visual in s p e c to r C hart j Garris

D isturbance Level Variations
•-

TG.QCXm ,
50,0(0

£§ 5O.QOn
?

3CM*«

;

Vfc

2’VXO j

in,r«p *

Experiment#
n o h s .p I

Figure 4.27: A chart created in the visualization toolbox

The visualization toolbox provides th e support for drawing charts, dynamically,
in user-defined ways1. Examples of different charts are dem onstrated in Figure 4.27.
The experiment setup toolbox allows the user to set up experiments and modify
any param eter th a t is defined w ithin th e system. The first tab of th e toolbox has
the controls for setting up experiments. In the second tab , the user can ad ju st any
param eter th a t is defined in th e system (Figure 4.28). This list is interconnected to
the simulation engine’s param eter interface. This makes any changes in th e list to be
immediately applied to the (running) system. This unique feature allows dynam ically
1The simulator uses the charting library JFreeChart (http://jfreechart.org) for drawing charts on
the GUI.

77

E x p e rim e n t S e tu p
P a r a m e te r s . E x p e rim e n t S e ttin g s .
- iL i
jP a r a m e te r

V a lu e

e n v .g rid siz e x
jenv.gridsizeY
ja g e n t.h e L p o v e rh e a d
ie n v .d is tu rb a n c e
ite a m .u n ic s s tc o s t
im a p .r e q u e s tT h r e s
I te a m .h e lp o v e rH e a d

10

is

10
5
0.0
5
300
5

e n v .d is tu rb a n c e :
90
i—

-— - ...~ * ~ --- ---------< P
1
1 1 1 1 1 1 1 I 1 ! i

Figure 4.28: The param eter editor in the experim ent setup toolbox
studying th e effect of individual param eters w ithin an experiment th a t is already
running.

CLI

In the Command-Line Interface (CLI). the input param eters can be read from files
or from the standard input. The results also can be w ritten into a file or ju s t printed
on the standard output. This version of th e front end can be easily used to support
functionalities such as distributed sim ulation or interoperability with other programs.

78

4.3.3

The M A S M odels

A g en t

T he agent architecture presented in this framework enables the basic behavior of
agents such as perceiving th e environment, reasoning, communicating, and perform ing
actions. However, the detailed mechanisms of the ag en t’s behavior are left unspecified
so th a t they can be defined based on specific requirements of a research problem. In
particular, the agents within the current version of th e framework are expected to work
as a team in such a way th a t they try to maximize their team benefit rath e r th a n
their own benefit. They are designed to support interaction protocols for perform ing
helpful behavior and are capable of modeling different types of reasoning (e.g. rational,
empathic, etc).

C oncurrent S im u lation o f M u ltip le T eam s

The concurrent teams simulation model easily fits into the general sim ulator architec­
ture (Figure 4.29). At the beginning of every m atch, the events th at affect the global
environment are fired. These events cause the global environm ent to change in certain
ways. Then, in a (pseudo) parallel setting, th e control is passed at the sam e tim e to
each MAS model, which starts by firing local events in its local environment followed
by a new round of the game. These local events affect the local environment of each
MAS model individually. Using this m ethod, it is guaranteed that all MAS models
face the same global events in their environm ent a t each round while they are allowed
to have their local events. It is w orth mentioning th a t, in this architecture, from the
agents’ perspective there is only one environm ent and th e layers are invisible to the

79

M a tch (W ith Parallel T eam s)
Initialize Match

Global Environment Events

MAS Model A: Local
Environment Events

MAS Model B: Local
Environment Events

MAS Model X: Local
Environment Events

MAS Model A: Round

MAS Model B: Round

MAS Model X: Round

[G am e IS fin ish e d ]

V
^ C a lc T eam S c o re ^

Figure 4.29: Handling multiple MAS models in parallel in each match.
agents.

4.3.4

D istrib u ted Sim ulation

The simulator provides scalable sim ulation by using a distributable sim ulation archi­
tecture. Speed and valid results are the two main requirements of this sim ulator.
However, precise simulation dem ands a great am ount of com putational power which
reduces the speed of the simulator. In order to overcome this barrier and achieve
both of the mentioned objectives, a distributed simulation mechanism is designed and

80

provided with the simulator.
The main factor th a t affects the speed of the sim ulation is the large num ber of
runs th a t are required for more (statistically) significant simulations. As th e size of
the sample the sim ulator is generating is always less than th e size of th e population
(all possible combinations of settings), there is a n atural sampling error associated
with each experiment result. This error can be reduced by increasing th e sam ple size
which, in our case, is the num ber of runs. For instance, one might need to repeat the
same experiment for more than 25000 times in order to get a reasonably small error.
The im pact of this factor can be reduced by breaking down the runs th a t are being
repeated, and run them in parallel. At the end, by aggregating the results, one can
achieve both the performance and th e precision required.
The simulator is designed to support distribution of the simulation load on a Linux
cluster in order to achieve scalability. Based on th e nature of these sim ulations and
factors th a t affect the performance, the main ideas behind the distributed simulation
design are as follows. As the runs of the same experim ent do not depend on each
other, they can happen in parallel. While th e sim ulator runs as a single process to
simulate each instance, each of these instances can be run in parallel w ith more th an
one simulator process. This process can be replicated on a Linux cluster as follows.
A copy of the simulator which is setup to be used in batch mode would be available
on each node of the Linux cluster. T he nodes of th e cluster are able to communicate
with each other, for exchanging both d a ta and commands, using th e Secure Shell
(SSH) protocol. The SSH allows sending remote commands and making basic remote
I/O between different network systems. A main front end is executed on th e m aster
node, where th e user can set up, run, and analyze the experiments. T he rest of the
system is invisible to the user. The whole process is done in three steps (Figure 4.30)

81

as follows:

Setup

C om putation
Node

Partial
Result

Setup

C om putation
N ode

Partial
Result
M ain N ode

Main Node

Setup

C om putation
N ode

Partial
Result

Time

Figure 4.30: The three steps of distributed simulation.

1.1. The m aster node, which only runs a front end, distributes the experim ent setup
file to each node within the cluster. In the setup, each node is set to ru n for a
fraction of the total required number of runs. If N is th e number of nodes and
r is the to tal number of required runs, then each node is set to run

times.

1.2. The m aster node remotely executes the sim ulator instances on each node of
the cluster and waits for them to finish. It also creates a Unix pipe for each
connection which can be used to retrieve inform ation from each node.
2. Each node starts executing the simulation.
3.1. Upon generating a new p artial result each node writes the results on its stan d ard
output which is redirected to the m aster node through the pipe.
82

3.2. The front end in the m aster node gathers all th e results, aggregates them , and
displays them to the user as if they were all generated in the same machine.

The overall characteristics of this approach is summarized in the following:

• reliability : A failure in any node has a limited effect upon the sim ulation process
as it just misses a group of runs and thus ju st reduces the precision.
• flexibility: This distributed architecture can be set up to run on any Linux
cluster with potentially heterogeneous processor hardware.
• cost-effectiveness: As this design requires no synchronization and communica­
tion between nodes, it could be used on any high speed computer network and
does not require the more expensive, low-latency network infrastructures.
• simplicity: The internal architecture of the sim ulator does not need to be
changed in order to be used in this model.

4 .4

In sta n tia tio n o f th e G en eric S im u lator

Specialized simulators for studying specific classes of A IPs can be instan tiated from
the generic simulator architecture and MAS model, presented in this chapter, by
incorporating the models of th e desired A IPs as well as a customized MAS model.
In the next chapter, the approaches to the modeling of AIPs and MAS are ex­
plained. In particular, a common microworld model for the studies of helpful behavior
in agent teamwork th a t can be incorporated in the framework is introduced. In order

83

to present the framework in more concrete terms, as well as to evaluate its usefulness,
we describe two separate simulators th a t have been created using th e framework for
our studies of two classes of AIPs for helpful behavior in teamwork. C hapter 5 presents
the MAS and AIP models th a t are used to build those simulators and C hapter 6 the
experiments th a t has been conducted using them.
The examples presented in the next two chapters are th e test cases for evaluating
the proposed framework and its flexibility and usability for instantiating specialized
simulators for different classes of A IPs and conducting experiments w ith them .

84

C hapter 5

M od elin g for S im u lation

This chapter first presents the framework’s approach for modeling agent interaction
protocols in Section 5.1. Next, Section 5.2 presents the modeling of a m ultiagent
system in the framework by elaborating a common world model that is built to support
our research on helpful behavior. Sections 5.3 and 5.4 present the specializations of
this world model th a t lead to two separate simulators, each designed for studying a
different class of helpful behavior AIPs.

5.1

M o d elin g o f In tera ctio n P r o to c o ls

In this section, I explain how one can model agent interaction protocols w ithin the
framework.

85

5 .1 .1

R e p r e s e n tin g P r o t o c o ls

Following one of the common techniques in protocol specification (Section 2.4), we
represent agent interaction protocols by interacting finite state machines (FSM ). Each
FSM represents the behavior of an agent, and their interactions are represented by
messages passed through a communication network. In our model this netw ork is
synchronous in the sense th a t th e agents alternate between their sending and receiving

...©
Figure 5.1: The alternating sending (S) and receiving (R) states of an A IP ’s FSM

phases in lockstep. As protocol deliberations occur between those phases, we prefer
to present them through separate states. Accordingly, each state of an FSM is labeled
as either a sending (S) or receiving (R) state. An agent can only send in an S state,
and receive in an R state. A sta te transition occurs in each synchronous cycle, and it
always leads to a state w ith an opposite label (Figure 5.1).
Each AIP, in order to be defined in th e framework, should be modeled following
the described FSM. In other words, the protocol should be defined as a sta te m achine
with alternating send and receive states guiding the agent through its interactions.
At each send state, agents can send messages to others based on th e protocol they
employ. Accordingly, agents receive and process their incoming messages in receive
states. In this model, th e state transition is determ ined by the protocol, based on
agent’s beliefs, incoming and outgoing messages, and current state.

86

5 .1 .2

M u lti-P r o to c o l I n te r a c tio n M o d e ls

Some MAS architectures allow dynam ic selection of interaction protocol.

In such

architectures, an agent can select between alternative protocols dynamically. In these
situations, the agent needs to be able to model m ultiple protocols and activate one
dynamically. The FSM model described above supports such models by combining
different FSMs. As represented in Figure 5.2, the state machines of individual A IPs

AIP Set (FSM)

AIP B
(FSM)

AIP C
(FSM)

AIP A
(FSM)

AIP D
(FSM)

Figure 5.2: T he augm ented FSM th a t combines several A IPs

can be combined based on common practices for combining state machines to create
a new FSM th a t models a set of AIPs. In this case, th e agents initially perform a
negotiation protocol A in order to agree on which of the protocols B , C, and D they
wish to use.

87

5.2

A M o d el o f a M u ltia g e n t S y ste m

This m ultiagent system (MAS) model is designed as a game along th e lines of the
Colored Trails [Gal et al., 2010] game. However, it is designed and developed inde­
pendently to provide a specific microworld for studying helpful behavior in a team w ork
context. The model represents th e environment, th e agents in a team context, and
the task and subtask specifications. Each entity is described in the following.

5.2.1

Environm ent

The environment is a rectangular board th a t consists of colored squares (Figure 5.3)
on which the players of the game (software agents) are situated. T he colors of the
squares are chosen from a fixed set of colors C j , ..., Cm, rn > 1. The environm ent is

Figure 5.3: The board of th e game
dynamic and evolves in each round of the game. T he evolution of the environm ent is

represented by the changes in the colors. The color of any given square can change
at any tim e according to a prescribed stochastic model.
To model different phenom ena in th e environment, it is often required to model
different types of disturbances. Therefore, th e user can design different disturbance
models and plug them into th e microworld. Each disturbance model can affect the
environment, and consequently th e behavior of agents, in a different way. T he dis­
turbance in the environment occurs a t the beginning of each round of th e gam e when
the simulation engine activates the global events of th e microworld.

5.2.2

Task

At the beginning of each game, a task is assigned to a team . The m ain objective of
the team is to achieve the given task. The task can be broken into subtasks in such
a way th a t achieving the task requires achieving all the subtasks. Each subtask is
represented by the location of a square as the starting point and by th e location of
another square as the goal. A subtask is then considered to be completed if and only if
all the squares of one of the paths connecting its starting and goal locations have been
marked by one or more agents. In other words, each subtask is done if and only if a
set of certain actions have been performed by agents. However, the progress towards
completion of the task can be m easured by a scoring system and, if the com pletion
cannot be achieved it may still be im portant to reach a high team score.
Actions are represented by agents making a move from one square to another.
These moves are on a p ath from the initial location of a subtask to its goal location.
Subtasks are initially assigned to agents a t the beginning of the game and can be
dynamically reassigned later based on any user-defined (re)assignment algorithm .
89

5.2.3

R esources

At the beginning of each game, the team is given an am ount of resource points. The
team should consume some of its resource points in order to perform each action.

5.2.4

A gent Team

Each team consists of agents Ai, ...,A n,n > 1. T he agents are situated in th e envi­
ronment in the sense th a t each agent is located on a certain square of th e board. It
is allowed th a t multiple agents have the same position on th e board.
Agents in th e same team are allowed to help each other. Currently two forms of
help are modeled: action help and resource help. In action help agents can perform
actions on behalf of their teammates. An instance of such help, term ed as help act,
involves an agent Ai th a t wants to move to a square of color Ck, and a helper agent,
A j th a t executes th a t action on behalf of A;. T he result is th at A, moves w ith its
budget •rl unchanged, and A j’s budget r3 is reduced by Cjk + h, where Cjk is th e cost
of an action on a cell with color Ck for agent A j, and h € N is a team-wide constant
called the help act overhead. Note th a t if A j has a higher capability (i.e., lower cost)
for actions of type Ck than A,, the help act saves resource points to th e team , provided
th a t the difference in costs is higher th an the help act overhead. The help act overhead
quantifies the extra work involved when an agent performs an action for another agent
rather th an for itself.
In resource help, agents can exchange resource points. For example, suppose agent
Ai has a higher capability of doing an action of type Ck th a n agent A j, b u t Ai does
not have enough resource points in order to perform Ck■ In this situation, A j can
90

send the necessary resource points to Ai so th a t A l can finish its designated action.
This will also help the team save more resource points. It is also possible for Ai to
receive resource points from multiple sources.

5.3

E xam ple: T h e M u tu a l A ssista n c e P r o to c o l (M A P )

M utual Assistance Protocol (MAP) [Nalbandyan, 2011] is a protocol for incorporating
helpful behavior in agent teamwork. In MAP, an agent can help another agent who
is requesting help if they can jointly agree th a t the outcome of th e help is in the
interest of their team. The decision about performing help act in thus based on a
rational bilateral distributed agreement between th e two agents. The agent use their
individual beliefs and interact through a bidding sequence in order to make their
decisions. A complete description of MAP can be found in [Nalbandyan, 2011] and
[Polajnar et al., 2012].
In this section, the approach for using the proposed framework in modeling a
multiagent system and building a sim ulator for studying and developing a version of
MAP called Action MAP is presented. First, the microworld th a t was used for exper­
iments is described. Second, the approach for modeling Action MAP and other help
strategies th a t have been developed for the comparison studies of M AP is explained.

5.3.1

T he M icroworld C onfiguration

The microworld th a t is used for studying and validating M AP is described in [Polajnar
et al., 2012].

This microworld is carefully tailored to model the essential aspects

91

of a teamwork environment needed for experimenting w ith helpful behavior. This
microworld is the basis for our experim entation. Here, I quote the description directly
from the paper:

The players are software agents A l t . . . ,A n, n > 1, situated on a rectangu­
lar board divided into colored squares. The game proceeds in synchronous
rounds.

Each agent can move to a neighboring square in each round.

Each move represents th e execution of an action. T he types of actions
a i , , a m are represented by the available colors, and their costs to indi­
vidual agents by the n x m m atrix cost of positive integer values.

The task structure and th e planning capabilities of agents are modeled in the
microworld component as follows:

At the sta rt of the game, each agent Ai is assigned its initial location
on the board, a unique goal w ith a specified location and am ount

of

reward points, and a budget rl = dia of resource points, where di is the
shortest distance (i.e., num ber of squares) from the ag en t’s initial location
to its goal, and a a positive integer constant. W henever Ai moves to a
field of color a j, it pays costij from its resource budget; if the budget is
insufficient, the agent is blocked. Each agent chooses its own p a th to the
goal, which represents the choice of its own local plan. The p ath s can
intersect; it is legal for multiple agents to be on the same square a t the
same time. The game ends when no agent can make a move (because it
has either reached the goal or lacks the resources).

92

The gam e’s objective is to maximize the team ’s score. T he team score is used as
the metric for evaluating different MAS models for these experiments and is calculated
based on the scoring rules defined as follows:

All agents'rem ain in the game until th e end, when their individual scores
are calculated as follows: if Ai has reached th e goal, its score is th e goal
achievement reward

plus any remaining resource points (as a savings

bonus); if Ai has failed to reach the goal, its score is dt a .. where dz is th e
number of moves Ai has completed, and a is a positive integer constant
representing the reward for each move. The team score is the sum of all
individual scores.

The microworld is designed to model dynam ics of the environment th a t can affect
agents’ actions. The changes in the environment are modeled by a disturbance model:

As a representation of environment dynamics, the color of any square can
be replaced, after each round, by a uniformly random choice from the
color set. The change occurs with a fixed probability D, called th e level
o f disturbance.

Most MAP experiments conducted so far use th e following disturbance model. For
any given square, in each round, the color revision occurs w ith probability D\ th e new
color is a uniformly random choice among all available colors (including th e current
one). Note th at, since the new color can be the same as the old one, th e probability
th a t a given square actually changes color in a given round is D — (1 — l / m ) D .
The disturbance model described above is defined as a global environm ent event.
All the team s w ithin the experiment will face such changes in their environm ents
93

in the exact same manner. A t the beginning of each round, the sim ulation engine
triggers this global environment event and causes the colors of the board to change
based on the level of disturbance introduced above. Level of disturbance is defined as
a param eter and can be set in the experim ent setup. It is possible to use other models
of disturbance for other experim entation with MAP.
In simulations of MAP, the helpful act is modeled essentially as described in 5.2.4:

T he requester Ai faces a move to a square of color a*, , charged a t costik ;
if A j agrees to help, A, moves at no cost to itself, w ith the costjk charged
to A j . Protocol interactions involve explicit com putation and communi­
cation costs, and the help act has a fixed overhead cost. While th e specific
decision criteria and protocols for help transactions m ay vary, th e general
intent of such transactions is to advance th e performance of th e team as
represented by the team score.

Finally, the rules of agents’ perception in the environm ent that are used for gen­
erating percepts for each agent are defined as follows:

Each agent sees the entire board. The agent knows its own cost vector.
It knows the range of all color costs, and thus its own level of expertise
for each action type, relative to w hat may exist in th e team. T he agent
has probabilistic beliefs about the cost vectors of other agents. T he qual­
ity of its probabilistic beliefs about team m ates’ abilities is modeled by a
team-wide constant probability pm , called the m utual awareness. For a
given agent A j , j ^ i, and color a fc, agent A t believes, with probability
pM , th a t costjk has the value th a t it actually has, and with th e proba­
bility 1 —Pm th a t all possible color cost values are equally likely. This
94

uncertainty reflects the idea th a t, in many realistic teamwork situations,
the performance of a team m ate with a different expert profile on a specific
problem type may be hard to estim ate reliably.

5.3.2

M odeling P rotocols

A ctio n M A P
j R equester Ai |

Helper Aj

Select act/on
Calculate

ieam-benefit

r e q u e s t-h e lp ( a c tio n )

n -1

Calculate
le a m - lo s s

bidfaction, net-impact} ft
Select best aid

accept-bid

Bid if

net'lmpact >0

*em

Figure 5.4: The Action MAP. Reprinted from: [Polajnar et al., 2012]

As a general procedure in the framework, in order to model a protocol (Action
MAP in this example), after it has been generally conceived initially (e.g. by th e
diagram in Figure 5.4), it needs to be represented in term s of interacting finite state
machines (FSM), based on the framework’s AIP modeling scheme described in Sec­
tion 5.1, so th a t it can be employed by the agents in th e framework. T he result of
this representation is displayed in Figure 5.5. This FSM follows alternating send and
receive states, which is required by th e framework’s FSM executer. Such FSM is then
supported by a full definition of th e agent’s behavior in each state and the transition
rules. An example of the definitions for some of the states of the Action M A P ’s FSM
is presented in Figure 5.6. The FSM definition is then translated into code th a t is
executable by the framework.
95

_reachedGoal | IneedHelp-

•needHelp & canCalc & canBroadcast

needHelp &!canCatc & IcanBroadcast

^ r -g e t -h e l p -r e q )

^ r -b l o c k e d J

R *IG N R-H ELP-REQ

S-RESPOND-TOREQ
•bidding & canSend"I
{(bidding & canSend) & IhasResOwnAct
j-Wd
((bidding & canSend) & hasResOwnAct

A.
R-81DDING

JW d O-OWN-ACt )

Z

R-GETBIDS

j^R-BLOCKEDj

IhasBidsfi hasResOwnAct—— ^~ !h asB id s & IhasResOwnAct
/

hasBids

s S-DEC1DE-OWNi
ACT

S-BIDDING

[r - d o -o w n -act I
>S
—O

! S-DECIDE-OWN-ACT

f”
v-

Transitions

; S-DECIDE-HELP-ACT

SBLOCKED

S-RESP0ND-8IDS

T=
R-GET-BID-CONF

\

U nconditional Transition:

L ogical 'a n d ': &

C ondrtionaiTransition:

L o g ic a l'o r: {

-dcanSend

R-ACEPT-HELP*
^
ACT

^ R-BLOCKED j

States
^ Initial State J

^R-DO-OWN-ACt J

( R-DO-HELP- ^

\

; Dummy S

Figure 5.5: The FSM model of Action MAP. Note th a t some states are shown more
than once for the purpose of b etter presentation.
U n ila tera l P ro to co ls

In order to study and evaluate Action MAP, two other protocols w ith different help
strategies have been modeled: The U nilateral Requester-Initiated Protocol (URIP)
and the Unilateral Helper-Initiated Protocol (UHIP). These protocols represent help
strategies th a t use unilateral decision making in contrast to Action M A P ’s bilateral
approach. The framework easily accommodates the concepts required for incorporat­
ing these help strategies. First, th e protocols are modeled in the sim ulator w ithout
further modifications in its generic A IP model. Second, th e framework supports in­
corporating the concept of probabilistic beliefs th a t is introduced in th is MAS model

96

S ta te R - G E T - B I D S :

Receive q(q > 0) bids (B id i, . . . , Bidq)
If q = = 0 (no bids):
If resources suffice for next action:
Set State to S-DECIDE-OWN-ACTION;
Return waitingToCommit;
Else:
Set State to S-BLOCKED;
Return waitingToCommit;
Else:
Select the bid with highest Net Team Benefit Aij\
Set State to R-RESPOND-TO-BIDS;
Return waitingToCommit;

S ta te S - B I D D I N G [dummy]:

Set State to R-GET-BID-CONFIRMED;
Return awaitingResponse;

S ta te R - G E T - B I D - C O N F I R M E D :

If receives confirmation message for bidding
Set State to S-DECIDE-HELP-ACTIONS;
Return waitingToCommit;
Else:
Set State to S-DECIDE-OWN-ACTIONS;
Return waitingToCommit;

Figure 5.6: Example: P art of state definitions for th e Action M AP FSM.
which is required for modeling unilateral help strategies.

5.4

E xam ple: T h e E m p a th ic H elp M od el

A model of empathy as a mechanism for triggering help in agent team w ork is intro­
duced in [Polajnar et al., 2011] and [Dalvandi, 2012]. A simulator is built using the

97

proposed framework in order to investigate w hether and how incorporating this model
into agent teamwork can improve the team ’s performance.
In this section, the special microworld configuration th a t is built for th is sim ulator
is explained. The modeling of the protocol is similar as in Section 5.3.

5.4.1

The M icroworld C onfiguration

The simulator built for studies of th e em pathic help model uses alm ost th e same
microworld configuration as the MAP sim ulator described in Section 5.3. The m ain
difference between the microworlds of th e two simulators is explained below.

c*

C* (C'„, < Cik)

C''ik (C"» < C'ik)

G am e #1

G am e # 2

G am e # 3

Figure 5.7: Modeling agent’s experience carried over multiple games. T he cost of
performing an action on the cell w ith color Ck by agent A i is denoted as Cik■ As the
figure demonstrates,
decreases as the agent plays more games.

The em pathic help model requires agents to acquire experience from th e actions
th a t they perform. To accommodate this concept, a notion of experience is modeled
in this sim ulator’s microworld in the following way. As described in Section 4.3, each
experiment run consists of a fixed num ber of matches. In each m atch, agents play
a new game b u t some information from previous games is allowed to be m aintained

98

between games within the same experim ent run. In this microworld, as agents perform
actions, they gain more experience. The notion of experience is modeled by a reduction
in the action cost for th a t agent. As the costs of agents can be carried over from
previous games, agents can gain experience from th e previous games in th e current
game (Figure 5.7).
The same concept explained here can be used for other types of research where a
long-term memory for agents, as well as a longer-term retention of the changes to the
environment, may be required (e.g. machine learning applications).

99

C hapter 6

T he Sim ulation P ro cess

This chapter outlines a selection of simulation experim ents th a t have been conducted
with the simulators developed within th e software framework introduced in this thesis.
These experiments constitute a p art of th e ongoing research into agent interaction
protocols within the MAS research group a t UNBC. Their significance in th e context
of th a t research has been described in two defended theses, [Nalbandyan, 2011] and
[Dalvandi, 2012], as well as in two conference papers [Polajnar et al., 2011, 2012]. In
the context of this thesis they are cited as test cases th a t illustrate the potential of the
software framework to support different MAS models and different requirem ents of the
experimenters. In particular, Section 6.1 describes the experiments for studying the
MAP interaction protocol using the sim ulator introduced in Section 5.3; Section 6.2
describes the experiments for studying the Em pathic Help Model, which is another
AIP for helpful behavior in teamwork, using the sim ulator introduced in Section 5.4.
P arts of the experiment descriptions, and the diagram s displaying th e sim ulation
results, are reproduced directly from th e cited publications.

100

6.1

E xam ple: T h e M u tu a l A ssista n c e P r o to c o l (M A P )

The experiments presented in this section have been conducted in order to stu d y dif­
ferent properties of Action MAP and its advantages over other help strategies. F irst,
the general experiment setup th a t has been used for these experiments is explained.
Next, two experiments th a t dem onstrate the framework’s potential in modeling and
experim entation with different aspects of Action MAP and the agents’ environm ent
are presented. These experiments were conducted by Narek Nalbandyan using the
software described in this thesis.

6.1.1

T he E xperim ent Setup

The param eters defined in the experim ent setup th a t has been used for th e experi­
ments presented in this section are summarized below:

• T he board size is 10 by 10.
• Each square on the board can have one of 6 different colors.
• Each team has 8 agents.
• The reward points for achieving each goal is 2000.
• The reward points for accomplishing each step on the chosen p a th to th e goal
square is 100 reward points.
• The initial allocation of resources for each agent is 200 points per each step in
its chosen path towards its goal square.

101

• The overhead cost of performing a help act is 30 points.
• Four agent team s are considered: Action MAP. URIP, UHIP, and No-Help.
• The number of runs for each experiment is set to 10,000.

6.1.2

The Im pact o f C om p u tation and C om m unication C osts
U n icast I C o m putation

Mutual A w areness = 50%
Disturbance = 20%

N O -H E L P

Figure 6.1: Team scores vs com putation and communication (unicast) costs.
Reprinted from: [Polajnar et al., 2012]
This experiment is designed to study th e performance of Action M AP com pared to
other help strategies with respect to different costs th a t exist in realistic settings. In
particular, this experiment looks a t the costs associated to performing com putations
in assessing help requests and offers and sending and receiving messages in a network.
These costs are referred to as computation and communication (unicast) costs.
The comparative performance of all four team s based on different com putation and
communication (unicast) costs is shown in Figure 6.1. The first observation is th a t
102

the three team s th a t use help protocols (URIP, UHIP, and M AP) perform b etter th a n
the one th a t does not use any help model. However, their scores decrease as th e costs
of com putation and communication increase. If the costs continue to increase beyond
the area shown in the graph, the team th a t uses no help will eventually outperform
the team s th a t use help. Furtherm ore, as observed in [Polajnar et al., 2012]:

UHIP uses the most com putation (leading to a sharper performance drop
at th e high-cost end) and th e least communication (making it dom inant
for high communication and low com putation costs). M AP scores are best
overall. The relative scores of M AP vs U RIP when communication costs
are dominant depend on the relative cost of broadcast vs. unicast [...].
Our implementation of broadcast as n — 1 unicast messages favors U RIP
in th e critical area.

This experiment dem onstrates the potential of the framework in modeling and
experim entation with some aspects of a m ultiagent system. First, because of th e fact
th a t performing com putations affects th e system ’s performance, it has been modeled
as a cost (penalty) in the system. Second, the performance of the system has been
measured in different levels of com putation costs. Similarly, another penalty in the
system ’s performance has been modeled as communication cost and been varied in
the experimentation.

6.1.3

T he Im pact of M u tual A w areness and D isturbance

This experiment gives more insights about in w hat situations, based on two different
param eters of the environment, team s th a t employ Action MAP perform b etter th a n
103

Awareness / Disturbance
Computation C o st = 3

’ MAP

Less g g g uRiP
^ ■ U H IP
' NO-HELP

Figure 6.2: Team scores vs m utual awareness and environmental disturbance.
Reprinted from: [Polajnar et al., 2012]
other teams. These param eters are th e level of m utual awareness between agents,
about the information they know from their team m ates’ skills; and th e level of distur­
bance, representing the frequency of changes in th e environment th a t occur dynam ­
ically. The experiment varies the level of m utual awareness and th e environm ental
disturbance in order to compare th e performance of agents using A ction M AP w ith
other unilateral strategies in different conditions of the environment.
The results of this experiment are shown in Figure 6.2. Their analysis in [Polajnar
et al., 2012] is as follows:

URIP and UHIP rely on m utual awareness, while M AP and NO-HELP
do not. URIP and UHIP perform significantly worse th an MAP for low
m utual awareness, and improve as th e rising knowledge of their team ­
m ates abilities improves unilateral judgm ent. At high m utual awareness,
a U RIP agent requests help from the right team m ates, and owing to lower
104

communication costs (partly caused by our costly broadcast) outperform s
the otherwise dom inant MAP. Dynamic disturbance in the environm ent
adversely affects all methods, because the stochastic color changes disto rt
the effects of the initial planning (i.e., lowest-cost p a th selection). The
distortion is most significant in the low-disturbance range, as evidenced
by steeper performance drop; as the color composition of the p ath s gets
closer to random, further stochastic disturbance causes less degradation.
Throughout the range, m utual help partly com pensates the effects of dis­
turbance, as the very costly steps in an agent’s p ath can be perform ed at
lower cost by helpful teammates. As th e figure shows, th e performance of
NO-HELP indeed degrades more significantly com pared to other m ethods.
MAP and UHIP degrade the least.

This experiment dem onstrates how an experimenter can model and m anipulate
different aspects of a MAS environment in order study the behavior of agents in each
configuration.

This illustrates th e capability of th e framework in accom m odating

different characteristics of real-world environments in a simplified microworld model
th a t is suitable for experimentation.

6.2

E xam ple: T h e E m p a th ic H elp M od el

This section first examines the framework’s interoperability capabilities by explaining
the technique th a t has been used for optimizing th e em pathic help model using its
simulator and MATLAB. Next, I present two experiments about different aspects of
the em pathic help model th a t have been conducted by Behrooz Dalvandi using the

105

software described in this thesis.

6.2.1

O ptim izing th e Perform ance o f th e Em pathic M od el

T he performance of an agent team th a t employs th e em pathic help model depends
on four different param eters of the model. Three of these param eters, called th e emo­
tional state, past experience, and salience, are em pathy factors th a t p articipate in
the formation of affective response in th e model of em pathy for artificial agents intro­
duced in [Dalvandi, 2012]. The emotional state of th e subject of em pathy influences
the readiness to offer help to the object; passed experience o f their m utual interactions
is another influencing factor, as is th e salience of th e o b ject’s signals th e indicating
the need for help. The forth param eter is the threshold which the combined effects
of the three em pathy factors need to exceed in order for a help act to take place.
In order to investigate th e performance characteristics of empathic help compared
to other help model, one needs to first determine which combination of values of the
four param eters leads to the optim al team performance. T he author has chosen to use
Genetic Algorithms (GA) in order to determ ine th e values of these param eters which
together lead to the optim al performance of the agent team th a t employs th e em pathic
help model. For performing the optim ization, the Global Optim ization (GO) toolbox
in MATLAB is used together w ith the simulator introduced in Section 5.4. In the
following, first a brief overview of the optim ization process is explained. Next, the
role of the simulation in the optim ization process is discussed. Finally, th e approach
to connect the simulator to MATLAB’s GO toolbox is presented.
In order to optimize a problem using GA, one needs to represent its possible solu­
tions as individuals (chromosomes) (i.e. a string representation of some values) and

106

define a fitness function th a t can evaluate each solution. In the sim ulator’s realm,
the individuals are a tuples of distinguished param eters which affect th e perform ance
of the simulated multiagent system (representing a team). Each tuple of these pa­
ram eter values then represents a possible solution.

The fitness function’s value is

determined by the performance of th e team th a t uses the specified param eter val­
ues and is measured by a m etric defined by the model and implemented w ithin the
simulator.
In this setting, the sim ulator is used as the fitness function. It takes an individual
generated by MATLAB and performs a simulation based on the values of param eters
defined in the individual. After the simulation process is complete, it retu rn s the
value of the team score as th e fitness value. Using this combination, th e optim ization
algorithm finds the optim al settings for those four param eters based on the team
performance in the simulation experiments.

Individual (X)

, MATLAB G.O/
S im u lato rU n terfa ce '

E xperim ent
S e tu p
S im u lato r
E xperim ent
Result

F itness V alue

wn

MATLAB

Figure 6.3: Interfacing the sim ulator with MATLAB’s Global O ptim ization (GO)
toolbox. The d ata flow for a single individual in th e population. The fitness value for
the rest of the population is evaluated in th e same way.
In order to allow MATLAB to interact with th e simulator, a specialized inter­
face is developed. This small program is responsible for translating and m anaging
107

MATLAB’s interactions with the simulator. MATLAB's GO toolbox can w rite each
individual d ata in a file and read the fitness function’s value from a file in each step
of its GA algorithm. In each step, the toolbox generates a population of different
individuals. Each individual represents a tuple of values of th e four em pathic model
param eters and a fitness value will be associated to it a t the end of a sim ulation
process. The interface’s job for each individual in the population, once it is invoked
by the toolbox, is to read the individual d ata from the file, generate an experim ent
setup, and execute the simulator w ith the generated experiment setup (as presented
in Figure 6.3). Upon finishing the simulation, the interface gets the experim ent result
from the simulator and writes it, as the value of th e fitness function, into a file which
is accessible by the toolbox. The toolbox uses this fitness value, checks w hether a new
generation is required, and if so, creates a new generation of individuals. This cycle
repeats until the toolbox finds th e optimal values based on its configuration. The op­
tim al values determ ined by this m ethod are then used in th e simulation experim ents
to study the behavior of agents employing the em pathic help model.
The results of the genetic algorithm optim ization on th e four em pathic param eters
are presented in Figure 6.4. T he optim ization process uses an initial population of
30 individuals and stops after it faces 50 stall generations. It uses th e ran k fitness
scaling function and the stochastic uniform selection function. Note th a t because the
optimization algorithm is defined so as to minimize the value of the fitness function,
we use the negative value of th e team score in the optim ization process.

108

(a)

Best:-63404 Mean: -63247.5

_6.i?1°

Best fitness
M ean fitn e s s

-6.15

-

6.2

-6:25
-63

-6:35

10

20

30

40
50
' Generation

60

70

80

90

100

Gurrent B e s t Individual

o

0.5

Threshold

Emotional State

Past Experience

Salience

N um ber of variables (4)
Stop*

Figure 6.4: The genetic algorithm optim ization of four em pathic param eters produced
by MATLAB. Reprinted from: [Dalvandi, 2012]

6.2.2

The E xperim ent Setup

The experiments with the em pathic help model follow the same experim ent setup
designed for the Action MAP experiments in order to provide a unified basis for
comparison. Also, the values determ ined by the optim ization process are incorporated
in the model for the following experiments.

109

6 .2 .3

T h e V a lid a tio n o f E m p a th y a s a H e lp T rigger

!

Em pathic
R andom

x 10

Ii
!

<n

i
7-

C
20
r\-s

100

100

7-

Figure 6.5: The performance of em pathic team versus random-help. R eprinted from:
[Dalvandi, 2012]
In order to investigate w hether or not em pathy can be an effective trigger of help
in an agent team , a series of experim ents are performed to compare th e perform ance
of em pathic agents with the performance of a team in which agents provide help
randomly. In the experiments, the agents from b o th team s use the same criteria in
requesting help. For offering help (answering to the help requests), th e agents in
the seconds team randomly agree to help based on a fixed probability value, called
the random help rate.

These experim ents vary th e random help rate in different

environmental disturbance levels (as described in Section 6.1).
Figure 6.5 shows the com parative team scores of the em pathic team and th e ran ­
dom help team for different values of random help rate and disturbance in th e envi­
110

ronment. In low to m oderate levels of disturbance the em pathic team outperform s
the random-help team for all levels of the help probability. This is indeed th e area of
highest interest for practical applications. A disturbance level of 50% implies th a t half
of the world changes randomly at each step, and the fact th a t beyond th a t p oint most
help strategies become ineffective is intuitively expected. This experiment series thus
shows th a t em pathy is a valid trigger for help m ost practically relevant situations.
For higher levels of disturbance em pathy-based help is no longer effective.
This experiment dem onstrates how one can model and manipulate a param eter of
an interaction model (random help model in this example) and study th e behavior of
agents in different configurations with respect to the p aram eter’s value.

6.2.4

A Com parison of E m pathic and R ational H elp

In order to investigate the comparative performance of team s using em pathic and ra­
tional help models, a suitable approach would be to realistically model th e deliberation
of rational agents about help acts in situations where the com putational com plexity of
such deliberations can vary widely. This is because of the expectation th a t em pathic
approaches, which require less com putation, might outperform rational ones as ratio­
nal deliberations become increasingly complex. Such experiments can be conducted
in future using the framework proposed in this thesis by connecting it to an external
reasoning engine, measuring the real com putational complexity of deliberations about
help, and using it for performance comparisons w ith em pathic help mechanisms.
The current experiment series relies on a simplification which does not allow for
realistic comparisons of the actual decision costs in the em pathic versus rational help
models. However, it allows one to identify th e general trends as the cost of rational
111

100

Figure 6.6: The performance of em pathic team versus Action MAP (as a rational
strategy) Reprinted from: [Dalvandi, 2012]
decision varies in th e presence of environm ental disturbance. For this purpose the
cost of rational decision is modeled by an independent param eter called th e rational
decision cost which affects the team score of agents using Action MAP.
Figure 6.6 shows th a t the em pathic agents exhibit superior performance when
rational decisions become complex. The graph shows th a t this phenomenon is more
pronounced at higher disturbance levels. This is because a t higher disturbance levels
the number of help requests increases and consequently th e rational agents need to
perform more calculations. The em pathic agents have lower decision costs and can
deal with such situations more efficiently.

112

C hapter 7

A n alysis and E valu ation

The main objective of this research has been to provide a software framework for
building simulators th a t facilitate th e study of agent interaction models in early stages
of their development. The framework’s purpose has been to help th e designer of an
agent interaction model by reducing th e design decision space through providing an
environment for simulation experiments th a t supports early feedback on com parative
performance of alternative solutions. To achieve th a t, a number of objectives and
design principles have been identified in Section 3.3. In this chapter, I analyze the
proposed framework with respect to its objectives and principles and evaluate to w hat
extent they are addressed in this thesis.
The graphical user interface (GUI) mode of th e front end (presented in Section 4.3)
supports interactive control and m anipulation of th e simulation model. T he experi­
ment setup toolbox of the GUI allows the user to modify th e simulation param eters
a t any time. The modifications are handled by th e param eter manager service of the
framework which guarantees th a t they apply to all th e components of th e sim ulator
113

and the simulation model. The feedback from th e modifications is provided interac­
tively by the visualization and console toolboxes of the GUI. In addition, th e user
can run an experiment step-by-step in order to study the behavior of agents in more
detail. These features together provide interactive experim ent control to th e users of
the simulators built using the framework.
The visualization toolbox of the GUI provides on-line visualization of th e simu­
lation results as well as th e state of the world. It responds to any changes in the
simulation model and results as they occur. Working along with th e interactive ex­
perim ent control feature, the interactive and dynamic visualization helps th e designer
of an interaction model to reduce the decision space by getting early feedback from
simulation experiments.
The framework’s design allows the user to preview the simulation results as their
precision increases gradually. T he front end of the framework th a t controls th e experi­
ment setup and the execution of th e experiment can execute a series of experim ents in
multiple steps, in such a way th a t in each step all th e experiments are executed w ith
a low number of runs — which can be done in a reasonable tim e — and th e results are
displayed to th e user. In further steps, th e results are updated as more experim ent
runs are being executed. This feature supports th e early feedback of th e framework
by allowing the user to preview the trend of any series of experiments before they get
to the desired precision level.
The architecture support for concurrent sim ulation of multiple teams, as described
in Sections 4.2 and 4.3, provides identical environments and experimental scenarios to
each team while they are being executed concurrently. In order to achieve th a t, the
architecture uses different layers of environment which allows the separation of global
events from local events. The architecture keeps this separation transparent to mul­
114

tiagent system (MAS) models and their agents, allowing them to in teract only with
their own environment w ithout knowing about th e layers and other team s. Combined
with interactive experimentation and visualization, th e performance and behavior of
all the teams are presented to the user at the same time as a part of th e early feed­
back mechanisms of the framework. This feature has been successfully tested in all
the experiments conducted using the simulators built with the framework, such as the
ones presented in Chapters 5 and 6. It addresses th e objective of reducing th e design
decision space by providing early feedback on the com parative performance of alter­
native candidate solutions in identical circumstances. The comparative performance
can be observed during th e course of th e experim ent and th e param eters th a t affect
it can be modified interactively for all candidates a t the sam e time.
The generic MAS model presented in this thesis is based on a generic microworld
model. It only captures th e essential elements of expert teamwork (described in Sec­
tions 2.3 and 3.2) by representing agents, tasks and subtasks, expertise, plans, and
helpful acts in simple forms. While it captures th e substance of the problem th a t the
experimenter intends to study, the model remains simple. T he environment is repre­
sented by a board of colored squares where each color represents a different expertise
th a t is required to perform a specific action. Agents are located on this board and
each have a set of individual capabilities. Each agent can individually plan how to
move from its initial location to its goal location and thus complete its subtask. In
addition, this simple model does not require the agents to employ complex ontolo­
gies to deal with the domain knowledge. The agent architecture of this MAS model
focuses on the interaction of agents and does not impose any requirements for using
complex agent reasoning (although it is possible) in dealing with th e environment.
These features of the MAS model allow the designers to focus on dealing w ith agent
interaction models rather than the domain knowledge and agent reasoning. This is

115

valuable in the early stages of the design process; later on, the analysis may require
further confirmation or refinement in more elaborate contexts.
The framework’s high-level structure (presented in Section 4.2) is designed to pro­
vide a low coupling between its MAS models component and the rest of th e framework.
The MAS models are designed as a separate component of th e framework which can
be plugged into the framework and interact with other framework’s com ponents. T he
MAS models’ design can be flexibly changed as long as it uses the sam e few inter­
actions with other components of the framework. This feature has been tested in
our research projects th a t have been performed using the framework. It contributes
substantially to the extendibility of th e application domain of the framework beyond
its initial scope.
The framework’s interoperability, as presented in Section 4.2, is designed in two
directions. First, it allows external systems to m anipulate experiment setups and
process simulation results through an adaptor program. In this approach, either the
simulator or the external system can invoke the other; thus, it allows b o th client and
server configurations for the sim ulator in interacting with external systems. T he in­
teroperability of the simulator has been validated during our research on em pathic
help model (Section 6.2). The decoupling of the framework from other pre- and p o st­
processing applications, along with its interoperability features, allows the framework
design to remain simple and focused on the key tasks, while delegating other po­
tentially complex tasks, such as optim ization, advanced visualization, or statistical
analysis, to existing specialized software packages.

This flexible architecture thus

extends the framework’s functionality.
Second, the framework allows its agents to employ more complex reasoning capa­
bilities th a t can be provided by external reasoning engines. The agent architecture of
116

the framework can activate an external reasoning engine in the deliberation process
of an agent to execute an agent program w ritten in an agent programming language.
This will delegate the reasoning to the external engine. This type of interoperabil­
ity can be provided by developing an adaptor program to interact w ith a specific
reasoning engine. This feature supports the transitions in agent interaction model
development, from the early stages th a t favor simplicity and abstraction, to th e more
m ature stages th a t benefit from more elaborate and realistic MAS contexts.
The architecture of th e simulators developed w ithin the framework is distributable
in the sense th a t each sim ulator can either run on a single processor or be replicated to
share the simulation load among a number processor nodes. The performance im pact
of the distributable architecture has been examined in the following experim ent series.
A simulator built using th e framework was executed on a cluster of identical machines
running Ubuntu Linux 10.04. Each machine had an Intel(R) Core(TM)2 Q uad CPU
Q6600 running at 2.40GHz and the nodes were connected through a lOOMb/s E thernet
network.
The simulator was set to conduct 10 experiments for 10 different levels of environ­
mental disturbance. The experiments included 3 agent team s, each w ith 8 agents and
the size of the board was set to 10x10. In order to get statistically significant results,
each experiment was repeated 24000 times.
The experiment involved th e execution of the same simulation task on a varying
number of nodes in the cluster. T he level of distribution was changed in 8 steps,
from a single node run to a cluster with 8 nodes, each tim e adding a new node. The
duration of the simulation was measured using the Linux/U nix tim e1 utility.
1h ttp ://p u b s.opengroup.org/onlinepubs/9699919799/utilities/tim e.htm l

117

120

100

c

E

s
Q

60

40

0

1

2

3

4

5

6

7

8

9

N u m b er of N o d e s

Figure 7.1: The duration of th e distributed simulation for 24000 runs, based on the
size of the cluster
The experimental results show th a t th e framework’s sim ulator architecture is fully
scalable; as the number of nodes on the cluster increases, th e speed of th e sim ulation
increases almost linearly. In this example, as presented in Figure 7.1, for a single
node run, th e time it took for the simulator to finish 24000 number of runs was 100.1
minutes whereas the time for the same simulation on a cluster with 4 nodes was 25.29
minutes which is almost I /4 th of the tim e it took w ith 1 node. The speed gain of the
simulator over different numbers of nodes is presented in Figure 7.2. In all the cases,
the difference between the speed gain and its ideal linear expectation is less th a n 5%.
The experimental results agree with the theoretical expectations according to the
nature of these simulations. The almost linear speed up can be explained by the fact
th a t the distributed simulation runs are different instances of the sam e experim ent
b ut independent from each other. The to tal num ber of runs can be broken into pieces

118

8

7

6
5
Q.

3
■<6U 4
IU
</>

S peed-up

2
1

0
0

1

2

3

4

6

5

7

8

9

N um ber of N odes

Figure 7.2: The speed-up of th e distributed simulator for an experiment w ith 24,000
runs. The plot dem onstrates th e relative speed of distributed com putation com pared
to the same com putation performed on a single node.
th a t can be executed in parallel which results in better system performance. The
scalability of the results comes from the fact th a t there is almost no overhead for
com m unication/synchronization between the instances of th e simulator distributed
over multiple nodes. The only overhead in this approach is for the task distribution
which is negligible. As a result, addition of a new node th a t can process a specific
portion of the load will reduce the overall duration of the simulation proportionate to
its given portion and linearly increase th e sim ulation speed.
The analysis of the performance im pact of the distributed simulation above shows
th a t the m ethod is indeed effective in increasing th e speed of simulation and providing
the results to the user faster.
The framework has shown a promising usability in th e two research projects on

119

agent interaction protocols (AIPs) dem onstrated in C hapters 5 and 6. T he fram e­
work's capability for instantiating specialized simulators has been verified in those
research projects. Various features of th e framework have enabled th e modeling and
studying of different aspects of those A IPs and th e flexibility of the fram ework's ar­
chitecture for implementing new features has been examined during those studies.
In summary, the above analysis suggests th a t the proposed framework is a valuable
tool for studying agent interaction models and is effective and suitable for a variety
of research projects in agent interactions.

120

C hapter 8

C onclusions and F uture W ork

This thesis describes a new software framework for studying agent interaction models
used in agent teamwork by means of simulation experiments. The; framework facili­
tates the building of custom simulators for various m ultiagent system (MAS) models,
which are then used in design-oriented simulation studies of agent interaction models
in their early development stages. T he main purpose of such a custom-made simula­
tor is to reduce the design decision space by providing early feedback on com parative
performance of alternative solutions in the course of sim ulation experiments, within
a specific research domain.
The results presented in this thesis have helped overcome th e methodological chal­
lenges th a t have been identified in the course of our investigation of concrete agent
interaction protocols for helpful behavior in agent teamwork. Specifically, these chal­
lenges include: the problem of customizing the simulation tools to m eet th e require­
ments and emphasis of a particular type of MAS research; th e problem of reducing
the complexity of simulation models by finding simple and yet representative generic
121

abstractions for a particular domain; and the problem of making the tools sufficiently
general, flexible, and extendible th a t variation in the MAS model structures does not
require substantial changes in the existing tool set.
In order to address these challenges, the framework provides a generic sim ulator
th a t can be instantiated with concrete MAS models. Each such MAS model is ab stract
and simple, based on a microworld, w ith a well-defined research scope and focus. It
requires a very modest im plem entation effort and does not need elaborate support
from the simulation environment. It is relatively easy to incorporate into th e generic
simulation environment provided by the framework in order to produce a custom
simulator th a t effectively supports a specific direction of research.
The generic simulator architecture of the framework provides a novel com bination
of features th a t facilitate experimenting with agent interaction models. In particular,
its generic simulation environment provides interactive experim entation and visual­
ization, concurrent simulation of multiple teams, low coupling between its MAS model
and the simulation environment, distributable architecture, and interoperability w ith
agent reasoning engines and other external systems. The MAS models also share a
generic architecture designed for the study of agent teamwork interactions. Its inter­
action module implements agent interaction protocols specified as interacting finite
state machines. The microworld is inspired by the Colored Trails game b u t designed
specifically for studies of helpful behavior in team s of artificial agents. Based on mes­
sage passing in the current im plem entation, the communication infrastructure is open
to extensions.
Central to the generic simulator architecture is the idea th a t the designer of a new
agent interaction model, facing a variety of decisions with many possible outcomes,
needs to be able to choose between alternative solutions by comparing their im pacts
122

on team performance efficiently and directly, so th a t th e design decision space can
be substantially reduced early in the development cycle. In support of this idea, the
generic simulator allows concurrent operation of multiple agent teams employing the
alternative solutions, with im mediate visualization of the simulation in progress, and
lets the experimenter interactively control the simulation parameters, including the
possibility of incrementally adjusting the number of runs in order to control th e level
of statistical significance of the results.
The framework supports interoperability of th e generic simulator w ith external
systems, as a client, server, or both. For instance, a custom simulator, acting as
a client, has employed MATLAB in order to provide genetic algorithm (GA) opti­
mization of its MAS model param eters, while at th e same time, acting as server, it
provided a simulation experiment per each individual (param eter value com bination)
in every GA generation, and returned their performance scores to th e GA algorithm
as their fitness values. In general, interoperability allows a custom sim ulator built
within the framework to interactively delegate variety of tasks, such as optim ization,
statistical analysis, or advanced visualization, to existing specialized systems.
The com putational complexity of the concurrent sim ulation of multiple MAS m od­
els can be overcome through a distribution of simulation runs of the same experim ent
across a potentially large number of nodes in a com puting cluster.

T he achieved

speedup in trials using up to eight nodes, has been found to be almost linear. This is
attributed to the fact th a t individual runs are m utually independent and do not need
to interact during execution.
The framework has been implemented and used in two research projects a t UNBC
to derive the custom simulators for two types of agent interaction protocols for helpful
behavior in agent teamwork: the M utual Assistance Protocol (MAP) and th e Em123

pathic Help Protocol. MAP lets one team member directly help another based on
their bilateral rational assessment th a t a help act is in the interest of th e team , while
in the em pathic help protocol, the decision relies on the affective response based on a
model of em pathy for artificial agents. In both cases, the protocol designers have been
able to run their own experiments, and the effectiveness of th e simulator in achieving
our formulated objectives has been confirmed.
W ith respect to possible future research, th e following directions can be considered:

• Although the scope of this thesis is on teamwork contexts, the design of the
framework does not exclude th e possibility th a t the developed solutions may
have a wider scope and be applicable, for instance, to selfish agents or to individ­
ual interactions without an im m ediate group context. Conducting experim ents
for applications other than agent teamwork could be am interesting direction for
future work.
• Adding the support for a standard agent com munication language as an under­
lying system for message passing would be an interesting part of th e future work
of this thesis. In most of the agent-oriented programm ing languages and MAS
platforms, agents employ an agent communication language in their communi­
cation. For more realistic experim entation, th e support for such language would
be valuable for the users of the framework.
• As a by-product of the work on this thesis, a direction for its future work is to
develop an execution layer for agent interaction models that allows abstracting
the interaction models in agent programs. T his would separate the interaction
mechanisms from the rest of th e m ainstream agent code. The execution layer
can be developed independently from m ultiagent platforms in order to make it

124

interoperable with different MAS platforms. This can be an extension of the
p arts of the framework which allow the agent architecture, considering its AIP
execution capability, to employ external agent reasoning engines.
• The current version of the framework only implements th e message passing com­
munication mechanism used for AIPs. Communication using environm ent and
communication based on a shared storage are not yet fully im plem ented. Im ­
plementing these mechanisms and providing relevant test-cases for them would
be a part of the future work.

125

B ibliography

Huib Aldewereld, Wiebe van der Hoek, and John jules Meyer. Rational team s: Logical
aspects of multi-agent systems. Technical report, Utrecht University, 2004.
J. Alferes, A. Brogi, J. Leite, and L. Pereira. Evolving logic programs.

Logics in

Artificial Intelligence, pages 50-62, 2002.
Fabio Bellifemine, Federico Bergenti, Giovanni Caire, and Agostino Poggi. Jade - a
java agent development framework. In Rafael Bordini, Mehdi Dastani, Jurgen Dix,
Amal Fallah Seghrouchni, and G erhard Weiss, editors, Multi-Agent Programming,
volume 15 of Multiagent Systems, Artificial Societies, and Simulated Organizations,
pages 125-147. Springer US, 2005. ISBN 978-0-387-26350-2.
Rafael H. Bordini, Lars Braubach, Mehdi D astani, Amal El Fallah Seghrouchni,
Jorge J. Gomez Sanz, Joao Leite, Gregory M. P. O ’Hare, Alexander Pokahr, and
Alessandro Ricci. A survey of program m ing languages and platforms for m ulti-agent
systems. Informatica (Slovenia), 30(l):33-44, 2006.
R.H. Bordini, J.F. Hiibner, and M. Wooldridge. Programming multi-agent system s in
AgentSpeak using Jason, volume 8. W iley-Interscience, 2008.

126

B. Chen and S. Sadaoui. A Generic Formal Framework fo r Multiagent Interaction
Protocols. Citeseer, 2003.
Wai-Khuen Cheng, Boon-Yaik Ooi, and Huah-Yong Chan. Resource federation in grid
using autom ated intelligent agent negotiation. Future Gener. Comput. Syst., 26(8):
1116-1126, October 2010. ISSN 0167-739X. doi: 10.1016/j.future.2010.05.012. URL
h t t p : / / d x . d o i .o r g /1 0 . 1 0 1 6 /j. f u t u r e .2 0 1 0 .0 5 .0 1 2 .
K. L. Clark and F. G. McCabe. Go!-a m ulti-paradigm programming language for
implementing multi-threaded agents. Annals o f M athematics and Artificial Intelli­
gence, 41:171-206, August 2004.
P.R. Cohen and H.J. Levesque. Teamwork. Nous, 25(4):487-512, 1991.
R.W. Collier. Agent factory: A framework fo r the engineering of agent-oriented ap­
plications. PhD thesis, University College Dublin, 2002.
D.D. Corkill. Blackboard systems. A I expert, 6(9):40-47, 1991.
R.S. Cost, Y. Chen, T. Finin, Y. Labrou, and Y. Peng. Modeling agent conversations
with colored petri nets.

In Working Notes o f the Workshop on Specifying and

Implementing Conversation Policies, pages 59-66, 1999.
Stefania Costantini and A rianna Tocchio. A logic programm ing language for m ulti­
agent systems. In Logics in Artificial Intelligence. Proc. o f the 8th Europ. C o nf,
JELIA 2002, L N A I 2424, pages 1-13. Springer-Verlag, 2002.
Behrooz Dalvandi. A model of em pathy for agent teamwork. Masters thesis, University
of Northern British Columbia, January 2012.
B. Dunin-Keplicz and R. Verbrugge. Teamwork in M ulti-Agent Systems: A Formal

127

Approach. Wiley Series in Agent Technology. John Wiley & Sons, 2011. ISBN
9781119957607.
H.R. Dunn-Davies, R.J. Cunningham, and S. Paurobally. Propositional statech arts for
agent interaction protocols. Electronic Notes in Theoretical Computer Science, 134
(0):55 - 75, 2005. ISSN 1571-0661. Proceedings of the F irst International W orkshop
on Euler Diagrams (Euler 2004).
R. Evertsz, M. Fletcher, R. Jones, J. Jarvis, J. Brusey, and S. Dance. Im plem enting
industrial multi-agent systems using jack tm. Programming multi-agent systems,
pages 18-48, 2004.
Xiaocong Fan, John Yen, and Richard A. Volz. A theoretical framework on proactive
information exchange in agent teamwork. Artif. Intell., 169(1):23—97, November
2005. ISSN 0004-3702.
Nicholas V. Findler and Gregory D. Elder. M ulti-agent coordination and cooperation
in a distributed dynamic environment w ith limited resources. Artificial Intelligence
in Engineering, 9:229-238, 1995.
G. Fortino and W. Russo.

M ulti-coordination of mobile agents: a model and a

component-based architecture.

In Proceedings o f the 2005 AC M sym posium on

Applied computing, pages 443-450. ACM, 2005.
Y. Gal, B. Grosz, S. Kraus, A. Pfeffer, and S. Shieber. Agent decision-making in
open-mixed networks. Artificial Intelligence, 2010. URL h t t p : / / d x . d o i . o r g / 1 0 .
1 0 1 6 /j.a r tin t.2 0 1 0 .0 9 .0 0 2 .
K.V. Hindriks, F.S. De Boer, W. Van der Hoek, and J. J.C. Meyer. Agent program m ing
in 3apl. Autonomous Agents and M ulti-Agent Systems, 2(4):357-401, 1999.

128

0 .E . Holland. M ultiagent systems: Lessons from social insects and collective robotics.
In Adaptation, Coevolution and Learning in Multiagent Systems: Papers from the
1996 A A A I Spring Symposium, pages 57-62, 1996.
Ece Kamar, Ya Gal, and B arbara J. Grosz. Incorporating helpful behavior into collab­
orative planning. Proceedings o f The 8th International Conference on Autonom ous
Agents and Multiagent Systems, 2:875-882, 2009.
David Keil and Dina Goldin. Indirect interaction in environments for m ulti-agent
systems. In Danny Weyns, H. Van Dyke Parunak, and Fabien Michel, editors, E n­
vironments fo r Multi-Agent Systems II, volume 3830 of Lecture Notes in Computer
Science, pages 68-87. Springer Berlin / Heidelberg, 2006. ISBN 978-3-540-32614-4.
H. Kitano, M. Asada, Y. Kuniyoshi, I. Noda, and E. Osawa. Robocup: T he robot
world cup initiative. In Proceedings o f the first international conference on A u ­
tonomous agents, pages 340-347. ACM, 1997.
H. Kitano, S. Tadokoro, I. Noda, H. M atsubara, T. Takahashi, A. Shinjou, and S. Shimada. Robocup rescue: search and rescue in large-scale disasters as a dom ain for
autonomous agents research. In Systems, Man, and Cybernetics, 1999. IE E E SM C
’99 Conference Proceedings. 1999 IE E E International Conference on, volume 6,
pages 739 -743 vol.6, 1999.
1. Kotenko. Simulation of agent teams: the application of dom ain-independent frame­
work to computer network security. In 23rd European Conference on Modeling and
Simulation (ECMS2009). Madrid, Spain, pages 137-143, 2009.
G.J.M. Kruijff, F. Colas, T. Svoboda, J. van Diggelen, P. Balmer, F. Pirri, and
R. Worst. Designing intelligent robots for hum an-robot teaming in urban search &;
rescue. In 2012 A A A I Spring Symposium Series, 2012.

129

Joao Alexandre Leite, Jose Julio Alferes, and Luis Moniz Pereira. Minerva - a dynam ic
logic programming agent architecture. In Revised Papers from the 8th International
Workshop on Intelligent Agents VIII, ATAL :01, pages 141-157, London, UK, UK,
2002. Springer-Verlag.
Jeffrey A Lepine, Mary Ann Hanson, W alter C Borman, and Stephan J Motowidlo.
Contextual performance and teamwork: Implications fo r staffing, volume 19. 2000.
Xiong Li, Xianggang Liu, Zhiming Dong, and K unju Li. Toward an agent-based model
of tactical engagement. In Advanced M anagement Science (ICAM S), 2010 IE E E
International Conference on, volume 3, pages 218 -223, july 2010. doi: 10.1109/
ICAMS.2010.5553251.
Jurgen Lind. Specifying agent interaction protocols w ith standard uml. In Revised P a­
pers and Invited Contributions from the Second International Workshop on AgentOriented Software Engineering II, AOSE ’01, pages 136-147, London, UK, UK,
2002. Springer-Verlag. ISBN 3-540-43282-5.
M. Luck, P. McBurney, and C. Preist. Agent technology: enabling next generation com­
puting (a roadmap fo r agent based computing). AgentLink/University of Southam p­
ton, 2003.
Nancy Ann Lynch. Distributed Algorithms. Morgan Kaufm ann Series in D ata M an­
agement Systems. Morgan Kaufm ann Publishers, 1996. ISBN 9781558603486.
Hamza Mazouzi, Amal El Fallah Seghrouchni, and Serge Haddad.

O pen protocol

design for complex interactions in multi-agent systems. In Proceedings o f the first
international jo int conference on Autonom ous agents and multiagent systems, pages
517-526. ACM Press, 2002.

130

F. Mokhati, M. Badri, and L. Badri. A formal framework supporting th e specification
of the interactions between agents. Inform atica (Slovenia), 31(3):337, 2007.
L. Monostori, J. Vancza, and S.R.T. Kum ara. Agent-based systems for m anufacturing.
C IRP Annals - Manufacturing Technology, 55(2) :697 - 720, 2006. ISSN 0007-8506.
doi: 10.1016/j.cirp.2006.10.004.
R. Nair, T. Ito, M. Tambe, and Stacy Marsella. The role of emotions in m ultiagent
teamwork: A preliminary investigation. Who needs emotions: the brain meets the
robot, (213):l-23, 2003.
Narek Nalbandyan. A m utual assistance protocol for agent teamwork. M asters thesis,
University of N orthern British Columbia, September 2011.
C. Nikolai and G. Madey. Tools of th e trade: A survey of various agent based modeling
platforms. Journal of Artificial Societies and Social Simulation, 12(2):2, 2009.
J. Odell, H. Van Dyke Parunak, and B. Bauer. Representing agent interaction pro­
tocols in uml. In Agent-Oriented Software Engineering, pages 201-218. Springer,
2001 .

Andrea Omicini and Enrico Denti. From tuple spaces to tuple centres. Science o f
Computer Programming, 41(3):277 - 294, 2001.
Andrea Omicini and Franco Zambonelli. Coordination for internet application de­
velopment. Autonomous Agents and M ulti-Agent Systems, 2:251-269, Septem ber
1999. ISSN 1387-2532.
Pier Palam ara, Vittorio Ziparo, Luca Iocchi, Daniele Nardi, and Pedro Lima. Team ­
work design based on petri net plans. In Luca Iocchi, Hitoshi M atsubara, Alfredo
Weitzenfeld, and Changjiu Zhou, editors, RoboCup 2008: Robot Soccer World Cup

131

XII, volume 5399 of Lecture Notes in Computer Science, pages 200-211. Springer
Berlin / Heidelberg, 2009. ISBN 978-3-642-02920-2.
Philippe Pasquier, Ramon Hollands, Iyad Rahwan, Frank Dignum, and Liz Sonenberg.
An empirical study of interest-based negotiation. Autonomous Agents and MultiAgent Systems, 22:249-288, 2011. ISSN 1387-2532. 10.1007/sl0458-010-9125-6.
Shamimabi Paurobally and Jim Cunningham. Achieving common interaction pro­
tocols in open agent environments.

In In Proceedings o f the 2nd international

workshop on Challenges in Open Agent Environments, page paurobally.pdf., 2002.
Alexander Pokahr, Lars Braubach, and W infried Lamersdorf. Jadex: A BDI reasoning
engine. In J. Dix R. Bordini, M. D astani and A. El Fallah Seghrouchni, editors,
Multi-Agent Programming, pages 149-174. Springer Science+Business M edia Inc.,
USA, 9 2005. Book chapter.
Jernej Polajnar, Behrooz Dalvandi, and Desanka Polajnar. Does em pathy between
artificial agents improve agent teamwork ? In Proceedings o f the 1Oth IE E E Interna­
tional Conference on Cognitive Inform atics & Cognitive Computing, pages 96-102,
Banff, Alberta, 2011.
Jernej Polajnar, Narek Nalbandyan, Omid Alemi, and Desanka Polajnar. An interac­
tion protocol for m utual assistance in agent teamwork. In Proceedings o f the Sixth
International Conference on Complex, Intelligent, and Software Intensive System s
(CISIS-2012), 2012.
Anand S. Rao. AgentSpeak(L): BDI agents speak out in a logical com putable lan­
guage.

In Proceedings of the 7th European workshop on Modelling autonomous

agents in a multi-agent world : agents breaking away: agents breaking away, pages

132

42-55, Secaucus, NJ, USA, 1996. Springer-Verlag New York, Inc.

ISBN 3-540-

60852-4.
S.J. Russell and P. Norvig. Artificial intelligence: A m odern approach. 1995.
R.E. Shannon. Systems simulation: the art and science. Prentice-Hall Englewood
Cliffs,, New Jersey, 1975.
Y. Shoham and K. Leyton-Brown. M ultiagent Systems: Algorithmic, Game-Theoretic,
and Logical Foundations. Cambridge University Press, 2008. ISBN 9780521899437.
M aarten Sierhuis, Jeffrey M. Bradshaw, Alessandro Acquisti, Ron van Hoof, Renia
Jeffers, and Andrzej Uszok. Human-agent teamwork and adjustable autonom y in
practice. In Proceedings of the Seventh International Symposium on Artificial In ­
telligence, Robotics and Autom ation in Space (i-S A IR A S ), 2003.
M.P. Singh. Group ability and structure. Decentralized AI, 2:127-146, 1991.
R.G. Smith. The contract net protocol: High-level communication and control in
a distributed problem solver.

Computers, IE E E Transactions on, C-29(12):1104

-1113, dec. 1980. ISSN 0018-9340.
Ian Sommerville. Software Engineering, pages 119-129. International com puter sci­
ence series. Pearson/Addison-Wesley, 2004. ISBN 0321210263.
V.S. Subrahmanian. Heterogeneous agent systems. The M IT Press, 2000.
R. Sun.

Cognition and multi-agent interaction: From cognitive modeling to social

simulation. Cambridge Univ Pr, 2006.
K atia Sycara and G ita Sukthankar. L iterature review of teamwork models. Technical
Report CMU-RI-TR-06-50, Carnegie Mellon University, November 2006.

133

M. Tambe. Towards flexible teamwork. Arxiv preprint cs/9709101, 1997.
M. Tambe, P. Scerri, and D.V. Pynadath. A djustable autonomy for the real world.
Journal o f Artificial Intelligence Research, 17:171-228, 2002.
M. Thielscher. Flux: A logic programm ing m ethod for reasoning agents. Theory and
Practice o f Logic Programming, 5(4-5):533-565, 2005.
Adelinde M. Uhrmacher and Danny Weyns. M ulti-Agent Systems: Sim ulation and
Applications. CRC Press, Inc., Boca Raton, FL, USA, 1st edition, 2009. ISBN
1420070231, 9781420070231.
Tom Wanyama and Behrouz Homayoun Far. A protocol for multi-agent negotiation
in a group-choice decision making process. J. Netw. Comput. Appl., 30(3):11731195, August 2007. ISSN 1084-8045. doi: 10.1016/j.jnca.2006.04.009. URL h t t p :
/ / d x .d o i .o r g / 1 0 . 1 0 1 6 /j. jn c a .2 0 0 6 .0 4 .009.
G. Weiss. Multiagent Systems: A Modern Approach to Distributed Artificial In telli­
gence. Intelligent Robotics and Autonomous Agents Series. MIT Press, 2000. ISBN
9780262731317.
Michael Wooldridge. A n Introduction to M ultiAgent Systems. Wiley, second edition,
2009.
Michael Wooldridge and Nicholas R. Jennings. Intelligent agents: Theory and prac­
tice. Knowledge Engineering Review, 10(2):115—152, 1995.
J. Yen, X. Fan, and R. Volz. Proactive communications in agent teamwork. Advances
in Agent Communication, pages 1959-1959, 2004.
N. Yorke-Smith, S. Saadati, L.M. Karen, and N.M. David. T he design of a proactive

134

personal agent for task management. International Journal on Artificial Intelligence
Tools, 21(01), 2012.

135