CPSC 601.72 and CPSC 599.30: Foundations of Multi-Agent Systems - Assignments

In this course, we will have three somewhat connected assignments:

The midterm paper about a cooperation concept
Implementing a multi-agent system rescueing survivors in an urban disaster situation
Writing a report about the implemented system

How the different assignments are weighted within the course grade is explained on the assessment page.

Midterm paper:

Each student will write a paper of not more than 10 pages on one of the following cooperation concepts for agents:

Cooperation by giving out selected information
Starting point:
    Denzinger, J.; Offermann, T.:
    On Cooperation between Evolutionary Algorithms and other Search Paradigms,
    Proc. CEC-99, Washington, IEEE Press, 1999, pp. 2317-2324.
Cooperation using blackboards/shared memory
Starting point:
    Craig, I.D.:
    A New Interpretation of the Blackboard Architecture,
    Tech. rep. 254, Department of Computer Science, University of Warwick, 1993.
Cooperation via a Master-Slave Approach
Starting point:
    Bündgen, R.; Göbel, M.; Küchlin, W.:
    A Master-Slave Approach to Parallel Term Rewriting on a Hierarchical Multiprocessor,
    Proc. DISCO-96, Karlsruhe, LNCS 1128, 1996, pp. 184-194.
Cooperation using Negotiations/The Contract-Net Protocol
Starting point:
    Davis, R.; Smith, R.G.:
    Negotiation as a Metaphor for Distributed Problem Solving,
    Artificial Intelligence 20, 1983, pp. 63-109.
Cooperation using Market Mechanisms/Auctions
Starting point:
    Kate Reynolds and Agorics, Inc.:
    Auctions,
    Series of web pages developed 1996.

Each report should be in article style, containing a general description of the cooperation concept, requirements on hardware and problems that can be solved using it, the general advantages and disadvantages of the concept and a section analyzing the usability of the concept for the multi-agent system that the team of the student will be developing.

Deadline: February 7,2003

Submission procedure
Email me the report as pdf-file.

Implementing a Rescue Team

Consider the following scenario:
A disaster has struck a city (unfortunately, we now know that such disasters are not only caused by nature), houses have fallen down burying their occupants, and fires and/or floods make parts of the city not directly accessible. The only hope of the survivors of the disaster that are alive under the rubble that was their houses is a team of five all-purpose robots that have to work together to rescue as many survivors as possible in the time span that humans can survive under these critical conditions.

It is the task of the student teams to write the control programs of these five robots that will be put into the ARES simulator system. ARES provides a very simplified simulation of the scenario described above. The world consists of grids that each are a "stack" of rubble with mixed-in survivors. For each piece of rubble in such a stack a certain number of robots is needed to remove it (and so to dig into the stack in order to rescue survivors). In the setting of ARES we will be using, whenever survivors are on top of the stack and picked up by a robot they immediately are transported to safety and therefore do not bother the robot. The whole rescueing task is made more difficult by incomplete start information for the robots, their inability to know with total certainty the content of a stack, survivors getting weaker and dying, and the need of the robots to re-energize themselves from time to time.

ARES has a clearly defined interface allowing the agents to tell it about the actions they want to perform and it provides the information about the world that is available due to the particular actions. Time in ARES is organized in discrete steps, but an agent has only a certain amount of computing time before ARES moves the world one step forward, so that efficiency of your agents is rather important. ARES also allows the robots (agents) to give it messages for other agents. More details are available on the ARES website . You will develop a cooperation concept for your 5 robots that should result in rescuing as many survivors as possible. The number of rescued survivors is the score that each team achieves and we will let each robot team tackle several simulations of ARES and add up the scores. Note that survival of the robots is not a necessity!

The team with the highest combined score will automatically achieve an A for their masters. But also all other teams can reach an A by having good ideas for cooperation of the robots or how to explore the simulations to locate survivors. The set of simulations will be determined by me and there will be simulations that your teams have never seen before (but within the given limits).

In addition to getting to know the simulator and your team mates, the main problems the student teams will have to face are deciding on a cooperation concept for their agents, developing exploration algorithms and interleaving them with the need to get robots together for rescueing survivors, and in general dealing with the incomplete information the agents have about the world. This will include determining what information to give to other agents and making decisions.

Deadline: April 4, 2003
Your multi-agent system should be finished this early, so that I have time to run my simulations and so that we can talk about the results in class. Each student team will have to install the system in such a way on an account that I can access it and can easily run it (together with ARES).

Report on your system

The report should be an article on the system you have built. It should contain a description of your agents, their decision making and their underlying ideas. You can (and should) also comment on your experience with ARES. More information about the structure of this report will be available here later in the semester.

Deadline: April 11, 2003

Submission procedure
Again, I want each team to email me the report as pdf-file.

to the timetable for the course.

Last Change: 13/12/2002