Project 4: Noah's helpers

According to the biblical story, Noah gathers a male and female of each species onto his ark to survive a great flood. What is left unsaid in that story is exactly how Noah and his helpers managed to efficiently track down exactly the right animals. It would have been possible, for example, for independent teams of helpers to retrieve duplicate animals, while missing certain species altogether, or missing one gender of a species.

Your task is to be Noah's personal assistant. You will coordinate some number h of helpers who can search the landscape for animals of interest. A helper can shepherd up to 4 animals at a time. The helpers can obtain animals and bring them back to the Ark. When a helper returns to the Ark, the helper gets up-to-date information about the animals that are currently on-board.

The landscape is 1000km by 1000km big, which we'll model as a 1000x1000 grid of cells. The Ark is positioned at a cell (X_A,Y_A) where X_A and Y_A are integers between 0 and 999 that are supplied as parameters to the simulator. A helper has a position (x,y) where x and y are floating point numbers, and the cell of the helper is $(\lfloor x \rfloor, \lfloor y \rfloor)$. Initially all helpers are on the Ark, and (x,y)=(X_A,Y_A).

When a helper enters a cell containing one or more animals, the helper has the option of adding each one to their flock. The helper knows the species and gender of each animal in their cell. When a helper moves onto the cell of the Ark, he/she automatically unloads the flock, and any animals of a species/gender that is not already on the ark is loaded on board. Duplicated animals do not contribute to the Ark and are removed from the simulation. An animal can also be released prior to reaching the Ark, say to make space for a higher-value animal. The released animal then occupies the cell on which it was released.

A helper can see 5km away. (This is a limit imposed by the curvature of the earth.) Noah cannot move, but he can send and receive signals (see below). People in this simulation can see other people within their sight radius, and can recognize individuals. They can also see animals in cells that overlap their sight radius. While people can determine an animal's species from a distance, they cannot determine the gender unless they are in the animal's cell.

Helpers and Noah can communicate by broadcasting a visual signal that anybody within sight-distance can see. On any one turn, a helper can broadcast one byte of information. Helpers and Noah know the turn number, so that it might be possible to embed time into the communication protocal, e.g., a value of 17 means one thing on even turns, and a different thing on odd turns. During a turn, a helper can move up to one kilometer in any direction. We'll think of a turn as corresponding to roughly 10 minutes of real time. Obtaining (and releasing) animals happens at the end of a turn, and does not take additional time.

After the helpers complete their turns, the simulator will allow animals to move. Animals that are not being shepherded each move with a probability of 0.5. If they do choose to move, the orthogonal cell with the fewest other animals currently on it is chosen as the destination. If there are ties, a candidate among the tied cells is randomly chosen.

There are S species of animals, all of which have male and female members. The species have different populations, meaning that some species may be rarer than others. Noah and his helpers know the animal poluations for each species, but do not know the precise locations or gender distribution of the animals at the start of the simulation. Each species $i, i=1,\ldots,S$ will have a total count $n_i \geq 2$. The simulator will place exactly n_i animals on random cells in the map. Cells can contain multiple animals. The simulator will choose an animal's gender at random with equal probability, except that the first two animals are guaranteed to be of opposite gender. S and the n_i values are input parameters that we'll vary to see how they affect the simulation.

The simulation ends at a time $T \geq 2016$ (at least 14 days) that is unknown to Noah or his helpers. At some point (time T-1008) in the simulation, it will start raining. At that point, helpers have exactly 7 days (1008 turns) to return to the Ark.

At the end of the simulation, all helpers must be on the Ark. The team will score 100 points for each species saved (i.e., both a male and female on board) and one point for each species for which only one member is on the Ark.

We'll run a tournament at the end of the project with various values for h, (X_A,Y_A), T, S and the species populations to cover various kinds of scenario.

Some things to think about:

• How will your strategy differ when there are many helpers compared with just a few?
• Should helpers be coordinating their efforts or operating independently?
• How does a species' rarity factor into your decision-making?