CSCE 782: Problem Set 6
Due: Monday, 27 November 2002 @2:30pm
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
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=n2 - 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,
- 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
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:
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