For this problem set you will implement a solution to the famous mailman problem. The mailman problem is an instance of the task allocation problem which is discussed in

- Michael Wooldridge. Introduction to MultiAgent Systems. John Wiley and Sons;. 2002. Chapter 7.3.1

- Jeffrey S. Rosenschein and Gilad Zlotkin. Rules of Encounter. The MIT Press. 1994.

Figure 1 shows the netlogo implementation I'm providing. The
triangles are the turtles, the white squares are the letters to
be delivered, and the yellow circles are letters that have been
delivered. Upon `setup`

the mailmen and letters are
randomly placed on the screen. Each letter is assigned a pair of
delivery coordinates. The job of the mailman is to move the
letters from their current position to the position specified by
their delivery coordinates. In doing so the mailman should also
try to minimize the total distance that they travel.

A little thinking about this problem should quickly lead you to conclude that there is an obvious algorithm for calculting the optimal allocation of letters to mailmen. And, this algorithm amounts to solving an exponential number of travelling-salesman problems, each of which is NP-complete. As such, we can quickly conclude that the optimal allocation, especially for 100 letters, is beyond our computational capabilities.

The solution you will provide will, therefore, be only an approximation to the optimal. I will look for the following qualities in your solution:

- The total distance should be minimized.
- The total distance should decrease as we increase the
number of mailmen. Notice (by clicking on
`run-tests`

) that my solution actually does the opposite! - The total distance should increase sub-linearly as the number of letters is increased.

Note also that in this implementation, unlike our previous ones,
each click of the `update`

button results in agents
moving different distances. This behavior is fine since the
agents record how much they have travelled.

**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: Tue Oct 21 11:26:46 EDT 2003