SI335: Project 3

Executive Summary: WormWorld

Important: This is a combination Project 3 and Problem Set 4. That means that it is to be done as a group. The rules for the assignment follow those for the Problem Sets rather than programming projects, which is to say that there is to be no discussion or exchange of ideas with anyone outside your group. Discussion within the group is, of course, not only OK, but kind of the whole point!

The abstract problem we consider is called WORMWORLD. It takes place on an infinite grid on which we have as input:

barriers, which are contiguous vertical or horizontal strips of cells that are off-limits,
food, which are individual grid locations, no duplicates allowed, at which "food" exists - where each food has an integer "value" associated with it,
a start position and direction, which is the position and direction the worm starts at, and
a duration, which is a cap on how many steps your worm gets to take.

The problem is this: find a path consisting of at most duration steps, that maximizes the total value of the food you eat along the way. Below, you'll have some questions to answer about this problem!

The concrete problem you'll have to address in your program is slightly simplified from the abstract WORMWORLD problem: the grid will be finite (so you don't wander off the screen, which makes for dull animation), and the food will all have value 1 (thereby simplifying our programming job a bit), which means we are trying to maximize the number of food items eaten within duration steps. Your program will act as the "brain" for a worm. I've written a simulator that takes an input, spawns a process of your brain program, and shows the worm as your brain drives it around. Your main goals are to make a worm brain that steers the worm so that lots of food gets eaten, and also a brain that operates successfully in an environment in which there are several worms competing for food. This planning problem is hard, so you'll have to find ways to make it fast enough to compete in WormWorld.

Important: Look closely at pages: The Protocol and An Example. The interaction between the simulator and the worm brains you write is not difficult. If you read these pages closely, you'll know everything you need.

What you get from me

First and foremost:

Download the following: stu.tar.gz
Unpack with the command: tar xf stu.tar.gz
Cd into the "stu" directory, and give the command: make Greedy

This will give you the basic pieces you need to get started. In particular, you should be able to give the command

./p3game i1a ./dbgreedy

and see a game play out. Here are the basic pieces I've given you:

p3game - the WormWorld simulator. Run: ./p3game -h for information.
Greedy.java - a very limited WormBrain. This follows a simple greedy strategy in which you move towards your "target", which was the food closest to your starting position. When you hit the target, you choose as your new target the unvisited food position that is closest to your old target, where closest means "manhattan distance" on the grid, i.e. without taking into account the barriers! Simpleminded though it may be, Greedy.java is a good starting point for you because it shows how you might handle the communication between your brain and my simulator. If you give the command "make Greedy", this will be compiled into the executable "greedy", which you can run in the game simulator like this:
```
	    ./p3game i1a ./greedy
                      |      |
	              |      \_ the executable to run for worm brain 0
                      |
                      \_ the board file to run on
	  
```
You can modify this to create your own solution. The original "greedy" worm brain is also in "dbgreedy" in case you want to run the original in the simulator after you've made modifications to Greedy.jar.
Pos and Dir - these are classes you might find useful for your own programs (See documentation Pos javadoc and Dir javadoc ).
ShortestPathOracle - this class does breadth-first search on a grid with barriers (like our game board) to find shortest paths (See documentation ShortestPathOracle javadoc and ).
NOTE: if you downloaded the original stu.tar.gz you are missing the files: ShortestPathOracle$DistMove.class and ShortestPathOracle$DistPos.class. Do an "ls" to check and, if they're not there, download these to files and put them in your stu directory.
Makefile - this has a single target (Greedy) in it right now, which compiles Greedy.java into an executable "greedy" that you can run like this: ./greedy
i1a, i1b, i1c - these are a few simple board files to get you started. I'll provide more later.

Problem 1: True Distance

At its heart, the WORMWORLD problem is a graph problem. You treat the food (and your starting position) as vertices in a graph. Each pair (u,v) of vertices is connected by an edge with weight equal to the number of moves it takes to get from u's position to v's position, or vice versa. The graph problem is to find a path (from your starting point) that hits the most vertics given that the sum of the edge-weights along the path doesn't exceed the limit "duration".

The greedy algorithm I gave you in the original Greedy.java attempts to follow the strategt of finding a path in this graph by following the edge of least weight that connects the current vertex to an unvisited vertex (i.e. we try to make the "nearest food" choice). However, this algorithm is flawed! It uses the "manhatten distance" between position $i$ and $j$, which is $|row_i - row_j| + |col_i - col_j|$, to compute edge weights (i.e. to decide which food is "nearest"). The problem is that this doesn't take the barriers into account! So you need to be able (in a single worm environment) to determine the true distances between different pieces of food (and between food and your starting point), where "true distance" means the actual number of steps it will take given that there may be barriers in your way.

To Do: The class ShortestPathOracle provides functionality for finding shortest paths on a grid like ours. Look carefully at the documentation for it. (Note: it just does breadth-first search. I didn't have the heart to make you guys implement it thoough!) Modify the Greedy.java so that your worm uses the "nearest food" greedy choice using true distances on the board (not Manhattan distance!). Feel free to use the ShortestPathOracle to get those distances.
Note: You should see improvement on i1a, i1b and i1c in terms of the number of food items eaten. Also, qualitatively, you should see that the worm moves in a more direct, logical manner; avoiding barriers. Try board-file i2a if you want a real obvious example of where the original greedy worm is bad and yours is good.

Requirements: You must have a makefile with target "Sol1" that compiles your worm brain to a single executable file named sol1. If you add these lines to the Makefile that came in "stu", and call your driver .java file "Sol1.java", that should do the trick. I will make and run your program as follows:

	  make Sol1
	  ./p3game i2a ./sol1

So if that works when you try it, you should be OK.

WRITTEN PROBLEMS

The "abstract problem" that I really care about has a "value" associated with each piece of food. For our program, each piece of food has value 1 ... it just makes things a bit easier, and the "value" is hard to visualize when we pop up a Window from the simulator. However, suppose we did have values associated with each piece of food: define a good "greedy choice" for a worm in such a world.
To the right is a desciption of a "board chunk" you can make that has an interesting property. If you have even integer w and arbitrary integer v, the corresponding board chunk has the property that to get from start to finish, you can either take 4 steps, but get zero food value, or take 4+w steps and get food value of v. Any other 0-value path you take will be longer than 4, and any other v-value path you take will be longer than 4+w. Using this "board chunk" idea prove that WORMWORLD is NP-Hard.
Why in the previous problem did I ask you to prove WORMWORLD is "NP-Hard" rather than "NP-Complete"?

Problem 2: Many Solutions

The greedy algorithm at this point is "deterministic". Which means that it always gives the same answer to the same problem. As discussed in class, it's good to add some randomness to the way the greedy algorithm operates, so that you can run it over and over, getting different solutions each time. In this case, we would keep the solution that hits the most food.

To Do: Describe a modification to the greedy algorithm that incorporates some randomness, so that we get different solutions, but still benefit from the "pretty good" quality of solutions produced by our greedy algorithm. Then, implement your randomized greedy algorithm in a new worm, which runs the randomized greedy algorithm many times, keeping the highest quality solution to use as the actual path you follow. Note: You have 5 seconds from the time you receive the s (start) message to plan your path. Then you have to respond to each m (move) message within 50ms. This is "wall clock" time, not CPU time. You can use

System.currentTimeMillis()

to keep track of ellapsed time. You should stop trying to generate new randomized greedy solutions when you get near to 5000 milliseconds of ellapsed time. That way you'll get an answer within the time limit.
Important: Try your worm brain on boardfile i5a. It should substantially outperform the greedy worm!

Requirements: You must have a makefile with target "Sol2" (or add the target to your Sol1 Makefile) that compiles your worm brain to a single executable file named sol2. I will make and run your program as follows:

	  make Sol2
	  ./p3game i5a ./sol2

So if that works when you try it, you should be OK.

WRITTEN PROBLEMS

Draw an example board where the greedy algorithm that uses true distance still fails to get within a factor of two of the optimal solution. Note: this means that your Problem 1 program, while it is an improvement over the original greedy worm brain, is not the end of the story!

Problem 3: Local Refinement

Finally, add some "Local Refinement" to your solution. In this approach, each greedy algorithm is repeatedly improved by "local refinement" before moving on to the next randomized greedy solution. I'd like you to come up with your own local refinement "operator", but I'll suggest one in case nothing comes to mind. Take a piece of food not in your path, and see if there is any position in the path that we could "splice" the new food object into the path without having the overall length of the path exceed the limit "duration".

To do: describe your local refinement operator in pseudo-code, then implement it to create a new (and hopefully even better) worm brain.
Important: Try your worm brain on boardfiles i3e and i4c. It should be able to do better than your Problem 2 worm brain, which only uses randomized greedy.

Requirements: You must have a makefile with target "Sol3" (or add the target to your Sol1/Sol2 Makefile) that compiles your worm brain to a single executable file named sol3. I will make and run your program as follows:

	  make Sol3
	  ./p3game i3e ./sol3

So if that works when you try it, you should be OK.

WRITTEN PROBLEMS

You are doing "randomized greedy + local refinement". Suppose your group came up with 10 different "operators" to use with local refinement. Why might it actually be less effective to use all 10 operators, and instead be better to just choose one or two to use?
Let $c$ be the cost of one call to "the oracle". Give an analysis of the worst-case running time of one round of "local refinement" within your algorithm. An O-bound is sufficient.

Submission and Presentation Instructions

Part 1 By COB Tuesday, 25 May, you must submit your Part 1 solution, and it must pass the test(s) there. At a bare minimum, it should find a path that gets all the food in WormWorld file i2a. If you take a look at that file, you should see why the original greedy worm brain did poorly but yours should do well. To submit part 1, cd to your stu directory with all your code and give the command:
```
~/bin/submit -c=SI335 -p=Proj03p1 *
```
Part 3 (which subsumes Part 2) Due COB Tuesday, 2 May, though I won't hold it against you if you submit during the reading day (3 May). To submit cd to your "stu" directory
```
~/bin/submit -c=SI335 -p=Proj03 *
```
Make sure you have the target Sol3 in your makefile, and make sure it builds an executable named sol3.
Note: I will run your Sol3 worm brain in the tournament. If, however, you have a different version you would like me to use in the multi-worm portion of the tournament, have a special target Sol4 in the makefile that builds that executable, and name the executable sol4.
Non-Programming Problems You may either schedule an interview time with me, which can be any time up to the day before the final. Or, you can submit written solutions which I will grade on their own, in which case you should have them slid under my door before I arrive the morning after the reading day.

Guidelines on Working Together on Programs

The algorithm design and implementation effort is expected to be shared amongst the whole group. You all need to be in on the whole thing and conversant with the whole thing. You are not splitting up the work, you are all doing it together with the advantages of having many eyes and many ideas.

It is expected that your whole group works together and is intimately familiar with all of your submitted code. I will choose team members at random to explain code to me, just as I choose team members at random to present solutions to non-propgramming problems. Do your coding together, at least in pairs if not the whole group, rather than working on tasks separately.
Your group is responsible for ensuring that your programs function correctly! If your greedy implementation doesn't produce the exact, correct greedy route, you'll lose major points. If your optimum implementation doesn't produce optimum routes, you'll lose major points. So test, test, test!
In line with the previous point, I strongly suggest that you have a group-member go off early on and write a program that verifies answers, i.e. that takes an input file and string defining a route and verifies that the route makes it all the way to the last column without leaving the grid, and counts how many targets get picked up along the way.
Also in line with the earlier points on testing, I strongly suggest that you work out some examples by hand so that you have something with known correct answers to test with.