Distributed Artificial Intelligence and Multiagent Systems

EECE 822

Spring 1999


1  Basic Information
2  Grading Policy
    2.1  Presentations
    2.2  Homeworks
        2.2.1  Homework 1:
        2.2.2  Homework 2:
        2.2.3  Homework 3:
        2.2.4  Homework 4:
    2.3  Final Project
3  Motivation
4  Calendar
5  Final Project Descriptions
    5.1  Path Visualize
    5.2  Online Demo for Path Finding Problem
    5.3  Cooperating Multi-Agents
    5.4  Shortest Path Algorithms for Real time Problems
    5.5  Comparative Study of Algorithms
    5.6  N-Queens
    5.7  Agent Based Work-Flow Design
    5.8  Moving Target Search

NOTE: For online pointers to information about multiagent systems go to http://multiagent.com.

1  Basic Information

Time: TTH 11-12:15pm.
Location: SWE 2A24
Instructor: José M. Vidal
Office: SWE 3A47 office hours: TTH 2-3:30
Phone: 777-0928
Email: vidal@sc.edu
Web: http://jmvidal.cse.sc.edu
Class Homepage: http://jmvidal.cse.sc.edu/822/
Prerequisite: Artificial Intelligence.

We will be using the textbook ``Multiagent Systems: A Modern Approach to DAI'', edited by Gerhard Weiß. The book has not yet been published (MIT Press) so I have made it available as a course pack at Kinko's on 111 Greene Street (near Wendy's). This book is required. It costs around $30.

2  Grading Policy

Class Participation 10%
Presentation(s) 20%
Homeworks 30%
Final Project 40%

2.1  Presentations

Each student will have to deliver at least one presentation. Each presentation will cover one of the subsections on the book. The subsections available are: 3.3, 3.4, 4.2, 4.3, 5.2, 5.3, 5.4, 5.5, 5.6, 5.7, 5.8, 6.2, 6.3, 6.4, 6.5, 7.1, 7.2, 7.3-7.4, 8.2, 8.3. Each student must pick one subsection and tell me about it by the deadline shown on the calendar (Section 4). The subsections will be assigned on a first-come first-server basis. The dates for the actual talks appear in the calendar.

Each presentation will have two parts: an initial expository section where the student explains the material, and a shorter critical section where the student criticizes the approach presented. That is, each student should do some critical thinking do determine the pros and cons of the approach.

  1. The imitations of the approach/algorithm/language/protocol etc. presented.
  2. The domains on which it might be useful, and domains it is useless.
  3. Any barriers towards an effective deployment of the approach.
  4. Possible comparisons with other approaches.

The two parts of the talk must be made explicit and not intermingled.

2.2  Homeworks

The homeworks will largely be taken from the book. There will be around six homeworks, all posted here.

2.2.1  Homework 1:

Exercises 1, 2, and 3 from Chapter 1. Due Jan 26.

2.2.2  Homework 2:

This homework is based on the JATLite system. You will:

  1. Download the JDK 1.1 (if your machine does not already have it) and run the standard demo.
  2. Then you will change IPRCApplet.html so that it connects to my router, running on jmvidal.cse.sc.edu, on router port 4444 and registar port 4445. You will then run the IPRCApplet and register it. The name of your applet should be your name. Once you register, you should also connect, then quit your applet. If you have registered correctly your name will appear here immediately (remember to reload the page!).
  3. Exercises 5, 6, and 7 from Chapter 2 in the book.

Howework 2 is due Feb. 9.

2.2.3  Homework 3:

Do exercise 1 from Chapter 4.Your program should also be able to handle NxN puzzles (not just 3x3). The programming can be done in any language, preferably Java or C++. You will need to email me the source code, as well as an executable. You will also turn in a hardcopy printout of the source code, which will include some example cases. The programs do not need to use any graphics, text output is fine. Please contact me if you have any questions.

Your program will need to accept input that tells it the initial board configuration, as well as print out the whole board at each step of the algorithm.

Homework 3 is due Feb. 23.

2.2.4  Homework 4:

Do exercise 2 (a-g) from Chapter 5. It requires a little programming. For this excercise g is a possible allocation of customers to salesmen. Following are clarifications for each one of the subparts of the question.

You will turn in a printout of the answers to a-g. You will also turn an email or hardcopy of your program.

Homework 4 is due March 23.

2.3  Final Project

The final project will be a project of your choice. The projects can be done by groups of up to three people. The more people are in the group, the more elaborate the project needs to be. Project proposals will be due towards the middle of the term. These will not be graded, I will simply approve them or tell you if it needs more work.

Some time early in the term I will be introducing the JATLite system (http://java.stanford.edu). Some of the projects could use this system to implement simplified versions of the protocols we have been talking about.

Other project ideas are:

Some interesting articles you can build upon or even just reimplement are [5], [9], [10],[12], [1], [2]. Some of these are books that include many papers with interesting experiments.

3  Motivation

The study of multiagent systems began within the field of distributed artificial intelligence (DAI) about 20 years ago. Today multiagent systems are a very active area of research and are beginning to see commercial and industrial applications. Also, the exponential growth of the Internet and its ability to connect people and machines from all over the world is making the arrival of multiagent systems an inescapable consequence of such high degree of interconnectivity. Automated, intelligent communication between autonomous and selfish ``agents'' is fast becoming the bottleneck to the continued growth of productivity provided by the Internet.

However, building multiagent systems requires a lot more than just an understanding of communication protocols and distributed programming paradigms. It necessitates the mastery of such varied techniques as: agent communication languages, agent architectures, distributed problem solving, protocol design, complex adaptive system analysis, and organizational theory.

In this class we will present an introduction to the ideas, protocols, architectures, and outstanding problems in multiagent system design. By the end of the class the student should be able to understand the basic concepts and techniques behind multiagent systems, as well as have some experience implementing simple prototype systems and using some of the most popular protocols.


Robert Axelrod. The Complexity of Cooperation, chapter Evolving New Strategies, pages 10-29. Princeton University Press, 1997.

Robert M. Axelrod. The Evolution of Cooperation. Basic Books, 1984.

Jeffrey M. Bradshaw, editor. Software Agents. The MIT Press, 1997.

Michael D. Cohen, Rick L. Riolo, and Robert Axelrof. The emergence of social organization in the prisoner's dilemma: How context-preservation and other factors promote cooperation. Santa Fe 99-01-002.

Jim Doran. Simulating collective misbelief. Journal of Artificial Societies and Social Simulations, 1998.

Michael N. Huhns and Munindar P. Singh, editors. Readings in Agents. Morgan Kaufmann, San Mateo, CA, 1997.

C. Ronald Kube and Eric Bonabeau. Cooperative transport by ants and robots. Santa Fe 99-01-008.

Eric Malville and Francois Bourdon. Task allocation: A group self-design approach. In Proceedings of the Third International Conference on Multi-Agent Systems, pages 166-173, Paris, France, 1998. IEEE.

Mitchel Resnick. Turtles, Termites and Traffic Jams. The MIT Press, 1994.

Paul Resnick and Hal R. Varian. Recommender systems. Communications of the ACM, 40(3):56-58, March 1997.

Jeffrey S. Rosenschein and Gilad Zlotkin. Rules of Encounter. The MIT Press, Cambridge, MA, 1994.

José M. Vidal and Edmund H. Durfee. Learning nested models in an information economy. Journal of Experimental and Theoretical Artificial Intelligence, 10(3):291-308, 1998.

4  Calendar

This will be filled in dynamically. Note that the reading must be done before the class.

Date Material Covered Homework Reading Chp.
Jan. 12 Course Intro. What are agents.
Jan. 14 Agent Architectures 1.3-1.4
Jan. 19 Languages 1.5-2.2
Jan. 21 Agent Interaction Protocols Choice of talk due. 2.3
Jan. 26 JATLite HW 1 Due.JATLite
Jan. 28 Agent Demo
Feb. 2 Task Sharing (Bilbrey), Result Sharing (Webb) 3.3-3.4
Feb. 4 Constraint Satisfaction 4.2
Feb. 9 Path Finding (Nida)HW 2 Due.4.3
Feb. 11 Eval. Criteria (Chutkay), Dist. Planning (Tutukuri) 5.2, 3.5
Feb. 16 Auctions (Shen) 5.4
Feb. 18 Voting (Thattavaradaraj)5.3
Feb. 22Last Day to drop class.
Feb. 23 Bargaining (Chaturvedula) HW 3 Due. 5.5
Feb. 25 Equilibrium Market Mechanisms (Kotla)5.6
March 2 Contract Nets (Raju)5.7
March 4 Coalition Formation (Nadella)Project proposal due.5.8
March 9 Spring Break
March 11 Spring Break
March 16 Learning Characterization (Prabhala) 6.2
March 18
March 23 L. Coordination (Chitupolu) HW 4 Due.6.3
March 25 Learning and Comm. (Jaafari-Lafti), L. Agents (Bharatahpudi) 6.4, 6.5
March 30 Organizational Theory (Vellore) 7.1
April 1 Organizational Concepts (Palapolu) 7.2
April 6 Dynamics and Methodology (Katarepalli) 7.3-7.4
April 8 Logic (Kumbham) 8.2
April 13 Cognitive Primitives (Patloola) 8.3
April 15 BDI and Coordination (Nimmagadda) 8.4-8.5
April 20 Communications Primitives (Tirunagari)8.6-8.7
April 22 Progress Report in my Office (email me) No Class
April 27 Final Project Presentations
April 28 Last Day of Classes.
April 30 Final Project Due

5  Final Project Descriptions

5.1  Path Visualize

5.2  Online Demo for Path Finding Problem

5.3  Cooperating Multi-Agents

5.4  Shortest Path Algorithms for Real time Problems

5.5  Comparative Study of Algorithms

5.6  N-Queens

5.7  Agent Based Work-Flow Design

5.8  Moving Target Search

File translated from TEX by TTH, version 1.94.
On 21 Apr 1999, 15:19.