University of Utah

School of Computing

Multiagent Systems

CS 6380
Spring Semester 2008
WEB 1248  TH 12:25- 1:45
Instructor: Thomas C. Henderson

Overview of Course

Course Objectives

The course covers fundamental notions of: Methods will be applied to a practical application (in Matlab).

Prerequisites

The prerequisite is  knowledge of programming, data structures, processes, and language syntax, Matlab and C; (CS 5300/6300 preferred).

Course Description

We will work on understanding multiagent systems. 

Software Used to Support Class

Students will develop on a Unix environment in Matlab. 

Required Materials

We will use:

Multiagent Systems, edited by Michael Wooldridge, Wiley, 2002 (required)

Assignments

There are 3 major types of assignments:

Class Syllabus

The lectures will cover the text on the following schedule:
 
                 Date                 Topic   Material (Wooldridge)     Assignments




Weeks 1 and 2
 Intro to Agents, Matlab, Simulation
 Chapters 1,2
   Problem 1 ,  Project 
Weeks 3 and 4
 Deductive Agents
 Chapter 3
   Problem 2 ,  Project    
Week 5
 Reasoning Agents
 Chapter 4
   Problem 3 ,  Project  
Week 6
Reactive Agents
 Chapter 5
   Problem 4  
Weeks 7 through 10
 Agent Negotiation
 Chapter 6
   Problem 5   
Weeks 7 through 10
 Agent Communication
 Chapter 7
   Problem 6   
Week 11 Spring Break!
 Spring Break!
Weeks 12 and 13 Agent Communication
 Chapter 8
   Problem 7 
Weeks 14 through 16
 MultiAgent Systems
 Chapter 9
   Problem 8   

Class Schedule and Assignments

The lectures and assignments will cover the text as we progress through the quarter. Class attendance is mandatory. Assignments will usually be handed out on Tuesday and due Thursday of the next week.

Instructor

Thomas C. Henderson, Professor

E-Mail:   tch@cs.utah.edu
Phone:     801-581-3601
Fax:         801-585-3743
Office Hours (3450 MEB):    In-class and by appointment.

Grading Information

The grading distribution will be as follows:
 
Problems:        50%
Project:            40%
In-Class:          10%

Your are expected to make a good effort on all assignments.  I will assign a grade based on how reasonable your solution is given the difficulty of the assignment, the time required, and the style and content of the solution.  Very few jobs evaluate performance on a very quantitative point system; my goal is to look at all your work, and to assign a grade based on your participation, effort and results.  It's better to ask questions before and during an assignment, than to try and understand what went wrong after it's due.  The proportions given above delineate how I intend to apportion the weight of the various work in the course.

Problem 1

     Due: 22 January 2008 (at class time)

     Design and implement in Matlab a simulation code for the Tileworld scenario as described in the text with :

      * 2-D grid (array)
      * an agent
      * tiles
      * obstacles
      * holes
      * agent can move right, up, left, down
      * if next to tile, agent can push it
      * obstacles are unmovable and untraversable
      * goal: fill holes with tiles
      * start: randomly generated, based on parameters
      * during: holes, tiles, obstacles randomly appear and disappear
      * parameters: frequency of appearance and disappearance of each type object; time interval for hole disappearance [0,Inf].
      * performance measure based on number of steps, number of holes filled:

               number_of_holes_filled/number_of_holes_that_appeared

      1. Develop basic simulation with agent that repeats:

         - Moves randomly until next to tile
         - When next to tile
            - Pushes tile random direction for random number of steps
                  until tile goes in hole or disappears
     
        A. Verify that code works correctly.
        B. Determine how parameter changes relate to performance.
        C. Demonstrate an adequate statistical framework, and discuss
           confidence in performance estimation results.

      2. Extend simulation to other smarter behavior and compare result.

      3. Run both 1 and 2 with multiple agents.

More on TileWorld (see Pollack paper in references link):
Come up with some version that is simple for a first coding exercise (e.g., limit size of holes to 1 square)

Problem 2

     Due: 5 February 2008 (at class time)

Do the following exercises out of Chapter 3 in the text:

Problem 3

     Due: 14 February 2008 (at class time)

Do the following exercises out of Chapter 4 in the text:

Problem 4

     Due: 21 February 2008 (at class time)

Do the following exercise out of Chapter 5 in the text:
Assume the following functions are available:

function agent = MAS_agent_ID(filename)
%
% On input:
%     filename (string): name of agent behavior function
% On output:
%     agent (int): agent ID

function percepts = MAS_perceive(agent)
%
% On input:
%     agent (int): agent ID provided by MAS_agent_ID
% On output:
%     percepts (percept data structure):
%           base_dir (float in [0,2*pi)): relative direction to base (from agent heading, positive rotation left)
%           range (360x1 vector): range to nearest object in that direction (360 degrees from straight ahead)
%           type (360x1 vector): type of object in that direction

Your name of your behavior function must be provided in a file named:

MAS_A_<your name>_<num>.HDR

where <your name> is:

      Tom: agents contributed by Tom
       Jon: agents contributed by Jon
      Matt: agents contributed by Matt
      Polly: agents contributed by Polly

and num is a unique, positive integer

The behavior function should take no arguments, and shoudl return an integer representing the requested action.
Actions are defined by a global:

   global ACT_GO ACT_DROP ACT_PICKUP

Problem 5

     Due: 4 March 2008 (at class time)

Do the following:

Problem 6

     Due: 20 March 2008 (at class time); Use Lab Report to convey results.

Do the following:

  1.  Develop an agent in the Mars environment that can perform the following tasks

       T1: Go to Base
       T2: Go to Sample
       T3: Carry Sample
       T4: Survey for Samples

       Explore how different utility functions on subsets of these tasks influence the following measures:

           * M1: Total number of samples delivered to base by all agents
           * M2: Total distance traveled by agents Consider and discuss the parameters involved and how they affect the outcome as well

  2.  Develop a multiagent monotone concession protocol; what properties, if any, can you prove about it?  How does it perform in the Mars world?

Problem 7

     Due: 8 April 2008 (at class time); Use Lab Report to convey results.

    1. Develop a (minimal, but sufficient for this problem) ACL in the Mars simulator.
 
         Design Due:  Thursday 27 March for discussion in class

    2.  Design a multi-type agent system to explore Mars for samples.  This should include the following agent types:

       Each action has a specific cost for each of these agents.  As a starting point (this may need modification!):
     Assume that the base has an infinite supply of energy; furthermore, assume that there is 1 Leader, 10 Surveyors, 3 Collectors and 5 Suppliers.  Explore the question of whether a fixed set of tasks communicated once by the leader and executed is more efficient than a strategy based on communicating.  Develop reasonable measures of performance.

Problem 8

     Due: 25 April 2008 (5pm); Use Lab Report to convey results.

    Continue the development of the multi-agent Mars exploration scenario. The goal is to explore the effects of interaction of multiple teams during exploration.  To this end, each of us will develop a team with our own strategy, and then we will test them together in a common simulation.  As agents explore, if they are within range to perceive another agent, they may propose an auction for either energy or information.  This involves extending the Mars Agent Language to include this possibility:

     * auction <type> <amount> <amount>

        where <type> is a 1: meaning energy for sample locations
                                 or 2:  meaning sample locations for energy

Each agent should have a basic exchange rate set by the Leader, and a local exigency rate (if low on energy or knows lots of sample locations)

We will test a first round by Thursday 17 April.  Then final systems need to be available by Tuesday 22 April so everybody can test them and produce a final report by the 25 April due date.  The issues to explore include performance (on selected measures) of different strategies.  The report should explain:

Project 1

  Project Assignment 1

  Due: 22 January 2008

  Produce a description of your project.  This should be some sort of investigation of multiagent scenario, e.g.:

    * Capture the Flag: two teams of agents, each has a flag and the other team attempts to capture it.

    * Web-based info production: agents interact with human, and seek requested information from web.  May store info and share with other agents.

    * Map analysis: given a raster image version of a map, agents use a blackboard to post and request info as they produce a semantic interpretation of the map (e.g., where are the roads and what are their names/numbers), text analysis, topographic feature extraction, etc.).

    * Furniture moving scenario: multiple robot agents must coordinate actions in order to move furniture.

  This must be a narrative that describes the scenario, the goals, the measures of performance and the major questions to be studied.

Project 2

  Project Assignment 2

  Due: 5 February 2008

Start Development of the project.  We will iterate over these two weeks and discuss breadth, depth and goals.

Project 3

  Project Assignment 3

  Due: 21 February 2008

           Write a detailed proposal.  This should state goals of project, background review, method, and timeline.

Assignment Due Time

Unless otherwise stated in an assignment, all assignments will be due by classtime on the assignment due date. The time that we use for an assignment is the last modified time of the source file in the student's directories. Be careful not to overwrite a file and wipe out its last modified time.

Appeals Procedure

See the Code of Student Rights and Responsibilities, located in the Class Schedule for more details.  Also, see:

  http://www.coe.utah.edu/dean_coe/t_guidelines.html

Assignment Late Policy

No late work is accepted. 

Individual Work

The purpose of the assignments is to improve your skills at solving problems and demonstrating that you understand the class material. Collaboration with other class members is acceptable in understanding problems or software tools. For any individual assignments or work turned in, you must do your own work. Using someone else's work or giving someone else your work is considered plagiarism and will be dealt with using standard College and University procedures.

Registration

See  http://www.coe.utah.edu/dean_coe/t_guidelines.html for the full academic calendar and withdraw guidelines. 

American with Disabilities Act (ADA)

The University conforms to all standards of the ADA. If you wish to qualify for exemptions under this act, notify the Center for Disabled Students Services, 160 Union.