Jörg Denzinger
Department of Computer Science
University of Calgary
Calgary, Alberta, Canada Jordan Kidney Department of Computer Science Calgary, Alberta, Canada Abstract
We present the ARES 2 system, a simulator of a city struck by an earthquake to
be used as testbed for agents written as assignment of a basic multi-agent
systems course. We briefly present the structure of this basic course,
look at ARES 2 from the perspective of an instructor, a student having to
implement agents running in it, and a system developer. We also report on
our experiences in using first ARES and then ARES 2 in 4 courses.
Keywords
Multi-agent systems, competition, cooperation, rescue teams
The area multi-agent systems (MAS) is influenced by many areas inside and
outside of Computer Science. Consequently, teaching a basic course on
multi-agent systems offers quite some challenges: usually students have
rather diverse backgrounds with regard to their knowledge in- and outside
of Computer Science which makes introducing concepts from the wide range
of areas MAS taps in difficult. Also, MAS are distributed systems and
usually are large systems, so that providing practical experiences via
assignments is critical, but it is very difficult to touch in these
assignments on all the key issues in multi-agent systems.
In this paper, we present the general set-up of a basic multi-agent course
aimed at senior undergraduate students and graduate students and how we
provide them with a practical experience in writing a non-trivial
multi-agent system using the Agent Rescue Emergency Simulator (ARES) system.
ARES provides a simplified rescue scenario
similar to Robocup
Rescue (see [RCR]). As the
general setting for ARES we have a simple world struck by an earthquake,
with survivors that are buried by rubble and need to be rescued by "robots"
that are controlled by agents developed and implemented by student teams.
The main tasks of a team of agents are locating survivors and digging
them out. Both requires cooperation of the agents within a team. The newest version
of ARES, ARES 2, allows for having such a cooperative unit of
agents acting alone in a scenario (world) and for having several
groups of agents (built by different groups of students) in the same
scenario. In the later case, we can set up various degrees of competition
and cooperation between these groups.
While ARES is not the only simulator available that can be used as
testbed for multi-agent systems developed as part of a course (other
systems include Robocup jr, see [KSA00],
Biter, see [VB02], or e-Game,
see [FM05]), ARES has
several features that are not present in these other systems. We already
mentioned the fact that ARES allows for a lot of different degrees of
competition and cooperation required to have a good group of agents. While
in soccer, opponent teams are always in competition with each other, in ARES
members of different agent teams may want to cooperate in certain cases. This
allows us to cover much more topics of a basic MAS course with an assignment
with ARES than can be covered by assignments with any of the other available
systems.
Additionally, a main goal in the development of ARES was to allow for
flexibility in how a particular assignment for students is set up. To
achieve this, we incorportaed the concept of so-called world rules
into ARES. A world rule describes a particular instantiation of a group of
features that guides the possible interactions (and consequences of these
interactions) between a group of scenarios in ARES and the agents that are
acting within ARES. ARES allows an instructor to choose from different
instantiations of world rules and it has several different world rule schemes,
like schemes defining the scoring of points for rescues, schemes defining
how costly communication is, schemes defining how many agents at most have
to work together to accomplish things, and so on.
This paper is organized as follows: After this introduction, in
Section 2 we present the
set-up of our course including its high-level structure. In
Section 3, we present our
ARES 2 system, by explaining the basic teaching philosophies behind it and
providing views on it from 3 different perspectives, namely the perspective
of an instructor setting it up for a course, a student having to develop
agents running in it, and a developer who might want to addto/change it.
In Section 4, we report on
our experiences in using ARES and ARES 2 the four times we employed it in
undergraduate and graduate classes. Finally, in
Section 5, we conclude with
some remarks on future work.
The area MAS is, due to connections to many areas within and outside
of Computer Science, a rather large field that does not have a totally
agreed upon core that can be used in basic MAS courses. This, together
with the preferences of instructors, results in rather different such
courses taught at different universities. In this section, we will
present the topics we cover in our MAS course at the University of Calgary
and also present the evaluation and assignment structure of this course
(for both the graduate and the undergraduate variant), since this structure
is heavily influencing our philosophy behind ARES and ARES 2.
The course consists of 13 weeks of 150 minutes of lecture time per week
with one reading week in the middle of the semester (that brings the total
time available for students to do assignments to 14 weeks, at least
unofficially). In the undergraduate variant of the course, the assessment
of students is based on a final written exam (accounting for 40 percent
of the course grade), the multi-agent system a student team is building
for ARES (also accounting for 40 percent) and an individual report each
student has to write about the system his/her team implemented and the
contributions the student made to the team effort (accounting for the
remaining 20 percent). If the report reveals that the student did not
participate sufficiently in the team effort, his/her grade for the system
can be lowered, but so far this was never necessary.
In the graduate variant of the course, we emphasize research a little bit
more by having each student write a midterm paper on a cooperation concept.
Each student in a team should cover a different concept and since we prefer
a team size of 5 (although we were not always able to act on this preference)
we offer as concepts for these reports
The other components of the assessment of a student are the multi-agent
system developed for ARES (accounting for 30 percent), a report about
this system (20 percent) and an oral exam (accounting for 30 percent).
Note that midterm paper and oral exam are evaluations of the individual
student, while the other two components are evaluations of a student team.
As in case of the undergraduate version, a student's grade for the team
component will be lowered if the oral exam shows that the student did not
sufficiently contribute to the team effort. Naturally, the exam covers
mostly the material of the course, but we usually also ask a few
questions about the system developed for ARES.
The materials covered in the lectures are as follows:
Our formal definition of a MAS is based on the definitions in
[Bu92] and we are using them to
drive home the point that on the one hand side a MAS can achieve
properties that not all of its agents have and that even if all agents in
a MAS have a certain property, this does not mean that the MAS
automatically has this property.
In the large section on concepts for interaction and cooperation, we
define what cooperative problem solving is, what is needed to describe
an organization, and then first focus on the basic communication
structures that are available to computer agents, namely communication
via shared memory and communication by message passing. This is then
followed by descriptions of basic cooperation concepts that add to
the concepts from above also the concept of voting. For each concept,
the general idea is described, an example is given and the pros and
cons are highlighted. The section ends with several examples in which
the organisation of the MAS is using several of the cooperation concepts.
These examples are the contract-net protocol (see
[Sm80]), the FA/C approach
(see [LC81]) and some
suggestions for extending blackboards by Craig (see
[Cr93]).
The section on competitive agent environments motivates the additional
problems that arise if agents are competing with each other, like
having to deal with false information or one agent undoing the
achievements of another agent. We then look at these problems from two
perspectives: the perspective of a single agent that wants to maximize
its goals and the perspective of someone who has to set up an
environment in which conflicting agents interact and are supposed to
nevertheless not do certain things. After a short intro into the
rationality assumption, payoff matrixes and Nash equilibriums from
Game Theory, we look into different ways of how to get models for
other agents, since such models can give an agent an edge. We then
look into several examples how environments and their rules can be set
to have a particular outcome of the agent interactions.
Currently, we use the delivery men problem as described in
[RZ98], a very primitive example of
traffic laws, and the problem of false agents in combinatorical
auctions (and the solution suggested in
[YSM00]). The whole
section finishes with a short look at coalitions.
More information about the course and the course materials can be found
here. For the graduate version of the course, there are no pre-requisites,
so that we have to introduce from time to time concepts from AI. For
the undergraduate version, the pre-requisites are the basic AI course and
the basic operating systems course; nevertheless, we repeat briefely the
necessary concepts from these courses when they are needed.
ARES (see [BDK03]) is a very
simplified simulation of a city struck by an earthquake. This simulation
is used to access teams of agents in different scenarios (or worlds). While
in ARES it was only possible to have one team of agents in a scenario, ARES 2
allows several such teams, adding to the experience the possibility of
direct competition between teams (but also allowing for cooperation, which is
unique to ARES 2).
In this section, we will first present our motivation in building ARES and
explain our philosophy behind it. Then we will describe ARES (and ARES 2)
from the perspective of an instructor using it in a class. This is followed
by a view on ARES from the perspective of a student having to build agents
to act in ARES 2 scenarios. Finally, we will take a look at ARES from
the point of view of a systems developer, explaining its general structure.
It is our strong belief that hands on experiences should be an integral
part of any multi-agent systems course. While this still allows for many
different approaches as to how the hands on experiences can be achieved,
we also think that experiencing the problems on all levels of implementing
a multi-agent system is the best way to have the students understand what
they might face later. This means that we want to cover everything, from
developing a communication protocol over implementing it for agents
potentially residing on different computers to developing a cooperation
concept suitable for the task to even dealing with agents not under the
control of the students. Naturally, this wish list is not without problems,
especially if the students are learning about MAS in parallel to doing
assignments, respectively developing and implementing a MAS on their own,
as is the case in our course.
In addition to coverage of topics and problems, there is naturally also
a wish list from the general educational perspective. First of all, with
the Internet and the resulting ease in not only getting information but also
in "copying" it, plagiatism becomes more and more an issue. While clear rules
and punishment of rule breakers is one way of dealing with this problem, it
also requires quite some effort by the instructor towards detection of
plagiatism. One of our goals in developing ARES was to avoid the problem
(following examples in MAS about avoiding conflicts) by being able to
easily modify the task for which the students build an MAS in many
different ways. The concept of world rules provides us with this ability.
Another important point from a general educational point of view is the
motivation of the students. The more the students like doing an assignment,
i.e. building an MAS, the more they will learn by doing it. For our design
of ARES, this had several consequences:
These two wish lists resulted in the following key decisions we made
regarding first ARES and then ARES 2. Following the lead of the RoboCup
Rescue initiative (see [RCR]), we have
chosen locating and rescueing survivors in a city struck by an earthquake
as the general problem realized within the testbed system we built. In
contrast to the RoboCup Rescue simulator, that is used for competitions
between systems developed by research groups all over the world and intended
to provide very realistic simulations of many aspects of such a disaster, we
abstracted away a lot of the complex details while still having the key basic
tasks. In fact, several of our abstractions led to possibilities for world
rules, i.e. the possibility to neglect certain aspects or keep some primitive
version of an aspect in (for example, replenishing energy by "sleeping"
anywhere or charging at particular locations). Form the motivational point
of view, only our simplified worlds give the students any chance to be
successful in the general task; four months are way too short to produce
anything meaningful (and original) with the RoboCup Rescue simulator.
When we thought about adding to ARES the possibility to have the agent teams of
several student teams interact within one scenario, the need to keep the
task manageable within four months required from us to add example
agents to ARES 2 that provide a skeleton that shows how to connect to
ARES 2 and how to communicate during a scenario run. More about this in
Section 3.3.
The interaction between agents and ARES is organized in rounds (or turns),
where ARES allots to each agent a certain amount of computing time to
decide on its actions. After ARES has received actions from each agent, it
computes the results of these actions in the scenario world (note that
some things, like removal of rubble, only happen if several agents perform
a certain action) and then a new round begins. When it is the turn of an
agent, it first receives a world update (centered around the agent position and
with a certain amount of uncertainty) and then the messages from the
other agents. After that, the agent has to make good use of its allotted
computing time to decide on its actions. While a round-based simulation
is easier to deal with than interactions in real time, the fact that
agents have a limited time for computing their actions adds at least a
real-time flavor. Additionally, the fact that messages from an agent to
other agents are delivered in the next round makes students well aware of
the fact that communication has a cost (which can even be strengthened, see
later). This is due to the fact that the survivors the agents try to rescue
start out with a limited amount of energy and loose some of this energy
every round up to the point of having zero energy which means that the
survivor died before being rescued. Therefore, using as few rounds as
possible to achieve objectives is very important in general.
From the perspective of an instructor, there are 3 tasks to perform in
using ARES 2 as a testbed for agent teams written by students as
assignment:
Before we take a look at the world rules and their possible instantiations,
we first provide some basics about ARES 2, using screenshots of the viewer
agent.
A world scenario in ARES 2 consists of a rectangular grid, where each grid
field is either a stack of layers or a "special" field. A layer is either a
piece of rublle, with an
associated number of agents needed to remove it and the amount of energy
that has to be spent by these agents, or it is one survivor or a survivor
group, with an associated number indicating the life energy of them. A
special field is either an instant killer grid, a fire grid or a recharging
grid. The effects of the instant killer grid and the fire grid are the same:
an agent stepping on it is "killed", i.e. taken
out of the run by ARES. We made the distinction to allow for the possibility
of spreading fire in later versions of ARES. A recharge grid, as the name
suggests, allows agent to recharge their energy, if the world rules are
set so that this is the way to regain energy for agents. Note that a recharge
grid also has a stack of layers. The following picture
shows these four types of grid fields:
In the world viewer, the graphical representation of a normal grid field
with its stack of layers shows only the top of the stack in the lower left
corner (with the number indicating how many agents are needed to remove a
piece of rubble, respectively how many survivors are there). The color in the lower right corner indicates the amount of energy
needed to step on the grid (a legend of the colors is provided by the world
viewer when you look at a whole world, see later) and at the top of the
representation the agents that are currently on the grid will be displayed (with
the different colors indicating agents in different teams and the number
identifying the agent within the team).
The following picture is a view on a (small) complete world as seen in
the world viewer.
In addition to a view of the world, we have a scrollable field providing
information about the world, action buttons that allow to change
the scale of the world display, the scrollable legend of the move cost
colors (MV Legend) and buttons that allow to connect agents to the
world and start a run.
By clicking on a grid field, we get an additional window providing information
about this particular field. The following picture is an example of
such a window:
In addition to the display of the field, we get the general grid information
and a scrollable field displaying the layers of the stack for this grid.
If we click on one of these layers, then the field on the right displays
the information associated with this layer.
We use the world viewer also to create world scenarios, but before we go
into details, we will first look at what world rules ARES 2 allows an
instructor to instantiate.
The idea of world rules -we from time to time also call them environmental
rules- is to allow for different general ways how agents and the world
scenarios interact. The instructor selects one instance of each particular
world rule for a course and the students know which instantiation
is chosen and develop their agents with this in mind. Many of the world rules
can be seen as particular constraints on the robots that the agents are
supposed to control. Note that the effects of the world rules are connected,
so that changing to a different instance of one world rule without changing
the others nevertheless might require to rethink decisions made about
the other rules. The world rules in ARES 2 are as follows:
The Messaging/Action Rule allows for four different instantiations:
Obviously, if the decision has to be communication or doing something in the
world, then coming up with cooperation concepts that require nearly no
communication is very important. If communication does not cost a turn,
then keeping the other agents updated is not costly and this in turn
allows for very well-informed agents. In ARES 2, there can be more than one
agent team and we can allow communication with them or not. However, if
other teams understand what is communicated is naturally not guaranteed.
The Maximal Cooperation Effort Necessary Rule essentially defines how many
agents at most are necessary to remove any piece of rubble in a world
scenario. So, the instantiations are positive natural numbers (0 is possible,
but not very interesting in our opinion). Note that not every piece of rubble
has to require this maximal number of agents to be removed. If we instantiate
this rule with a number higher than the number of agents in a team (but lower
than the total number of agents in a scenario) and have most pieces of rubble
requiring the maximum number of agents, then cooperation between agent teams
is required. But naturally the Scoring Rule will influence the cooperation
also a lot.
For the Energy Control Rule, we have two instances:
Obviously, choosing the second instance requires much better and careful
planning by the agents than the first instance.
The Scoring Rule was added in ARES 2 to deal with having several agent teams
active in a scenario. While with only one team scoring is simply done by
counting the number of survivors rescued during a rescue run, the fact that
several agents might execute the SAVE_SURV action allows for several
possibilities how scoring can be done. The possible instantiations
are
The different instantiations obviously influence the balance between
cooperation and competition between the agent teams quite a lot. Some
instantiations allow for parasitic behaviors.
The instantiations of the Information Accuracy Rule determine how much
the information the agents get from ARES is distorted. An instantiation is a
percentage value. Information distortion is used when the agents get the
initial information about a world scenario, when an agent performs the
OBSERVE command and with regard to what an agent is told about the
deeper levels of the stack of the grid field it is on.
The Thinking Rule determines how much processor time an agent gets each
round. Small amounts of time obviously make the initial planning of
the agents more difficult and push them towards more reactive behavior.
An additional decision an instructor has to make when setting the world rules
is how many agents are there in a team. This selection has some connection to
the Maximal Cooperation Effect Necessary Rule.
In order to evaluate the agent teams that the students develop and
implement, several world scenarios are usually needed. For our courses, we
use several randomly generated scenarios (fulfilling the chosen instantiations
of the world rules, obviously) and several purposefully generated scenarios
that test extreme conditions ("pathological" ones), like, for example, if
the agents can split up to rescue survivors that are only lightly burried,
or how the agents react if several grids show exactly the same survivor
life energies. We also test how quickly the agents come together to form
subteams necessary for rescueing survivors, how flexible the agents are
(do they do detours to rescue survivors that they can rescue alone), and
how they deal with obstacles and isolation.
The scenarios developed for testing how teams behave with other teams around
usually are set up in such a manner that there are areas where only one agent
from each team is present and where rescueing survivors requires cooperation.
But we also have areas where each team alone can, in theory, rescue every
survivor. We use fire and instant killer grids as borders for those
areas. Such scenarios usually are developed with a certain number of teams
in mind and special starting positions for each agent of a team. We then run
these scenarios several times with each of the student teams taking on
the role of each of the teams for which we developed the scenario.
For devloping a world scenario, an instructor can either start with an
empty world (useful for the pathological worlds developed to test specific
behavior), an already created world or (s)he can let ARES create a
random world. Then the instructor can use the world viewer to fine tune
individual grid fields. The following picture shows a screenshot of the
world viewer together with the window that allows building and fine-tuning
of worlds.
The window to the right allows to build random worlds by entering their
sizes, wether special grids should be created randomly, what number of
survivors should be put (randomly) into the world and how the
Maximal Cooperation Effort Necessary Rule is instantiated (Max RB RM).
After creating such a world scenario (or loading it), the instructor
can work on individual grid fields using this window and the grid field
details window from above. With the grid field details window it is
possible to create/manipulate the stack of layers while with the
window above, the grid type and its move cost can be manipulated. We can also
put a particular agent on the grid.
We have an ARES website (see [ARES])
that mainly aims at providing detailed information on how to create agents
that interact with ARES. Therefore, in the following, we will provide
more a brief overview than an in-depth description.
From the perspective of the students their main task is the
development and implementation of a team of agents. These agents must
interact
together through the simulation setup within the ARES system. The
students must first learn what is required from them to
make agents that can interact with the ARES system to participate in a
simulation. This will require the students to learn the following
tasks:
As already stated,
for the first task the students can study the information presented on
the ARES website (see [ARES]).
The site provides information on the use
of the ARES system along with in-depth explanations of the connection
procedure and communication language between the agents and the ARES system.
The tasks of understanding and implementing steps two and three
from above are not difficult, but they are time consuming. The time
used to implement these technical details pulls away from the time that
could be spent more productively working on the models that need to be
developed within the agents. As a result of this we have developed a
basic package in C++ that handles these technical details for the
students, presenting them with an easier interface for the beginning
phase of the implementation of their agents. Below is a basic diagram and
explanation of the package that is available to the students.
The center of this package is the "Base Agent" component. This
component handles the following tasks:
To use the features provided by the "Base Agent" component the
students must inherited and fill in the required list of functions.
These functions are used for communication between the base agent code
and the students agent code. The communication between the base code
and the students code is done through a callback mechanism. When
specific events occur the base code calls a predetermined function
from the students code.
When a message or action must be sent to the ARES system, the
students' code can call functions from the base code. The base code
then handles formating the message and sending it to the ARES system.
Also provided by the package is a basic set of classes that can be
used or modified to represent information in the world presented by the
simulation.
The last two tasks required by the students are to understand what
information the agent has to work with and the implementation of
the code for their agent(s). Below is a short description of the
types of information the agents are presented with during a
simulation:
The actions available to an agent are as follows:
The result of most actions is a message by ARES informing an agent about
its surroundings and the energy consumed by the last action.
During the time an agent has to to do its computations for a round it can
send to ARES several actions. Depending on the instantiation of the
Messaging/Action Rule, ARES either lets the agent perform in the simulation
only the last action sent by it or the last non-message sending action and
all message actions.
As the existance of an ARES 2 system suggests, there is a need to produce new
versions of ARES. This is not only due to errors found in the system,
adjustments to new run environments or the need to improve the interface,
the area multi-agent systems is also constantly expanding and therefore
it will be necessary from time to time to adjust ARES to allow for coverage
of new MAS concepts. We were aware of this when we created the first version
of ARES and we tried to make expanding ARES as easy as possible by already
using some concepts from MAS that have proven to be useful from a software
engineering point of view. But naturally a developer faces a more difficult
task than our students. In the following, we will provide a brief overview
of the tools we used and of the structure of ARES itself.
From the perspective of a developer there are two main areas
that must be understood before additions can be made to the system.
Currently the ARES 2 system will only run under the Linux operating
system. As a result, the developer should have a familiarity with the
Linux operating system and the required C++ libraries for the ARES
system. If a Linux machine is unavailable alternatives
such as a Linux emulator can be set up on a windows machine, A
suggested emulator to use is Cygwin (see [CYGWIN]).
The technical skills required will involve an understanding of both C++
and Java. The developer must also be familiar with the AWT package from
Java for modification of the user interface provided with the system.
The developer should also have a basic understanding of TCP network
communication in both languages. Below is a list of the external tools
that were used in the development of the ARES system:
The major components of the ARES system can be broken down into three
main agents itself:
The graphical viewer agent was developed in Java and both the
simulation and information keeper agents were developed in C++.
Below is a more detailed diagram of all the major components within
the ARES system. Each of these components is realized within one of the
three main agents mentioned above.
ARES also protocols each simulation run. By just using the viewer agent
it is possible to view runs several times without having to repeat the
simulation run itself. This allows, for example, to view a run from the
perspective of different agents or of particular grid fields.
Evaluating the usefulness of a tool like ARES 2 objectively is very difficult.
The methods used in areas like human-computer interaction all rely on either
human users trying out all tools in a set of tools and reporting on their
preferences or having different groups of users doing a particular task,
one group with the tool and one without, and comparing the results of
the task (resp. some performance measures on the task fulfillment).
For a tool like ARES, that is so fundamentally coupled with our basic MAS
course, both approaches cannot be applied: there is simply no time to
let students work with several tools and there are not enough students, yet,
to allow for control groups. Even more, there is a clear ethical problem
involved: if the tool to be evaluated is really better in helping students
learn teh material of the course, how can we ask students to not use it
and risk getting worse grades than the students that had the advantage of
working with the tool? Naturally, the same problem might also occur with
groups using different tools.
Due to these problems, we will not try to do a scentific evaluation
of ARES and ARES 2 in the sense sketched above. Instead, we will first
report on the systems the students developed in the courses, which shows
that by using ARES, resp. ARES 2, the students developed interesting
solutions, which indicates mastery of the subject. Additionally, we will
provide some data out of the evaluations of instruction done by our
university that shows that the course as a whole is well received by
students and we will present some remarks from students that
were made either with the university evaluations or in their papers.
We have used the original ARES system in 2 graduate courses and we used
ARES 2 in one undergraduate and two graduate courses (one of the graduate
courses shared lectures with the undergraduate course). In general,
the students were very enthusiastic about developing their agent teams and
the fact that the student team whose agent team performs best over all
the world scenarios we use for evaluation gets a prize (and is guaranteed
an A for the system part) created a very healthy competitive athmosphere.
The fact that we ourselves do not know what the best concept for a particular
combination of instantiations of the world rules is (and that we became aware
of this fact the very first time we used ARES, see below) keeps our influence
on the students limited and has resulted in very interesting concepts and
systems.
The first time we used ARES, we instantiated the world rules as follows
(see also [BDK03]): The
Messaging/Action Rule allowed agents to either send messages or perform
a non-message-sending action. The Maximal Cooperation Effort Necessary Rule
was instantiated to 5, which was also the number of agents that a team
had. The instantiation of the Energy Control Rule allowed agents to
gain new energy by sleeping wherever they wanted. The Scoring Rule did not
exist in ARES and the Information Accuracy Rule allowed for a distortion
of 5 percent. We gave the agents 1 second CPU time for their decisions.
The students created rather different concepts for their agents, but the
best team used an approach that we now call the "superagent" approach.
Essentially, the cooperation strategy is to bring all five agents together
(initially the agents communicate their positions and come up with a good
meeting place where they then come together) and then have them move
together through the world. Since they are all on the same grid field,
they collect the same information and since they use the same decision
algorithms, they do not require to communicate their plans to each other
(this course was taught at the beginning of 2002, so before
[PT02] proved that this is the best
way to minimize communication). The only communication necessary after
the superteam was joined was to announce to the others when an agent ran
out of energy, so that the whole team then went to sleep. Due to the chance
that really all 5 agents might be needed, keeping them together is usually
the best solution (except for pathological scenarios developed to make
this look bad; unfortunately, we did not think about that so that this first
time we had no such scenarios in our evaluation set). Naturally, this
was not the kind of concept we wanted to be developed, so that for the
following times we taught the course we had scenarios where the superagent
approach performes very bad and we also used instantiations of the
world rules that we think make the superagent approach not a good idea.
The second time we used ARES, rather shocked by the results of the first
time, we instantiated the world rules as follows: The
Messaging/Action Rule now treated messages special so that agents could
communicate in addition to performing a non-message-sending action. We still
had 5 agents per team, but now we instantiated the Maximal Cooperation Effort
Necessary Rule to 2, so that the superagent approach would clearly waste
resources. Additionally, we wanted to see what the students will do with
the 5th agent. The instantiation of the Energy Control Rule allowed agents
to sleep everywhere, again. The Scoring Rule still did not exist and we
left the instantiations of the Information Accuracy Rule and the Thinking Rule
as they were before.
In this course, we had 3 student teams and they choose rather different
approaches. Each team was able to be the best team for at least 2 of
our evaluation scenarios and the winning team won 2 more scenarios than the
next best team (and it also had the highest number of survivors rescued
over all the scenarios). The winning team used a master-slave concept
where the odd agent off acted as the master for two slave teams. Each
slave team used for its coordination the superagent approach (we told
the students about the outcome of the first time we taught the course).
The master wanders through the world identifying grids that likely
have survivors. It compiles a list of such grids and whenever a slave
team needs a new job, it sends to this team the coordinates of the
grid nearest to the current position. Into this list of grids the master
also integrates information it gets from the slave agents who send
information about their surroundings to the master every round (due to
communication now being not so costly).
In 2004, we had ARES 2 available and we used it for the first time with
both a graduate and an undergraduate course. The Messaging/Action Rule
was instantiated so that messages can be passed in addition to a
non-message-sending action every round and only messages to the own
team were allowed. We now had 7 agents per team so that we could
instantiate the Maximal Cooperation Effort Necessary Rule to 3 (so
essentially we wanted this to be similar to the previous course, but
throwing more agents in the mix). The instantiation of the Energy Control
Rule allowed agents to sleep everywhere, again. The Scoring Rule was
instantiated to all teams getting credit for a rescue of survivors that
had an agent performing the SAVE-SURV action. The instantiations of
the Information Accuracy Rule and the Thinking Rule stayed as before.
We had 6 undergraduate teams and one team of graduate students in this
year. The winning team was an undergraduate team with the graduate team
coming in second best (but clearly beaten by the undergraduate team; it
should be mentioned that in this undergraduate team we had 2 students who
were at the end of their degree and took just this course). The winning
team made good use of the fact that they could communicate as much
as they wanted by having a kind of distributed blackboard that
contains all the information known to any agent (each agent has a copy and
updates it every round using the messages from the other agents). The
agents are not forming permanent subteams but form ad-hoc teams whenever
the need arises. When an agent encounters a grid field with survivors and
rubble requiring more than one agent to remove and this seems to the
agent the best field to work on, this agent places a beacon on this
grid (which is naturally communicated to the other agents). It then computes,
based on the global information on the blackboard, if enough other agents
will see this beacon as the best place for them to work on. If yes, it
will wait, else it will look for another field to work on.
As in the previous year, the students make use of the fact that, if global
information consistent between agents is available, communication can
be avoided by having the agents use the same decision functions (note
that this means that agents act one turn earlier, since they do not have
to wait for a message that they will get in the next round). If new information
becomes available in the next round that indicates better grid fields to
work on, agents that the round before were intended to help another
agent can change their goals. If no other agent will substitute for such an
agent, the waiting agent will then also look for a better field and will
delete the beacon.
With regard to dealing with other teams we had several teams that just
ignored the other teams. The winning team dealt with other teams by
trying to cooperate with them initially. If other teams were also cooperative
they continued to cooperate with them, i.e. they assumed that agents from
these teams would help digging when standing on the same grid field and
digging was necessary. But the moment another team was not cooperative, i.e.
the own team and the other team would have been able to remove a piece of
rubble but the rubble was not removed in the next round, they blacklisted
this team and from then on did not cooperate with agents from this team
anymore.
The last time we taught our course was in Winter 2005 as a graduate
course. Naturally, we used ARES 2 and set the world rules as follows:
The Messaging/Action Rule was instantiated as in the last year making
communication not very expensive. We again had 7 agents per team and set
the Maximal Cooperation Effort Necessary Rule to 3. We changed the
instantiation of the Energy Control Rule to requiring that agents
recharge their energy at charging grids only. Scoring Rule, Information
Accuracy Rule and Thinking Rule were instantiated as in the last year.
Having to recharge at specific locations forced the students to deal with
the problem that their agents are initially not given the move costs on
the grid fields. Therefore, all teams came up with ways how to
estimate costs for paths from one grid field to another and how to
make use of the information on some of the fields that was gathered
earlier. The winning team started out with the flexible teams that won
the year before but tried to make use of the fact that agents coming together
for a rescue tend to be in a good situation to continue on if good
targets requiring several agents are around. The students tried to keep
such teams together as long as breaking up did not promise a
substantially better result. The move cost estimation of the winning team
was tighter than the estimation of the other team, but in none of
our evaluation runs did they loose an agent due to running out of
energy. With regard to cooperation with other teams, starting out
cooperating and having a blacklist was the common approach.
All in all, as initially stated, both we and the students are very happy
with our experiments with ARES and ARES 2. The overall evaluation of the
course (according to the University of Calgary's official evaluations
of instruction) has been 5.2 out of 7 in the first year, 6.5 in the second
year we used ARES, 5.8 from the undergraduates (5 graduates were too few
to be questioned) the first year of using ARES 2 and 6.67 from the graduate
students in 2005. Unfortunately, none of the more detailed questions by
the University address tools used in the course. This also means that
only a few students commented on ARES in the University evaluations. Here
are the few comments from these evaluations:
As stated before, we also asked the students to comment on ARES and
ARES 2 in the system descriptions they had to produce. But this means
that the student is, in contrast to the University's evaluations, not
anonymous and even more the comments are part of a paper that is graded,
so that we do not claim that the following comments are an objective
picture of what the students thought about ARES and ARES 2. Additionally,
every student (or student team in case of the graduate courses) had
to comment on ARES, so that we obviously have to make a selection. We tried
to select comments addressing how the different goals we had with ARES and
ARES 2 are fulfilled (in the eyes of the students).
The students also provided quite a few suggestions for future versions
of ARES. While many of these suggestions would make working with ARES
more difficult (it is always amazing what students that are through with
something are willing to let their successors do), some suggestions
are quite interesting, as the next section shows. An interesting effect
came out of our ability to vary the world rule instantiations. Not only
is plagiatism no issue, we could talk rather freely about what ideas
students had in earlier years and some of the student teams picked up
on this, as documented by the "evolution" of the winning teams.
We presented the ARES 2 system, a simulator for rather abstract worlds in
which agents have to locate and rescue survivors in a city that has been
struck by an earthquake. ARES 2 allows for agent teams written by different
student teams to interact in such worlds and due to the concept of world
rules we can vary the need for cooperation and competition between
these teams. The world rules also allow to put different foci on what
the agent teams have to accomplish and how this is done. ARES 2 enhanced
the learning experience for students in our basic multi-agent
systems course a lot by providing a wide range of hands-on experiences.
While there are a lot of combinations of the instantiations of the
current world rules that we have not tried out in our courses, we do already
think about additional world rules for future ARES versions. Fire that can
spread, survivors that have to be delivered to collection points or
rubble that does not vanish but gets dropped on another grid file are a
few of the ideas that we had or that were suggested by students. With the
ARES 2 version we managed to include some coverage of the course material
on competitive multi-agent systems into the assignment. But topics like
modeling other agents or learning agents will not be within reach of
assignments that are done in parallel to learning the material the first
time (as some of the students' comments pointed out, the time is already
rather limited so that they could not use all of the ideas they had).
Nevertheless, we think that ARES already can be used in
assignments that are aimed at covering these topics -in a follow-up
course to our current course, for example- and there are also a lot
of additional rather simple features that added to ARES can enhance the
learning of these advanced materials. Examples are bystander agents that
have unknown behaviors (that could be modeled) or world information updates
by ARES for the teams during a run.
denzinge@cpsc.ucalgary.ca
http://pages.cpsc.ucalgary.ca/~denzinge/denzinger.html
University of Calgary
kidney@cpsc.ucalgary.ca
1. Introduction
2. Our Basic Multi-Agent Systems Course
Each student gets one source as starting point and is expected to find
additional papers so that (s)he can provide in the paper a general
description of the concept and also suggestions how this general concept
can be instantiated to be used by the agents the student's team has to
implement for ARES. Note that due to the different world rule
instantiations (see Section 3.2)
this second part of the paper is usually different from semester to
semester. The midterm paper accounts for 20 percent of the course grade.
This provides some motivation about MAS and a brief history of the field
mainly organized around important papers.
This section provides some formal definitions around the term agent
and agent properties (making rather clear the limitations we face here
and the fact that there is no agreed upon definition for agent within
the field) and looks into several approaches to model agents (i.e.
situation-action pairs, rule-based modeling, state-based modeling,
object-oriented modeling, role-based modeling, BDI logics).
This is divided into three parts: formal definitions and properties,
interaction and cooperation concepts, and competitive agent environments
While many researchers see the ability to learn as fundamental to an
agent (even researchers that are not doing research in learning), we
have to admit that this section of the course is mainly in it since
learning is a major research interest of us. We start with a short
introduction to learning in general, provide an example for how MAS
adds an additional dimension since agents can use different kinds of
learning and then provide an example for reinforcement learning in
the context of MAS (namely the DFG algorithm of Gerhard Weiss, see
[We95]) and one example for
evolutionary learning (here we present the different stages of our
OLEMAS system, see
[DF96],
[DK00], and
[DE02]).
While this section should provide quite a few examples, we usually are
only able to cover two systems. We have chosen one example with rather
complex (intelligent) agents (namely the MARS system of
[KMM93]) and one example with
very simple agents (that form processing pipelines for classifying web
documents).
3. ARES 2
3.1. Our basic philosophy
3.2. ARES 2 from the perspective of an instructor
standard grid instant killer grid fire grid recharging grid 
3.3. ARES 2 from the perspective of a student
The task of updating other information about the world is left up to the
students.
3.4. ARES 2 from the perspective of a system developer
4. Experiences with ARES and ARES 2
Naturally, the students also pointed out to us any programming mistakes
within ARES, resp. any shortcommings of the documentation that they
encountered.
5. Conclusion and Future Work
6. References