General Info

CPSC 609: Foundations of Multi-Agent Systems - Assignments

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

  • The midterm paper about a cooperation concept and
  • the final paper about the design of an agent team for the ARES simulator.

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:
        Maasland, E. ; Onderstal, S.:
        Auction Theory,
        Medium Econometrische Toepassingen 13, 2005, 4-8.

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, and an assessment of the general advantages and disadvantages of the concept.

Deadline: February 15, 2019

Submission procedure
Email me the report as pdf-file before noon.

Designing 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. If this happened to a small city, the only hope of the survivors of the disaster that are alive under the rubble that was their houses is a team of 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. In a big city, there will be several such teams.

The ARES simulator system provides a very simplified simulation of the scenario described above, aimed at providing an environment for (simulated) robot teams that are developed and implemented by students of a MAS class. 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 simplified scenario of ARES, 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 the implementation of your agents is rather important. ARES also allows the robots (agents) to give it messages for other agents.

Naturally, the best use of ARES is to develop and implement agents for it, but the department was not able to guarantee the necessary resources for supporting such an assignment when I had to decide about assignments for this class. Therefore we will have as assignment each student writing a paper presenting a possible design for agents acting in ARES

For all students, the design should reflect the following world rule settings:

  • A rescue team consists of seven robots
  • A maximum of 3 robots is needed to remove rubble (maximal cooperation effort necessary)
  • Robots can replenish energy by sleeping anywhere (energy control)
  • A robot can either do a non-communication action or a communication to the other agents in a turn (messaging/action)
Additionally, each student will be assigned an individual setting for the world rule that defines how scoring is done when robots from several teams perform the SAVE_SURV operation for a survivor (scoring rule).

The report should be an article on the system you have designed. It should contain a description of your agents, their decision making and their underlying ideas, highlighting especially how you deal with having robots from other teams in the world. The report should also comment on the advantages and disadvantages you think your agents have. Note that a student's team of agents does not have to use the cooperation concept the student explored in his/her midterm paper

Deadline: April 10, 2019

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

to the timetable for the course.

Last Change: 8/10/2018