CSCE 782: Problem Set 4

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

The Mailmen Problem

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.

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: