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.

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
^{2}- 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.

**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:

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.

José M. Vidal Last modified: Sat Nov 2 12:38:14 EST 2002