Project 2: Make Hay While the Sun Shines

In Iceland, due to the high latitude and cold winters, the summer hay growing season is short. Farmers therefore optimize their activities to minimize downtime. If careful, they can sometimes squeeze in multiple harvests in a single summer season. The harvesters used in Iceland are highly automated. They cut the grass and package the cut grass into plastic-covered bales that are deposited at regular intervals, as I witnessed on a recent trip. At the end of the harvest, the field is covered in a somewhat regular pattern of hay bales.

Your job is to efficiently bring the hay from the field to the barn. You are equipped with a fleet of tractors each with a trailer. A tractor can hold one bale of hay using a forklift-like attachment. A tractor can also be attached to a trailer with a capacity of up to 10 bales of hay. Hay can be stacked or unstacked to/from the trailer using the tractor's forklift. For this to happen, the trailer must first be detatched from the tractor.

Your primary goal is to collect the hay within a given time threshold T. If you take significantly less time (say t), all the better. A secondary goal is to be efficient, i.e., to use only as many (say n) of the tractors as you really need to get the job done. At the end of the simulation, groups will be ranked lexicographically on the (n,t) pair, smaller being better. (We'll allow groups to run multiple simulations with different n, and the smallest n that meets the time threshold will be used for the rankings.)

The field is m meters by m meters, and has opposing corners at (0,0) and (m,m). We'll vary m, but a typical value might be m=400. For reasons outlined below, we'll assume m is a multiple of 5. The barn is at (0,0) and all tractors start there. Tractors can move at 10m/s when unattached, but only at 4m/s when attached to a trailer, no matter how full the trailer is. Tractors can park their trailers in the field, and re-attach them later. They can even attach a trailer that was brought to the field by a different tractor.

The layout of the hay is determined by a slightly randomized process as follows. The harvester sweeps across the field cutting a 5-meter width swath as it goes. Due to natural variation in the density of the grass, a bale of hay will be generated every h meters, where h is a random variable uniformly distributed between 20 and 30. The lateral position of the bale within the 5 meter span is also uniformly random. When the harvester reaches the end of a ``row,'' it turns around and proceeds in the opposite direction along the next ``row.'' So the expected number of bales in the field will be m²/125.

We'll provide code that generates the bale distribution given a random number seed and m. The coordinates of all bales are available at the beginning of the game. For the tournament, groups will be evaluated on an identical hay layout.

The API of the game will be provided later. The simulator will ask for a command for each tractor, and will calculate exactly how long it takes for each tractor to execute its command. When the earliest of these is complete, the simulator will ask for another command, and so on. A tractor can execute one of the following commands, with the time needed as follows:

1. Move-to(location). Time depends on distance and whether tractor is attached to a trailer.
2. Detatch. 1 minute. (The simulator will keep track of the position of the trailer, but the player should maintain that information too.) Only applies if the tractor has an attached trailer.
3. Attach. 1 minute. The tractor must be within 1 meter of a detatched trailer to execute this command. If by some chance there are multiple trailers within range, the simulator will choose the closest one. If there are no trailers in range, this command is a no-op that lasts 1 minute.
4. Load. 10 seconds. The tractor loads a bale of hay from the ground onto the forklift. The bale of hay must be within 1 meter, and if there is more than one nearby, the closest is taken. Loading can only happen if the forklift doesn't already hold a bale of hay.
5. Unload. 10 seconds. A bale of hay is deposited from the forklift onto the ground at the current location. (Only works if there's a bale on the forklift.) If the current location is within 1 meter of (0,0), the bale of hay is considered ``in the barn'' and disappears from the simulation.
6. Stack. 10 seconds. A bale of hay is deposited from the forklift onto the nearest detatched trailer, which must be within 1 meter. This operation will fail (i.e., be a no-op) if the trailer already holds 10 bales.
7. Unstack. 10 seconds. A bale of hay is put onto the forklift from the nearest detatched trailer, which must be within 1 meter.

The simulation ends when all bales are in the barn, or when time expires. We'll assume that trailers, tractors, and bales, are points, and will ignore collisions etc. Tractors start at (0,0) attached to their trailers. Note that a tractor can transport 11 bales at once: 10 in the trailer and one on the forklift.

Some things to think about:

• Should tractors work independently, or are there benefits to cooperation?
• Given that attached trailers slow down the tractors, when are they helpful and when are they detrimental?