Distributed Artificial Intelligence and Multiagent Systems

EECE 822

Spring 1999

Contents

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

2.1  Presentations

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:

2.2.2  Homework 2:

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:

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:

• a) Easy. No programming needed.
• b) Write a program that enumerates each of the allocations and prints each one in a different line. In the same line also print each of the agents' preference for that allocation. An agent's preference for allocation g equals 50 minus the minimum travel distance for the agent to visit all the customers it needs to visit in g and return to where it started.
• c) What is g^*?
• d) List the route of each salesman in g^*. Your program does not need to do this. You can do it by hand once you know what g^* is.
• e) Ignore this one. It is almost the same as b).
• f) Print the Clarke tax for the three agents in g^*. Hint: negative taxes are OK.
• g) Add up f).

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:

• Extend your talk (or any other section) into a 10-15 page critical analysis. This will require that you seek out the original sources, and any other relevant material.
• Implement any of the protocols or systems we talked about. This can be done in Java or C++ (or any language you want, as long as I can run it). Note that a multiagent simulation does not need to have multiple threads of execution. That is, you can write a program that simulates the behavior of many agents.
• Do one of the Level 2 or 3 problems from the book.
• Write an introduction and/or demonstration of one or more of the algorithms in HTML/Java/JavaScript.
• Anything else you can convince me of...

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.

References

[1]

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

[2]

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

[3]

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

[4]

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.

[5]

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

[6]

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

[7]

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

[8]

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.

[9]

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

[10]

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

[11]

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

[12]

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.

5  Final Project Descriptions

5.1  Path Visualize

• Members: Adrian Nida and Robert Webb.
• Description: Windows application that will simulate the LRTA* algorithm and display the shortest path on a graphical display. The display will consist of an image of MARVIN (Robot in 3D38) navigating the shortest route from the start to the goal node. The program will be on a user defined N x N grid. The user will select the starting location (Node) for Marvin as well as the Goal Node. The program will show marvin move along the best path as defined by the LRTA* algorithm. The paths are represented by the "grid lines" produced when the nodes are connected in a Grid Pattern. This will allow the number of possible paths to be N*N. Obviously the value of N will be constrained by the system on which the program is run. We had not considered obstacles. We will try to implement this feature IF time permits :) This would be analogous to removing a link between nodes and would allow for custom paths to be created. This adds an additional level of complexity to the program.
• Deliverables:

  1. MFC / C++ source code.
  2. executable based on above
  3. short presentation showing important code snippets and execution.
  4. To be run on WinTel boxes - preferably Pentium +
  5. Short instruction manual.

5.2  Online Demo for Path Finding Problem

• Members: Xufeng Shen
• Description:This project is to build a web site that demonstrates the path-finding problem. In detail, I am going to use HTML and Scripting languages to build a web page that describes the problem and explains the algorithms used in the demo. The core of the demo will be a Java applet. A graphical map will be built to simulate the real one. The map will contain nodes stand for cities and connecting lines stand for the roads. It is desirable that user can fully control of city's location, name and establishing roads. Use can define the problem by choosing his/her preferred departure city and destination city. User will also be able to choose one of the algorithms provided for computation. The task will be finding the path based on the algorithm user chose. The algorithms will include at least one that is not used in the Hw3. The searching will be visualized in the map and allow user to compare the difference between approaches.
• Deliverables:

  1. Executable file (Java and HTML files). [I will post them here-Jose].
  2. Screen shot of running result.
  3. Source code.

5.3  Cooperating Multi-Agents

• Members: Mehdi Jaafari-Lafti, Buddy Bilbrey
• Description:This project is going to show how agents can work together to accomplish a task. The task at hand is trash collection for which each of the agents will have equal capabilities. Using a centralized manager system, the agents will be able to communicate their surroundings and whether those surroundings have any trash in them that needs to be collected and disposed of. This is going to be simulated using a two dimensional grid that will represent each of the agents locations and actions.

• Deliverables: This project is going to be accomplished using Visual C++. It will be a multithreaded application (which is expanding both of the members programming skills) where each thread represents a different agent. The main thread will be the manager. There will be four worker threads, one for each quadrant. The quadrant size hasn't been determined at this time but is expected to be approximately a 12 x 12 grid. The user will define each of the locations of the trash within the grid that is to be picked up and disposed of. Of course, the program will prompt the user for this information. Frequently, the display on the screen will be updated to reflect the movement of the agents and the disposal of trash. The goal is to move the trash to the "goal" location which is going to be located in the center of the grid.

5.4  Shortest Path Algorithms for Real time Problems

• Members: Tirunagari Durga Deep, Kotla Kanoj Kumar, Sri Ram Chaturvedula.
• Description:We are going to use the Shortest Path Algorithm to find the Shortest path between the Agents so that it will find an Optimum path to the Destination using the LRTA* . We are planning to implement this algorithm for a real time problem. The language we are going to use is either Java / C++ and as given below we are going to supplement our program with a MS power Point Presentation and a Theretical Description of the various algorithms and papers on LRTA * algorithm and giving the various other applications of this algorithm.
• Deliverables: Detailed Power Point Presentation. Program Using C++ / JAVA. Detailed Theoretical Description.

5.5  Comparative Study of Algorithms

• Members: Shreekanth Chutkay, Siddhartha Nadella, Ganesh Vellore
• Description: This project will involve a comparative study of algorithms (4.2.4 asynchronous backtracking and 4.2.5 asynchronous weak-commitment ) based on their implementation for a constraint satisafaction problem (N Queens) It will involve a simulation of algorithm implementation for solving the N Queen problem and an analysis of the same based on the test results. Further details will be posted ASAP.
• Deliverables: . MFC / C++ Source Code. Executable File. Sample Test Results. Summary Analysis of Sample Results.

5.6  N-Queens

• Members: Raghavendra Katrapalli

• Description:JAVA Applet that will simulate the Backpropagation algorithm to solve the N Queens problems. The display will be an image of a chess queen in each row and there will be a number of queens(depending up on the size of the chess board, given by the user). The queens will arrange themselves by using the algorithm.
• Deliverables: .Readme file about the project(in brief) JAVA Source code file. Applet(class file) that is generated by the above code

5.7  Agent Based Work-Flow Design

• Members:Gautam Kumar Chitupolu, Mohan Prabhala, Narayanan Raju

• Description:This Project will show how agents will be used to support an Industrial team, and the research concerning them. A case study involving a prominent industry will be conducted and analyzed. Also, performatives in KQML will be written to show the interaction between the agents using JATLITE system.

• Deliverables: .KQML performative code, Literature on work flow in Industry and the case study, Critical Analysis between the system implemented with and without agents.

5.8  Moving Target Search

• Members: Dinesh Kumbham, Thattavaradaraj Sunil, Venkat Patloola

• Description: Implementation of moving target search algorithm. The problem space is a 20x20 grid in which a target moves in random and the problem solver tries to catch the target.

• Deliverables: Executable (java), project description, source code.