CSCE 782: Problem Set 3

Due: Wednesday, 1 October 2003, @4pm

Upload Problem Set

Figure 1: The cargo problem implementation you will be using. You can get the source code here.

The Cargo Problem

For this problem you will provide your solution to the cargo problem. This problem is a variation on the problem presented in

and many other papers from the same authors. Their solutions to this problem are much more complicated than what I expected from you, of course.

In this problem there are a number of robots and a set of cargo units. All the robots and cargo units start at home base. The goal is for the robots to move all the cargo units to the destination patch. The problem is that the patches in the world are populated by mines which the robots cannot see. When a robot steps on a patch with one or more mines a mine might explode. If a mine explode it might kill one robot, but no more. If the mine did not explode then the robot can see the mine. The robots cannot communicate with each other at a distance and can only carry one cargo unit at a time. So, to summarize the rules of the game

  1. The robots can only move N,S,E,W and one unit at each step, that is, each time go is invoked.
  2. A robot can only communicate with other robots that are on his patch.
  3. A robot can only move one piece of cargo at a time. If the robot is killed the cargo is left in that patch.
  4. A mine will only kill one robot (IMPORTANT!). Once it does, the mine also disappears.
  5. A robot cannot "see" if there is a mine on any other patch except for the one it is standing on
  6. The robots know that the world is a torus and that they start at -9,-9 and must deliver to 9,9. They also know their current location (xcor,ycor)
  7. The best solution is the one that delivers all the cargo in the fewer number of time steps, averaged over several runs

I don't know what the best solution is for this problem, or even if it is possible to do it with 50 robots. If you find that you cannot do it then increase the number of robots, but do not decrease the number of mines.

It is clear that you will need to have some sort of coordination and since the robots cannot communicate over distance, this will mean they will have to arrange to meet. It is also clear that many robots will have to be sacrificed. Of course, the more you sacrifice the fewer that will remain for carrying the cargo.

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.
José M. Vidal
Last modified: Tue Sep 16 16:17:30 EDT 2003