CSCE 782: Problem Set 6

Due: Monday, 27 November 2002 @2:30pm

Upload Problem Set

Figure 1: Click on the image in order to see the applet and get the source code

Multiagent Search Algorithms

The only way to really understand how an algorithm works is by implementing it (even that might not be enough sometimes!), especially if the implementation has some nice graphics to show how the algorithm is progressing. As such, I have implemented the Adopt algorithm for the N-queens problem, as presented in

Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo. An Asynchronous Complete Method for General Distributed Constraint Optimization. In Proceedings of Autonomous Agents and Multi-Agent Systems Workshop on Distributed Constraint Reasoning, p. 104--118, 2002.

My implementation shows the number of messages sent by each agent. As you can see, the top two agents end up sending the great majority of the messages--not a fair distribution of labor. Running the program one step at a time with the traces on helps one understand how this algorithm works.

Unfortunately, I can't compare it with the algorithms we talked about in class because I have not implemented those. That is where you come in. For this problem set you will choose one of the search algorithms and implement it. During this xmas break I plan to set up a web page with all the netlogo implementations of standard MAS algorithms/problems that I have written over the year. I hope to include some of your models in there. You will, of course, receive full credit in bold letters. Your choices are (you only have to implement one!):

The n-queens problem using Asynchronous Backtracking.
The n-queens problem using Asynchronous Weak-Commitment Search.
The x-puzzle (for x=n² - 1) problem using Asynchronous Dynamic Programming.
The x-puzzle using LRTA*.
You could also try implementing any of these algorithms for a different problem (e.g., a maze, graph-coloring, etc.)
If you want a real challenge, you can try to improve on the Adopt algorithm by evening-out the distribution of messages amongst agents while maintaining the algorithm complete. I will require a proof that your algorithm works.

Submission Instructions

This problem set is to be done individually. You cannot ask or receive help from anyone. As will all the problem sets, you will hand them in using our department's dropbox. For the netlogo problem sets you will hand in only one file, your .nlogo file. You will use the information tab of the program for writing your detailed explanation of the techniques you used, how the program works, how to set the controls to obtain the different behaviors you want to show, etc. The information tab needs to start with:

Name: email: ID: I understand that it is the responsibility of every member of the Carolina community to uphold an maintain the academic standards and integrity of the University of South Carolina. Any member of the University community, who has reasonable grounds to believe that an infraction of the Code of Student Academic Responsibility has occurred, has an obligation to report the alleged violation. I certify that I have neither given nor received unauthorized aid on this problem set.

Questions

José M. Vidal

Last modified: Sat Nov 2 12:38:14 EST 2002