# CSCE 782: Problem Set 1

## Due: Monday, 8 September 2003 @4:00pm

### Upload Problem Set

Figure 1: The Tileworld implementation you will be using. Click on the picture to see the applet run and get the source code, or get the source code here

### Tileworld meets Netlogo

For this problem I have recreated the Tileworld, as described in pages 37-39 of the textbook, shown in Figure 1. Your goal is to solve the tileworld problem. You will be graded on how well you explain your approach as well as on how well your program performs. The tileworld originally appeared in

### Implementation

In my implementation, each time the `update` function is called all the agents (which I call robots) get a chance to move one unit. At each time a new tile appears with probability `tile-birth-prob` and lives exactly `tile-lifetime`. Similarty, at each time a new hole appears with probability `hole-birth-prob` and lives exactly `hole-lifetime`. The `score` is calculated using the formula from page 38 of the textbook, that is, the percentage of holes filled with respect to the total number of holes that have appeared.

You should concentrate on improving the agents' ability to move quickly move a tile to a hole before it dissapears, and without getting in each others' way.

Whenever your robot needs to move it should set the heading it wants (making sure that it is one of 0,90,180,270) and call `move-one` to move one step in that direction. This function makes sure that any tiles or other agents that are in that location are pushed away. This also means that one robot can push another one.

### Testing

I will test your program with `num-robots=1,2,3,10,20`, ```tile-birth-prob = hole-birth-prob = .5```, ```tile-lifetime 50, hole-lifetime = 20``` and with other variations on those numbers in order to test the robustness of your approach.

### Hints

1. Start early!
2. Think first. Then think it through again. Then implement it. Repeat.
3. Your robots can look at the `time-to-live` of the tiles and holes.

### Further Research

• What is the best solution to this problem? Is is even possible to find it?
• Can you come up with a solution that does not use any communications between the robots?
• What is the effect of cooperation in this problem? If the agents where selfishly trying to fill as many holes as possible (think of contractors each getting paid for the number of holes he filled), can you think of an incentive mechanism which would make them behave well as a team? Does your original solution work when we assume selfish agents?
• How robust is your solution if we allow robots to break unexpectedly? What if we gave tiles and holes lifetimes taken from a probability distribution?
• If we gave the holes priorities, so that you got different scores for filling each one, how would you have to change your solution?

### 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: (Choose any random number. This number will be your ID for this course.) 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. ```

### Questions

José M. Vidal
Last modified: Tue Aug 26 17:00:05 EDT 2003